Name
Abstract | ||
|---|---|---|
Estimating the evolutionary distance between genomes of two organisms is a challenging task for Computational Biology. One of the most well-accepted ways to do this is to consider the size of the smallest sequence of rearrangement events required to transform one genome into another, characterizing the rearrangement distance problem. Computationally, genomes can be represented as permutations of integers and, with this, the problem can be reduced to transforming a permutation into the identity with the minimum number of operations (sorting the permutation). These operations are given by a rearrangement model and they affect segments of a genome in different ways. Among the most common models are those that allow only reversals, only transpositions, or both of them. In this paper we study sorting permutations when a restriction of biological relevance is added: the size of the rearrangements should be at most a given value lambda. Some results are known for lambda = 2 and lambda = 3 but, to the best of our knowledge, there are no results for lambda > 3. We consider rearrangement models that allow reversals and/or transpositions for sorting unsigned permutations given any value of lambda. We present approximation algorithms for 3 such problems, where the approximation factors depend on lambda and/or on the size of the permutations. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1007/978-3-319-91938-6_7 | ALGORITHMS FOR COMPUTATIONAL BIOLOGY (ALCOB 2018) |
Keywords | DocType | Volume |
Genome rearrangement,Sorting permutations,Reversals,Transpositions,Computational Biology | Conference | 10849 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Guilherme Henrique Santos Miranda | 1 | 0 | 1.69 |
| Carla Negri Lintzmayer | 2 | 26 | 9.14 |
| Zanoni Dias | 3 | 262 | 44.40 |