Autor(es)

Alexandrino, Alexsandro Oliveira ; Brito, Klairton Lima ; Oliveira, Andre Rodrigues ; Dias, Ulisses ; Dias, Zanoni ; Scherer, NM ; DeMelo-Minardi, RC

• Tipo de documento: Artigo Científico
• Fonte: ADVANCES IN BIOINFORMATICS AND COMPUTATIONAL BIOLOGY, BSB 2022; v. 13523, p. 11-pg., 2022-01-01.

Resumo

Sorting Permutations by Transpositions is a famous problem in the Computational Biology field. This problem is NP-Hard, and the best approximation algorithm, proposed by Elias and Hartman in 2006, has an approximation factor of 1.375. Since then, several researchers have proposed modifications to this algorithm to reduce the time complexity. More recently, researchers showed that the algorithm proposed by Elias and Hartman might need one more operation above the approximation ratio and presented a new 1.375-approximation algorithm using an algebraic approach that corrected this issue. This algorithm runs in O(n(6)) time. In this paper, we present an efficient way to fix Elias and Hartman algorithm that runs in O(n(5)). By comparing the three approximation algorithms with all permutations of size n <= 12, we also show that our algorithm finds the exact distance in more instances than the previous two algorithms. (AU)

• Processo FAPESP: 19/27331-3 - Problemas de ordenação por rearranjos de genomas
• Beneficiário: André Rodrigues Oliveira
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• Processo FAPESP: 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural
• Beneficiário: Flávio Keidi Miyazawa
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 13/08293-7 - CECC - Centro de Engenharia e Ciências Computacionais
• Beneficiário: Munir Salomao Skaf
• Modalidade de apoio: Auxílio à Pesquisa - Centros de Pesquisa, Inovação e Difusão - CEPIDs