Simple Gene Assembly Is Deterministic

• Autorzy: Langille M. , Petre I.
• Języki publikacji: EN

Abstrakty

EN

We investigate in this paper a simple intramolecular model for gene assembly in ciliates. Unlike the general intramolecular model, the folds that a micronuclear chromosome may form to assemble the genes is very restricted (minimal) here: between any two pointers there may be at most one coding block. It has been known that the general model is universal, being able to assemble any gene pattern (to sort any signed permutation). The simple model on the other hand is not universal: there exist signed permutations that cannot be sorted in this model. Remarkably though, all known micronuclear gene patterns in ciliates can indeed be assembled in the simple model. We prove in this paper that while the general model is non-deterministic, the simple model is ``weakly deterministic'': any gene pattern either has only successful or only unsuccessful sorting strategies. Moreover, although different strategies may lead to different permutations for the same input, these final results have the same structure.

Słowa kluczowe

EN

gene assembly; signed permutations; simple operations; determinism

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 73, nr 1-2
• Strony: 179--190
• Opis fizyczny: bibliogr. 23 poz.

Twórcy

autor

Langille M.

autor

Petre I.

• Academy of Finland and Turku Centre for Computer Science, Department of Computer Science, Abo Akademii University, FIN-20520 Turku, Finland,

Bibliografia

• [1] A. Cavalcanti, T.H. Clarke, L. Landweber: MDS IES DB: a database of macronuclear and micronuclear genes in spirotrichous ciliates. Nucleic Acids Research, 33, (2005), 396-398.
• [2] A. Ehrenfeucht, T. Harju, I. Petre, D. M. Prescott, G. Rozenberg: Formal systems for gene assembly in ciliates. Theoret. Comput. Sci., 292 (2003), 199-219.
• [3] A. Ehrenfeucht, T. Harju, I. Petre, D.M. Prescott, G. Rozenberg: Computation in Living Cells: Gene Assembly in Ciliates. Springer-Verlag, Berlin, 2003.
• [4] A. Ehrenfeucht, I. Petre, D.M. Prescott, G. Rozenberg: Universal and simple operations for gene assembly in ciliates. In Words, Sequences, Languages: Where Computer Science, Biology and Linguistics Meet (V. Mitrana, C. Martin-Vide, eds.), Kluwer Academic, Dortrecht, 2001, 329-342.
• [5] A. Ehrenfeucht, I. Petre, D.M. Prescott, G. Rozenberg: String and graph reduction systems for gene assembly in ciliates. Math. Structures Comput. Sci., 12 (2001), 113-134.
• [6] A. Ehrenfeucht, D.M. Prescott, G. Rozenberg: Computational aspects of gene (un)scrambling in ciliates. In Evolution as Computation (L.F. Landweber, E. Winfree, eds.), Springer-Verlag, Berlin, 2001, 216-256.
• [7] T. Harju, I. Petre, V. Rogojin, G. Rozenberg: Simple operations for gene assembly. In: Proceedings of DNAbased computers 11, Springer-Verlag, Berlin, to appear (2006).
• [8] T. Harju, I. Petre, G. Rozenberg: Gene assembly in ciliates: molecular operations. In Current Trends in Theoretical Computer Science (G. Paun, G. Rozenberg, A. Salomaa, eds.), World Scientific, Singapore, 2004, vol. 1, 527-542.
• [9] T. Harju, I. Petre, G. Rozenberg: Two models for gene assembly in ciliates. LNCS 3113, Springer-Verlag, Berlin, 2004, 89-101.
• [10] T. Harju, I. Petre, G. Rozenberg: Modelling simple operations for gene assembly, submitted. Also as a TUCS technical report www.tucs.fi, 2005.
• [11] T. Harju, I. Petre, G. Rozenberg: Modelling simple operations for gene assembly, submitted, 2005. Also as a TUCS technical report TR697, http://www.tucs.fi
• [12] L.F. Landweber, L. Kari: The evolution of cellular computing: Nature's solution to a computational problem. In Proceedings of the 4th DIMACS Meeting on DNA-Based Computers, Philadelphia, PA, 1998, 3-15.
• [13] L.F. Landweber, L. Kari: Universal molecular computation in ciliates. In Evolution as Computation (L.F. Landweber, E. Winfree, eds.), Springer-Verlag, Berlin, 2002.
• [14] D.M. Prescott: Cells: Principles of Molecular Structure and Function. Jones and Barlett, Boston, 1988.
• [15] D.M. Prescott: Cutting, splicing, reordering, and elimination of DNA sequences in hypotrichous ciliates. BioEssays, 14 (1992), 317-324.
• [16] D.M. Prescott: The unusual organization and processing of genomic DNA in hypotrichous ciliates. Trends in Genet., 8 (1992), 439-445.
• [17] D.M. Prescott: The DNA of ciliated protozoa. Microbiol. Rev., 58 (1994), 233-267.
• [18] D.M. Prescott: The evolutionary scrambling and developmental unscabling of germlike genes in hypotrichous ciliates. Nucl. Acids Res., 27 (1999), 1243-1250.
• [19] D.M. Prescott: Genome gymnastics: unique modes of DNA evolution and processing in ciliates. Nat. Rev. Genet., 1 (2000), 191-198.
• [20] D.M. Prescott, M. DuBois: Internal eliminated segments (IESs) of Oxytrichidae. J. Eukariot. Microbiol., 43 (1996), 432-441.
• [21] D.M. Prescott, A. Ehrenfeucht, G. Rozenberg: Molecular operations for DNA processing in hypotrichous ciliates. Europ. J. Protistology, 37 (2001), 241-260.
• [22] D.M. Prescott, G. Rozenberg: How ciliates manipulate their own DNA - A splendid example of natural computing. Natural Computing, 1 (2002), 165-183.
• [23] D.M. Prescott, G. Rozenberg: Encrypted genes and their reassembly in ciliates. In Cellular Computing (M. Amos, ed.), Oxford University Press, Oxford 2003.