Name
Title | ||
|---|---|---|
Approximation Algorithms for Sorting Permutations by Length-Weighted Short Rearrangements. |
Abstract | ||
|---|---|---|
Genome rearrangements are events that affect large portions of a genome. When using the rearrangement distance to compare two genomes, one wants to find a minimum cost sequence of rearrangements that transforms one into another. Since we represent genomes as permutations, we can reduce this problem to the problem of sorting a permutation with a minimum cost sequence of rearrangements. In the traditional approach, we consider that all rearrangements are equally likely to occur and we set a unitary cost for all rearrangements. However, there are two variations of the problem motivated by the observation that rearrangements involving large segments of a genome rarely occur. The first variation adds a restriction to the rearrangement's length. The second variation uses a cost function based on the rearrangement's length. In this work, we present approximation algorithms for five problems combining both variations, that is, problems with a length-limit restriction and a cost function based on the rearrangement's length. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1016/j.entcs.2019.08.004 | Electronic Notes in Theoretical Computer Science |
Keywords | Field | DocType |
Genome Rearrangements,Approximation Algorithms,Sorting Permutations | Genome,First variation,Discrete mathematics,Approximation algorithm,Computer science,Permutation,Sorting,Unitary state | Journal |
Volume | ISSN | Citations |
346 | 1571-0661 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alexsandro Oliveira Alexandrino | 1 | 0 | 3.38 |
| Guilherme Henrique Santos Miranda | 2 | 0 | 1.69 |
| Carla Negri Lintzmayer | 3 | 26 | 9.14 |
| Zanoni Dias | 4 | 262 | 44.40 |