Marion Scheepers

Algorithmic Phenomena in Nature


We are still in the early stages of a new scientific revolution. This time the revolution is driven also by the flood of discoveries and associated data in the life sciences. One of the underlying themes in these discoveries is that the great variety of observed phenomena about life are outcomes of well-defined processes (algorithms) following well-defined execution rules (programs).

One algorithmic phenomenon I have been giving particular attention to is related to a process occurring in ciliates: Ciliates are single celled eukaryotes with two types of nuclei. The one type of nucleus is an encrypted version of the other type. Some events in the cell's life cycle trigger decryption of the encrypted version, while the previously unencrypted nuclei present during the decryption process are degraded. We call the cellular machinary that accomplishes micronuclear decryption the decryptome.

At present laboratory investigations of the process did not yet identify enough cellular components of the decryptome to enable in vitro work. However:

A number of mathematical papers, as well as a textbook, investigating aspects proposed in the mathematical models have appeared in the literature.

Research opportunities:

Capabilities of the ciliate decryptome:

The actual molecular components of the ciliate decryptome have not yet been isolated for in vitro experimentation and exploitation. Current information of its capabilities is based on laboratory experimentation in vivo. The available mathematical models of parts of this process allows for theoretical exploration of the capabilities of the decryptome. Along these lines, Kari and Landweber have shown that for a certain proposed mathematical model of the actions performed by the decryptome the decryptome has the capabilities of a universal Turing machine [4].


Context directed swaps:

Context directed swaps, denoted cds, is one of the two permutation sorting operations postulated in [2] as used by the ciliate decryptome to accomplish micronuclear decryption. Not every permutation is sortable by cds. This fact raises the basic question of characterizing the cds sortable permutations. Such a characterization has been given in several journal articles. These studies focused almost exclusively on sortable permutations and their sortability. Related questions include whether for a cds-sortable permutation actually achieving a sorted permutation requires careful choice of which cds moves to apply. The cds Inevitability Theorem shows that any sequence of applicable cds applications, of same length as a sorting sequence, will sort such a permutation. Permutations that are not cds sortable can also be classified into different classes according to the number of failed cds sorting states achievable from this permutation. The fundamental structure coding this information about a given permutation was identified and is called the strategic pile of the permutation.

Context directed reversals:

Context directed reversals, denoted cdr, is the other permutation sorting operation postulated in [2] as used by the ciliate decryptome to accomplish micronuclear decryption. Again, not every signed permutation is cdr-sortable, and the cdr sortability of signed permutations have been characterized in several journal articles.

in this field can range over working in a laboratory with DNA from intermediate stages of micronuclear decryption, analyzing large volumes of recent micronuclear data to determine potential micronuclear precursors of genes, identifying the mathematical capabilities of the ciliate decryptome, the complexity of the decision and search problems that are routinely solved by the decryptome in performing the decryption, and more.



[1] Möllenbeck M, Zhou Y, Cavalcanti ARO, Jönsson F, Higgins BP, Chang W-J, et al. The Pathway to Detangle a Scrambled Gene. PLoS ONE 3(6) (2008):: e2330. doi:10.1371/journal.pone.0002330
[2] D. M. Prescott, A. Ehrenfeucht, G. Rozenberg, Template-guided recombination for IES elimination and unscrambling of genes in stichotrichous ciliates, Journal of Theoretical Biology 222 (2003) 323–330. doi:10.1016/S0022-5193(03)00037-7
[3] M. Nowacki, V. Vijayan, Y. Zhou, K. Schotanus, T.G. Doak and L.F. Landweber, RNA-mediated epigenetic programming of a genome-rearrangement pathway, Nature 451, 153-158 (10 January 2008) | doi:10.1038/nature06452
[4] L.F. Landweber and L. Kari, Universal molecular computation in ciliates, in Evolution as Computation (L.F. Landweber and E. Winfree eds), Springer-Verlag (2002), 257 - 274.

Data Bases