A1 Refereed original research article in a scientific journal
Formal properties of gene assembly: Equivalence problem for overlap graphs
Authors: Harju T, Petre I, Rozenberg G
Publisher: SPRINGER-VERLAG BERLIN
Publication year: 2004
Journal:: Lecture Notes in Computer Science
Journal name in source: ASPECTS OF MOLECULAR COMPUTING
Journal acronym: LECT NOTES COMPUT SC
Volume: 2950
First page : 202
Last page: 212
Number of pages: 11
ISSN: 0302-9743
Abstract
Gene assembly in ciliates is a life process fascinating from both the biological and the computational points of view. Several formal models of this process have been formulated and investigated, among them a model based on (legal) strings and a model based on (overlap) graphs. The latter is more abstract because the translation of legal strings into overlap graphs is not injective. In this paper we consider and solve the overlap equivalence problem for realistic strings: when do two different realistic legal strings translate into the same overlap graph? Realistic legal strings axe legal strings that "really" correspond to genes generated during the gene assembly process.
Gene assembly in ciliates is a life process fascinating from both the biological and the computational points of view. Several formal models of this process have been formulated and investigated, among them a model based on (legal) strings and a model based on (overlap) graphs. The latter is more abstract because the translation of legal strings into overlap graphs is not injective. In this paper we consider and solve the overlap equivalence problem for realistic strings: when do two different realistic legal strings translate into the same overlap graph? Realistic legal strings axe legal strings that "really" correspond to genes generated during the gene assembly process.
UTU Research Portal