Name
Abstract | ||
|---|---|---|
One of the main challenges in Computational Biology is to find the evolutionary distance between two organisms. In the field of comparative genomics, one way to estimate such distance is to find a minimum cost sequence of rearrangements (large scale mutations) needed to transform one genome into another, which is called the rearrangement distance. In the past decades, these problems were studied considering many types of rearrangements (such as reversals, transpositions, transreversals, and revrevs) and considering the same weight for all rearrangements, or different weights depending on the types of rearrangements. The complexity of the problems involving reversals, transpositions, and both rearrangements is known, even though the hardness proof for the problem combining reversals and transpositions was recently given. In this paper, we enhance the knowledge for these problems by proving that models involving transpositions alongside reversals, transreversals, and revrevs are NP-hard, considering weights w(1) for reversals and w(2) for the other rearrangements such that w(2)/w(1) <= 1.5. In addition, we address a cost function related to the number of fragmentations caused by a rearrangement, proving that the problem of finding a minimum cost sorting sequence, considering the fragmentation cost function with some restrictions, is NP-hard for transpositions and the combination of reversals and transpositions. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.3897/jucs.2020.057 | JOURNAL OF UNIVERSAL COMPUTER SCIENCE |
Keywords | DocType | Volume |
Genome Rearrangements, Weighted Rearrangements, Transpositions | Journal | 26 |
Issue | ISSN | Citations |
9 | 0948-695X | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alexsandro Oliveira Alexandrino | 1 | 0 | 3.38 |
| Andre Rodrigues Oliveira | 2 | 0 | 6.76 |
| Ulisses Dias | 3 | 41 | 13.23 |
| Zanoni Dias | 4 | 262 | 44.40 |