Approximation Algorithms for Sorting λ-Permutations by λ-Operations
Open Access
- 1 June 2021
- journal article
- research article
- Published by MDPI AG in Algorithms
- Vol. 14 (6), 175
- https://doi.org/10.3390/a14060175
Abstract
Understanding how different two organisms are is one question addressed by the comparative genomics field. A well-accepted way to estimate the evolutionary distance between genomes of two organisms is finding the rearrangement distance, which is the smallest number of rearrangements needed to transform one genome into another. By representing genomes as permutations, one of them can be represented as the identity permutation, and, so, we reduce the problem of transforming one permutation into another to the problem of sorting a permutation using the minimum number of rearrangements. This work investigates the problems of sorting permutations using reversals and/or transpositions, with some additional restrictions of biological relevance. Given a value , the problem now is how to sort a -permutation, which is a permutation whose elements are less than positions away from their correct places (regarding the identity), by applying the minimum number of rearrangements. Each -rearrangement must have size, at most, , and, when applied to a -permutation, the result should also be a -permutation. We present algorithms with approximation factors of , , and for the problems of Sorting -Permutations by -Reversals, by -Transpositions, and by both operations.
Keywords
Funding Information
- Fundação de Amparo à Pesquisa do Estado de São Paulo (2013/08293-7, 2015/11937-9, 2017/12646-3, 2017/16246-0, and 2017/16871-1)
- Conselho Nacional de Desenvolvimento Científico e Tecnológico (400487/2016-0, 425340/2016-3, and 304380/2018-0)
- Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (001)
This publication has 19 references indexed in Scilit:
- Sorting by Transpositions Is DifficultSIAM Journal on Discrete Mathematics, 2012
- On sorting unsigned permutations by double-cut-and-joinsJournal of Combinatorial Optimization, 2010
- Sorting Signed Permutations by Inversions in O(nlogn) TimeJournal of Computational Biology, 2010
- An approximation algorithm for sorting by reversals and transpositionsJournal of Discrete Algorithms, 2008
- Sorting by Short SwapsJournal of Computational Biology, 2003
- Sorting Permutations by Reversals and Eulerian Cycle DecompositionsSIAM Journal on Discrete Mathematics, 1999
- Transforming cabbage into turnipJournal of the ACM, 1999
- Sorting by TranspositionsSIAM Journal on Discrete Mathematics, 1998
- Parametric genome rearrangementGene, 1996
- Genome Rearrangements and Sorting by ReversalsSIAM Journal on Computing, 1996