Algorithmic properties of ciliate sequence alignment

We study the problem of optimally partitioning scrambled genes of stichotrichous ciliates into their relevant functional segments, and of aligning scrambled genes with non-scrambled genes. This problem is significantly more difficult than traditional sequence alignment due to the patterns that occur in the scrambled genes. Here, a formal model is created to capture this problem. Then, the inherent complexity of this problem is discussed using the model. We determine that the problem of determining if there is a solution (an alignment) which achieves some minimum score is NP-complete.