Browsing by Author "Korkin, Dmitry"

Now showing 1 - 6 of 6
  • Thumbnail Image
    Item
    A New Dominant Point-Based Parallel Algorithm for Multiple Longest Common Subsequence Problem
    Korkin, Dmitry
    This work introduces a new parallel algorithm for computing a multiple longest common subsequence (MLCS). Given a set of strings, the longest common subsequence can be obtained by removing a number of symbols from each sequence. Although there was a lot of research done in the parallelization of MLCS algorithms for the special case of two sequences, so far there were no any general parallel methods for computing MLCS of an arbitrary number of sequences. Our method is a parallel approach to dominant points-based method recently proposed by Hakata and Imai. The parallel algorithm is presented and the related theoretical results as well as the algorithm’s implementation on IBM SP3 using MPI system are discussed. Keywords: longest common subsequence, dominant points, parallel algorithms, IBM SP3
  • Thumbnail Image
    Item
    On a novel evolutionary based model for genome rearrangement
    Korkin, Dmitry
    The role of understanding the genome rearrangement is becoming more and more crucial in the modern life sciences. The new, alternative model explaining the process of genome rearrangement as well as the relationships between diverged gene-order sequences is proposed. The main characteristic feature of the model is its evolutionary nature: the gene-order sequences are viewed as the result of evolutionary genome development, that is, consecutive transformation of the ancestral genome via non-local genome mutations of two types, insertion and reversal. The close relationship of the above evolutionary-based mutations in the proposed model and “traditional” genome rearrangement mutations, such as, reversal and transposition, is discussed. A new, multiple longest common subsequence-based, method for extraction the evolutionary processes directly related to genome rearrangement is presented. Its advantages, disadvantages and future enhancements are outlined.
  • Thumbnail Image
    Item
    What Is a Structural Representation in Chemistry: Towards a Unified Framework for CADD?
    (2001) Goldfarb, Lev; Golubitsky, Oleg; Korkin, Dmitry
    A fundamentally new formal framework for structural representation of organic compounds based on the first "true" (general) formalism for structural object representation recently proposed by us|evolving transformation system (ETS) model is outlined. The applied orientation of the paper is towards the molecular design in general and computer aided drug design (CADD) in particular. Inadequacies of the conventional models used in (CADD) for molecular representation and classification as well as the advantages of the proposed ETS model are discussed. Some advantages of the ETS model is its capability to represent naturally all important structural features of molecules, e.g. different atoms and their bonding types (including hydrogen bonding), basic 2D and 3D isometries, the molecular class structure. The model allows one not only to classify a new compound, but also to construct a chemically valid new compound from the class of compounds that was previously learned based on a small set of examples. The model also guarantees the inheritance of the chemical structural class information from the parent class to all its subclasses. In general, the ETS model offers a much more precise "language" for chemical structural formulas. The central role of the class learning problem in CADD is suggested. Moreover, we propose the ETS model as a unified framework for the class learning problem and therefore as a unified formal framework for CADD. This would allow considerable streamlining of the CADD by assigning to the chemist the role of an interactive user of the system rather that a role of a human weak link within the CADD process.
  • Thumbnail Image
    Item
    What Is a Structural Representation?
    (2001) Goldfarb, Lev; Golubitsky, Oleg; Korkin, Dmitry
    We outline a formal foundation for a “structural” (or “symbolic”) object/event representation, the necessity of which is acutely felt in all sciences, including mathematics and computer science. The proposed foundation incorporates two hypotheses: 1) the object’s formative history must be an integral part of the object representation and 2) the process of object construction is irreversible, i.e. the “trajectory” of the object’s formative evolution does not intersect itself. The last hypothesis is equivalent to the generalized axiom of (structural) induction. Some of the main difficulties associated with the transition from the classical numeric to the structural representations appear to be related precisely to the development of a formal framework satisfying these two hypotheses. The concept of (inductive) class representation—which has inspired the development of this approach to structural representation—differs fundamentally from the known concepts of class. In the proposed, evolving transformations system (ETS), model, the class is defined by the transformation system—a finite set of weighted transformations acting on the class progenitor—and the generation of the class elements is associated with the corresponding generative process which also induces the class typicality measure. Moreover, in the ETS model, a fundamental role of the object’s class in the object’s representation is clarified: the representation of an object must include the class. From the point of view of ETS model, the classical discrete representations, e.g. strings and graphs, appear now as incomplete special cases, the proper completion of which should incorporate the corresponding formative histories, i.e. those of the corresponding strings or graphs.
  • Thumbnail Image
    Item
    What is a structural representation? A proposal for an event-based representational formalism: Sixth Variation
    (2007) Goldfarb, Lev; Gay, David; Golubitsky, Oleg; Korkin, Dmitry; Scrimger, Ian
    We outline a formalism for structural, or symbolic, representation, the necessity of which has been acutely felt not just in artificial intelligence and pattern recognition, but also in the natural sciences, particularly biology. At the same time, biology has been gradually edging to the forefront of sciences, although the reasons obviously have nothing to do with its state of formalization or maturity. Rather, the reasons have to do with the growing realization that the objects of biology are not only more important (to society) and interesting (to science), but that they also more explicitly exhibit the evolving nature of all objects in the Universe. It is this view of objects as evolving structural entities/processes that we aim to formally address here, in contrast to theubiquitous mathematical view of objects as points in some abstract space. In light of the above, the paper is addressed to a very broad group of scientists. One can gain an initial intuitive understanding of the proposed representation by generalizing the temporal process of the (Peano) construction of natural numbers: replace the single structureless unit out of which a number is built by multiple structural ones. An immediate and important consequence of the distinguishability (or multiplicity) of units in the construction process is that we can now see which unit was attached and when. Hence, the resulting (object) representation for the first time embodies temporal structural information in the form of a formative, or generative, object “history” recorded as a series of (structured) events. Each such event stands for a “standard” interaction of several objects/processes. We introduce the new concept of class representation via the concept of class generating system, which outputs structural entities belonging to that class. Hence, the concept of class is introduced as that of a class of similar structural entities, where the “similarity” of such entities is ensured by them being outputs of the same class generating system and hence having similar formative histories. In particular, such a concept of class representation implies that—in contrast to all existing formalisms—no two classes have elements in common. The evolving transformation system (ETS) formalism proposed here is the first one developed to support such a new vision of classes. Most important, since the operations that participated in the object’s construction are, for the first time, made explicit in the representation, it makes the inductive recovery of class representation (on the basis of object representation) much more reliable. As a result, ETS offers a formalism that outlines, for the first time, a tentative framework for understanding what a class is. Even this tentative framework makes it quite clear that the term “class” has been improperly understood, used, and applied: many, if not most, of the current “classes” should not be viewed as such. A detailed example of a class representation is included. In light of ETS, the classical discrete “representations” (strings, graphs) appear as incomplete special cases at best, the proper adaptation of which should incorporate corresponding formative histories, as is done here. The gradual emergence of ETS—including the concepts of structural object and class representations, the resulting radically different (temporal) view of “data”, as well as the associated inductive learning processes and the representational levels—points to the beginning of a new field, inductive informatics, which is intended as a class oriented rival to conventional information processing paradigms.
  • Thumbnail Image
    Item
    What is a structural representation?: Second version
    (2004) Goldfarb, Lev; Gay, David; Golubitsky, Oleg; Korkin, Dmitry
    We outline a formalism for “structural”, or “symbolic”, representation, the necessity of which is acutely felt in all sciences. One can develop an initial intuitive understanding of the proposed representation by simply generalizing the process of construction of natural numbers: replace the identical structureless units out of which numbers are built by several structural ones, attached consecutively. Now, however, the resulting constructions embody the corresponding formative/generative histories, since we can see what was attached and when. The concept of class representation—which inspired and directed the development of this formalism—differs radically from the known concepts of class. Indeed, the evolving transformation system (ETS) formalism proposed here is the first one developed to support that concept; a class representation is a finite set of weighted and interrelated transformations (“structural segments”), out of which class elements are built. The formalism allows for a very natural introduction of representational levels: a next-level unit corresponds to a class representation at the previous level. We introduce the concept of “intelligent process”, which provides a suitable scientific environment for the investigation of structural representation. This process is responsible for the actual construction of levels and of representations at those levels; conventional “learning” and “recognition” processes are integrated into this process, which operates in an unsupervised mode. Together with the concept of structural representation, this leads to the delineation of a new field—inductive informatics—which is intended as a rival to conventional information processing paradigms. From the point of view of the ETS formalism, classical discrete “representations” (strings, graphs) now appear as incomplete special cases at best, the proper “completion” of which should incorporate corresponding generative histories (e.g. those of strings or graphs).