Gene Assembly in Ciliates

Ciliates are single-cell organisms that have two functionally different nuclei, one called micronucleus and the other called macronucleus (both of which can occur in various multiplicities). At some stage in sexual reproduction a micronucleus is transformed into a macronucleus in a process called gene assembly. This is the most involved DNA processing in living organisms known today. The reason that gene assembly is so involved is that the genome of the micronucleus may be dramatically different from the genome of the macronucleus --- this is particularly true in the stichotrichs group of ciliates. The investigation of gene assembly turns out to be very exciting from both biological and computational points of view.

The following monograph gives an accessible account of both the biology and the formal analysis of the gene assembly process.

A. Ehrenfeucht, T. Harju, I. Petre, D.M. Prescott, and G. Rozenberg Computation in Living Cells -- Gene Assembly in Ciliates Springer Verlag, 2004

Below are selected publications within NWO project 635.100.006 "VIEWS".

Abstract. Gene assembly in ciliates is one of the most involved DNA processings going on in any organism. This process transforms one nucleus (the micronucleus) into another functionally different nucleus (the macronucleus). We continue the development of the theoretical models of gene assembly, and in particular we demonstrate the use of the concept of the breakpoint graph, known from another branch of DNA transformation research. More specifically: (1) we characterize the intermediate gene patterns that can occur during the transformation of a given micronuclear gene pattern to its macronuclear form; (2) we determine the number of applications of the loop recombination operation (the most basic of the three molecular operations that accomplish gene assembly) needed in this transformation; (3) we generalize previous results (and give elegant alternatives for some proofs) concerning characterizations of the micronuclear gene patterns that can be assembled using a specific subset of the three molecular operations.

Abstract. The gene assembly process in ciliates (single-cell organisms) is interesting from both the biological and computational point of view. This paper studies the computational nature of the gene assembly process. Motivated by the breakpoint graph known from another branch of DNA transformation research, we introduce the reduction graph as a tool for the study of this process, and illustrate its usefulness by proving a number of properties of gene assembly.

Abstract. The concept of breakpoint graph, known from the theory of sorting by reversal, has been successfully applied in the theory of gene assembly in ciliates. We further investigate its usage for gene assembly, and show that the graph allows for an efficient characterization of the possible orders of loop recombination operations (one of the three types of molecular operations that accomplish gene assembly) for a given gene during gene assembly. The characterization is based on spanning trees within a graph built upon the connected components in the breakpoint graph. We work in the abstract and more general setting of so-called legal strings.