Computational Efficiency of Intermolecular Gene Assembly

We investigate here the computational efficiency of gene rearrangement found in ciliates (unicellular organisms). We show how the so-called guided recombination systems, which model this gene rearrangement, can be used as problem solvers. Specifically, these systems can uniformly solveSAT with time complexity O(n ˙ m) for a Boolean formula of m clauses over n variables.