Directed Overlap-inclusion Graphs as Representations of Ciliate Genes

• Autorzy: Azimi S. , Harju T. , Langille M. , Petre I. , Rogojin V.
• Języki publikacji: EN

Abstrakty

EN

The simple intramolecular model for gene assembly in ciliates consists of three molecular operations based on local DNA manipulations. It was shown to predict correctly the assembly of all currently known ciliate gene patterns. Mathematical models in terms of signed permutations and signed strings proved limited in capturing some of the combinatorial details of the simple gene assembly process. A different formalization in terms of overlap-inclusion graphs, recently introduced by Brijder and Hoogeboom, proved well-suited to describe two of the three operations of the model and their combinatorial properties. We introduce in this paper an extension of the framework of Brijder and Hoogeboom in terms of directed overlap-inclusion graphs where more of the linear structure of the ciliate genes is described. We investigate a number of combinatorial properties of these graphs, including a necessary property in terms of forbidden induced subgraphs.

Słowa kluczowe

EN

directed overlap-inclusion graphs; gene assembly in ciliates; simple operations

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 110, nr 1-4
• Strony: 29--44
• Opis fizyczny: Bibliogr. 24 poz., wykr.

Twórcy

autor

Azimi S.

autor

Harju T.

autor

Langille M.

autor

Petre I.

autor

Rogojin V.

• Computational Biomodeling Laboratory, Turku Centre for Computer Science, Abo Akademi University, Turku 20520, Finland,

Bibliografia

• [1] Brijder, R., Harju,T., Jonoska, N., Petre, I., Rozenberg, G.: Gene assembly in ciliates. In: G. Rozenberg, T.H.W. Bck, J.N. Kok (Eds.): Handbook of Natural Computing, Springer, to appear, 2011.
• [2] Brijder, R., Hoogeboom, H.J.: Combining overlap and containment for gene assembly in ciliates. Theoretical Computer Science, 411(6), pp. 897-905. doi:10.1016/j.tcs.2009.07.047
• [3] Brijder, R., Langille, M., Petre,I. : A string-based model for simple gene assembly. In: E. Csuhaj-Varju and Z. Ésik (Eds.): Proceedings of FCT 2007, Springer, Lecture Notes in Computer Science 4639, 161-172, 2007.
• [4] Brijder, R., Langille, M., Petre, I.: Extended strings and graphs for simple gene assembly. Theoret Comp Sci, 411, 730-738, 2010.
• [5] Cavalcanti, A., Clarke, T.H., Landweber, L.: MDS IES DB: a database of macronuclear and micronuclear genes in spirotrichous ciliates. Nucleic Acids Research 33 (2005) D396-D398.
• [6] Ehrenfeucht, A., Harju, T., Petre, I., Prescott, D. M., Rozenberg, G.: Computation in Living Cells: Gene Assembly in Ciliates, Springer (2003).
• [7] Ehrenfeucht, A., Petre, I., Prescott, D. M., Rozenberg, G.: String and graph reduction systems for gene assembly in ciliates. Math. Structures Comput. Sci., 12, (2001), pp. 113-134.
• [8] Ehrenfeucht, A., Petre, I., Prescott, D. M., Rozenberg, G.: Universal and simple operations for gene assembly in ciliates. In: V. Mitrana and C. Martin-Vide (eds.) Words, Sequences, Languages: Where Computer Science, Biology and Linguistics Meet, Kluwer Academic, Dortrecht, (2001) pp. 329-342.
• [9] Ehrenfeucht, A., Prescott, D. M., Rozenberg, G.: Computational aspects of gene (un)scrambling in ciliates. In: L. F. Landweber, E. Winfree (eds.) Evolution as Computation, Springer, Berlin, Heidelberg, New York (2001) pp. 216-256.
• [10] Ehrenfeucht, A., Harju, T., Petre, I., Prescott, D. M., Rozenberg, G.: Formal systems for gene assembly in ciliates. Theoret. Comput. Sci. 292 (2003) 199-219.
• [11] De Fraysseix, H., Ossona de Menzdez, P.: A short proof of a Gauss problem. Lecture Notes in Computer Science, 1353, (1997), pp. 230-235.
• [12] Golumbic, M. C.: Algorithmic graph theory and perfect graphs, Academic Press,(1980), ISBN 0-12-289260-7.
• [13] Harju, T., Li, C., Petre, I., Rozenberg, G.: Complexity Measures for Gene Assembly In: K. Tuyls (Eds.), Proceedings of the Knowledge Discovery and Emergent Complexity in Bioinformatics workshop, Springer, Lecture Notes in Bioinformatics 4366, 42-60, 2007.
• [14] Harju, T., Petre, I., Rozenberg, G.: Formal properties of gene assembly: Equivalence problem for overlap graphs. Lecture Notes in Comput. Sci, 2950 (2004) 202-212.
• [15] Harju, T., Li, C., Petre, I., Rozenberg, G.: Modelling simple operations for gene assembly. In: Junghuei Chen, Natasha Jonoska, Grzegorz Rozenberg (Eds), Nanotechnology: Science and Computation, 361-376, Springer, 2006.
• [16] Harju, T., Petre, I., Rogojin, V., Rozenberg, G.: Patterns of simple gene assembly in Ciliates, Discrete Applied Mathematics, 156(14), Elsevier, (2008), pp. 2581-2597.
• [17] Harju, T., Rozenberg, G.: Computational processes in living cells: gene assembly in ciliates. Lecure Notes in Comput. Sci. 2450 (2003) 1-20.
• [18] Landweber, L. F., Kari, L.: 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) pp. 3-15.
• [19] Landweber, L. F., Kari, L.: Universal molecular computation in ciliates. In: L. F. Landweber and E.Winfree (eds.) Evolution as Computation, Springer, Berlin Heidelberg New York (2002).
• [20] Langille, M., Petre,I.: Simple gene assembly is deterministic. Fundamenta Informaticae 72 (2006) 1-12, IOS Press.
• [21] Langille, M., Petre,I., Rogojin, V.: Three models for gene assembly in ciliates: a comparison. Computer Science Journal of Moldova, 18 (1), 1-26, 2010.
• [22] Lekkerkerker, C., Boland, J.: Representation of a finite graph by a set of intervals on the real line, Fundam. Math. 51 (1962), 45-64.
• [23] Petre, I., Rozenberg, G.: Gene assembly in ciliates. Scholarpedia 5 (1), 9269, 2010.
• [24] Ehrenfeucht, Prescott, D. M., Rozenberg, G.: Molecular operations for DNA processing in hypotrichous ciliates. Europ. J. Protistology 37 (2001) 241-260.