The Structure of Elementary Strategies for Gene Assembly in Ciliates

• Autorzy: Rogojin V. , Petre I.

Identyfikatory

DOI

10.3233/FI-2015-1204

• Języki publikacji: EN

Abstrakty

EN

We consider in this paper the assembly of micronuclear genes in stichotrichous ciliates to their macronuclear form. We represent the micronuclear genes and all their intermediate forms from micro- to macro- as signed permutations, where integer i stands for the i-th MDS of the macronuclear gene and i stands for the inverted form of that MDS; the macronuclear assembled gene is represented as the sorted permutation 1 2 : : : n, while its micronuclear form is an arbitrary signed permutation. We focus on the elementary gene assembly model consisting of two operations on signed permutations: eh (elementary hairpin inverting) and ed (elementary double recombination); gene assembly is modeled in this framework as a permutation sorting process. The general problem we investigate is to give a characterization of all signed permutations that can be sorted by the elementary operations. We make progress towards a full solution for this problem by relating sequences of eh and ed operations applicable to a given permutation to paths in the dependency graph associated to that permutation.

Słowa kluczowe

EN

ciliata; permutations; genetic recombination; mathematical models; problem solving

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 138, nr 1/2
• Strony: 145--158
• Opis fizyczny: Bibliogr. 17 poz., rys.

Twórcy

autor

Rogojin V.

• Computational Biomodeling Laboratory, Turku Centre for Computer Science and Department of Information Technologies, Abo Akademi University 20520 Turku, Finland

autor

Petre I.

• Computational Biomodeling Laboratory, Turku Centre for Computer Science and Department of Information Technologies, Abo Akademi University 20520 Turku, Finland

Bibliografia

• [1] Angela Angeleska, Nataˇsa Jonoska, Masahico Saito, and Laura F. Landweber. RNA-guided DNA assembly. Journal of Theoretical Biology, 248(4):706–720, 2007.
• [2] Andrzej Ehrenfeucht, Tero Harju, Ion Petre, David M. Prescott, and Grzegorz Rozenberg. Computation in Living Cells: Gene Assembly in Ciliates. Springer, 2004.
• [3] Andrzej Ehrenfeucht, David M. Prescott, and Grzegorz Rozenberg. Computational aspects of gene (un)scrambling in ciliates. In Laura F. Landweber and Erik Winfree, editors, Evolution as Computation, Natural Computing Series, pages 216–256. Springer Berlin Heidelberg, 2002.
• [4] Tero Harju, Ion Petre, Vladimir Rogojin, and Grzegorz Rozenberg. Patterns of simple gene assembly in ciliates. Discrete Applied Mathematics, 156(14):2581–2597, 2008.
• [5] Tero Harju, Ion Petre, and Grzegorz Rozenberg. Modelling simple operations for gene assembly. In Junghuei Chen, Natasha Jonoska, and Grzegorz Rozenberg, editors, Nanotechnology: Science and Computation, Natural Computing Series, pages 361–376. Springer, 2006.
• [6] Lila Kari, Jarkko Kari, and Laura F. Landweber. Reversible molecular computation in ciliates. In Juhani Karhumäki, Herman Maurer, George Păun, and Grzegorz Rozenberg, editors, Jewels are Forever, pages 353–363. Springer Berlin Heidelberg New York, 1999.
• [7] Laura F. Landweber and Lila Kari. The evolution of cellular computing: nature’s solution to a computational problem. Biosystems, 52(1):3–13, 1999.
• [8] Laura F. Landweber and Lila Kari. Universal molecular computation in ciliates. In Laura F. Landweber and Erik Winfree, editors, Evolution as Computation, pages 257–274. Springer, 2003.
• [9] Miika Langille and Ion Petre. Simple gene assembly is deterministic. Fundamenta Informaticae, 73(1,2):179–190, 2006.
• [10] Miika Langille, Ion Petre, and Vladimir Rogojin. Three models for gene assembly in ciliates: A comparison. Computer Science Journal of Moldova, 18(1):1–26, 2010.
• [11] Mariusz Nowacki, Vikram Vijayan, Yi Zhou, Klaas Schotanus, Thomas G Doak, and Laura F. Landweber. RNA-mediated epigenetic programming of a genome-rearrangement pathway. Nature, 451(7175):153–158, 2008.
• [12] Ion Petre and Vladimir Rogojin. Dependency relations between elementary intramolecular operations in gene assembly in ciliates. Journal of Automata, Languages and Combinatorics.
• [13] Ion Petre and Vladimir Rogojin. Decision problems for shuffled genes. Information and Computation, 206(11):1346–1352, 2008.
• [14] David M. Prescott, A. Ehrenfeucht, and G. Rozenberg. Template-guided recombination for IES elimination and unscrambling of genes in stichotrichous ciliates. Journal of Theoretical Biology, 222(3):323–330, 2003.
• [15] David M. Prescott, Andrzej Ehrenfeucht, and Grzegorz Rozenberg. Molecular operations for DNA processing in hypotrichous ciliates. European Journal of Protistology, 37(3):241–260, 2001.
• [16] Vladimir Rogojin. Successful elementary gene assembly strategies. International Journal of Foundations of Computer Science, 20(3):455–477, 2009.
• [17] Grzegorz Rozenberg, Thomas B¨ack, and Joost N. Kok, editors. Handbook of Natural Computing. Springer, 2012.