Computational processes in living cells: Gene assembly in ciliates

: Harju T, Rozenberg G

: 2003

Lecture Notes in Computer Science

DEVELOPMENTS IN LANGUAGE THEORY

: LECT NOTES COMPUT SC

: 2450

: 1

: 20

: 3-540-40431-7

: 0302-9743

One of the most complex DNA processing in nature known to us is carried out by ciliates during the sexual reproduction when their micronuclear genome is transformed to the macronuclear genome. This process of gene assembly is intriguing and captivating also from the computational point of view. We investigate here three intramolecular molecular operations (ld, hi, and dlad) postulated to accomplish gene assembly. The formal models for these operations are formulated on three different abstraction levels: MDS descriptors, legals strings and overlap graphs. In general both legal strings and overlap graphs contain strings and graphs that do not model any micronuclear gene. After a short survey of gene assembly we study the problem of recognizing whether a general legal string or a general overlap graph is a formalization of a micronuclear gene.

Mathematics