Computational Aspects of Gene (Un)Scrambling in Ciliates

Ciliates, a very ancient group of organisms, have evolved extraordinary ways of organizing, manipulating, and replicating the DNA in their micronuclear genomes. The way that ciliates transform genes from their micronuclear (storage) form into their macronuclear (expression) form constitutes a very interesting case of “DNA computing in vivo”. In this paper we investigate in detail one aspect of this transformation, viz., gene (un)scrambling. In particular, we use the formal framework of pointer reduction systems to investigate the computational aspects of gene (un)scrambling.