Your browser doesn't support javascript.
loading
A new 1.375-approximation algorithm for sorting by transpositions.
Silva, Luiz Augusto G; Kowada, Luis Antonio B; Rocco, Noraí Romeu; Walter, Maria Emília M T.
Afiliação
  • Silva LAG; Departmento de Ciência da Computação, Universidade de Brasília, Brasília, Brazil. laugustogarcia@gmail.com.
  • Kowada LAB; Instituto de Computação, Universidade Federal Fluminense, Niterói, Brazil.
  • Rocco NR; Departmento de Matemática, Universidade de Brasília, Brasília, Brazil.
  • Walter MEMT; Departmento de Ciência da Computação, Universidade de Brasília, Brasília, Brazil.
Algorithms Mol Biol ; 17(1): 1, 2022 Jan 15.
Article em En | MEDLINE | ID: mdl-35033127
BACKGROUND: SORTING BY TRANSPOSITIONS (SBT) is a classical problem in genome rearrangements. In 2012, SBT was proven to be [Formula: see text]-hard and the best approximation algorithm with a 1.375 ratio was proposed in 2006 by Elias and Hartman (EH algorithm). Their algorithm employs simplification, a technique used to transform an input permutation [Formula: see text] into a simple permutation [Formula: see text], presumably easier to handle with. The permutation [Formula: see text] is obtained by inserting new symbols into [Formula: see text] in a way that the lower bound of the transposition distance of [Formula: see text] is kept on [Formula: see text]. The simplification is guaranteed to keep the lower bound, not the transposition distance. A sequence of operations sorting [Formula: see text] can be mimicked to sort [Formula: see text]. RESULTS AND CONCLUSIONS: First, using an algebraic approach, we propose a new upper bound for the transposition distance, which holds for all [Formula: see text]. Next, motivated by a problem identified in the EH algorithm, which causes it, in scenarios involving how the input permutation is simplified, to require one extra transposition above the 1.375-approximation ratio, we propose a new approximation algorithm to solve SBT ensuring the 1.375-approximation ratio for all [Formula: see text]. We implemented our algorithm and EH's. Regarding the implementation of the EH algorithm, two other issues were identified and needed to be fixed. We tested both algorithms against all permutations of size n, [Formula: see text]. The results show that the EH algorithm exceeds the approximation ratio of 1.375 for permutations with a size greater than 7. The percentage of computed distances that are equal to transposition distance, computed by the implemented algorithms are also compared with others available in the literature. Finally, we investigate the performance of both implementations on longer permutations of maximum length 500. From the experiments, we conclude that maximum and the average distances computed by our algorithm are a little better than the ones computed by the EH algorithm and the running times of both algorithms are similar, despite the time complexity of our algorithm being higher.
Palavras-chave

Texto completo: 1 Coleções: 01-internacional Base de dados: MEDLINE Tipo de estudo: Prognostic_studies Idioma: En Revista: Algorithms Mol Biol Ano de publicação: 2022 Tipo de documento: Article País de afiliação: Brasil País de publicação: Reino Unido

Texto completo: 1 Coleções: 01-internacional Base de dados: MEDLINE Tipo de estudo: Prognostic_studies Idioma: En Revista: Algorithms Mol Biol Ano de publicação: 2022 Tipo de documento: Article País de afiliação: Brasil País de publicação: Reino Unido