Title | ||
---|---|---|
Approximation Algorithms for Sorting Permutations by Fragmentation-Weighted Operations. |
Abstract | ||
---|---|---|
Rearrangements are mutations that affect large portions of a genome. When comparing two genomes, one wants to find a sequence of rearrangements that transforms one into another. When we use permutations to represent the genomes, this reduces to the problem of sorting a permutation using some sequence of rearrangements. The traditional approach is to find a sequence of minimum length. However, some studies show that some rearrangements are more likely to disturb an individual, and so a weighted approach is closer to the real evolutionary process. Most weighted approaches consider that the cost of a rearrangement can be related to its type or to the number of elements affected by it. This work introduces a new type of cost function, which is related to the amount of fragmentation caused by a rearrangement. We present some results about lower and upper bounds for the fragmentation-weighted problems and the relation between the unweighted and the fragmentation-weighted approach. Our main results are 2-approximation algorithms for 5 versions of the fragmentation-weighted problem involving reversals and transpositions events. |
Year | DOI | Venue |
---|---|---|
2018 | 10.1007/978-3-319-91938-6_5 | ALGORITHMS FOR COMPUTATIONAL BIOLOGY (ALCOB 2018) |
Keywords | DocType | Volume |
Genome rearrangements,Sorting permutations,Approximation algorithms | Conference | 10849 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
0 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Alexsandro Oliveira Alexandrino | 1 | 0 | 3.38 |
Carla Negri Lintzmayer | 2 | 26 | 9.14 |
Zanoni Dias | 3 | 262 | 44.40 |