Strings Modeling Gene Segment Arrangements

We use combinatorial analysis to understand DNA recombination processes that certain species of ciliates undergo during reproduction. In these species, during conjugation, a transcriptionally active macronucleus is destroyed and regenerated from a germline micronucleus where a majority of genes are fragmented in several (up to ~150) segments. These segments may be out of order or reversed, separated by so-called “junk” DNA which may be excised as cyclic molecules. An alignment of short repeat sequences, called pointers, at the endpoints of gene fragments, guides the recombination process so sequences of pointers can represent the arrangement of the gene fragments. Recent experimental data detected the existence of previously predicted cyclic molecules. The data also indicated that fragments of up to two genes may interleave or overlap around the cyclically excised DNA sections. We propose a combinatorial model to describe each linear arrangement of gene fragments neighboring cyclic molecule junctions as a sequence of pointers, and we call these sequences legal strings. We generate all possible legal strings with a computer algorithm and sort them into biologically equivalent classes. We describe a one-to-one correspondence between legal strings indicating gene fragment organization of two genes and paths in a rectangular lattice that start at (0,0) and end at (m,n) using only horizontal, vertical, and diagonal steps within a unit square. The number of such paths are within a square array corresponding to Delannoy numbers