Context Directed Reversals on Permutations and Graphs

Efficient Information Processing is fundamental to activities stretching from genome maintenance to data management. This project is analyzing the nature of and unusual efficiency in sorting information, of an elaborate genome maintenance system. Single cell organisms called ciliates host an encrypted copy of their genome in a micronucleus. Their genome maintenance system often replaces the current functional genome by decrypting an encrypted copy.

Decryption is performed through permutation sorting, using context directed reversals (cdr) and context directed block swaps (cds). The decryption mechanism has computational power and is programmable, giving compelling reasons to examine its mathematical properties. Generalizing several prior results, we identify the set of all signed permutations that are sortable by applications of cdr and cds. The methods used in this investigation are from the mathematical fields of algebra, combinatorics, graph theory and low dimensional topology.