Name
Abstract | ||
|---|---|---|
In comparative genomics, rearrangements are mutations that affect a stretch of DNA sequences. Reversals and transpositions are well-known rearrangements, and each has a vast literature. The reversal and transposition distance, that is, the minimum number of reversals and transpositions needed to transform one genome into another is a relevant evolutionary distance. The problem of computing this distance when genomes are represented by permutations was proposed >20 years ago and received the name of sorting by reversals and transpositions problem. It has been the focus of a number of studies, but the computational complexity has remained open until now. We hereby solve this question and prove that it is NP-hard no matter whether genomes are represented by signed or unsigned permutations. In addition, we prove that a usual generalization of this problem, which assigns weights w(rho) for reversals and w(tau) for transpositions, is also NP-hard as long as w(tau)/w(rho) <= 1.5 for both signed and unsigned permutations. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1089/cmb.2019.0078 | JOURNAL OF COMPUTATIONAL BIOLOGY |
Keywords | Field | DocType |
genome rearrangements,reversals and transpositions,sorting problems,weighted operations | Sorting,Comparative genomics,Artificial intelligence,DNA sequencing,Computational biology,Machine learning,Mathematics | Journal |
Volume | Issue | ISSN |
26.0 | 11 | 1066-5277 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andre Rodrigues Oliveira | 1 | 0 | 6.76 |
| Klairton Lima Brito | 2 | 0 | 1.01 |
| Ulisses Dias | 3 | 41 | 13.23 |
| Zanoni Dias | 4 | 262 | 44.40 |