Formal properties of gene assembly: Equivalence problem for overlap graphs



: Harju T, Petre I, Rozenberg G

Publisher: SPRINGER-VERLAG BERLIN

: 2004

Lecture Notes in Computer Science

ASPECTS OF MOLECULAR COMPUTING

: LECT NOTES COMPUT SC

: 2950

: 202

: 212

: 11

: 0302-9743


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.



Last updated on 2025-14-10 at 09:49