Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1016/j.tcs.2009.12.006 | Theoretical Computer Science |
Keywords | DocType | Volume |
Ciliates,Gene descrambling,Complexity theory,Bioinformatics,Computational modeling | Journal | 411 |
Issue | ISSN | Citations |
6 | 0304-3975 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| J. Mark Keil | 1 | 613 | 66.64 |
| Jing Liu | 2 | 0 | 0.34 |
| Ian McQuillan | 3 | 97 | 24.72 |