Algorithmic properties of ciliate sequence alignment

作者：Keil J Mark; Liu Jing; McQuillan Ian^*

来源：Theoretical Computer Science, 2010, 411(6): 919-925.

DOI：10.1016/j.tcs.2009.12.006

• Ciliates
• Gene descrambling
• Complexity theory
• Bioinformatics
• Computational modeling

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 Clue 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.

• 出版日期2010-2-6
• 单位Saskatoon; Saskatchewan