Busca avançada
Ano de início
Entree


A 1.375-Approximation Algorithm for Sorting by Transpositions with Faster Running Time

Texto completo
Autor(es):
Alexandrino, Alexsandro Oliveira ; Brito, Klairton Lima ; Oliveira, Andre Rodrigues ; Dias, Ulisses ; Dias, Zanoni ; Scherer, NM ; DeMelo-Minardi, RC
Número total de Autores: 7
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