Sorting by Prefix Reversals and Prefix Transpositions

Autor(es)

Dias, Zanoni ^[1] ; Dias, Ulisses ^[1]

Afiliação do(s) autor(es)

^[1] Univ Estadual Campinas, Inst Comp, Campinas, SP - Brazil

• Tipo de documento: Artigo Científico
• Fonte: DISCRETE APPLIED MATHEMATICS; v. 181, p. 78-89, JAN 30 2015.
• Citações Web of Science: 4

Resumo

In this paper, we present a new algorithm for the Sorting by Prefix Reversals and Prefix Transpositions Problem. The previous approximation algorithm was bounded by factor 3, and here we present an asymptotic 2-approximation algorithm. We consider theoretical and practical aspects in our analysis, and we show that our method is better than other approaches in both cases. (C) 2014 Elsevier B.V. All rights reserved. (AU)

• Processo FAPESP: 12/01584-3 - Problemas de Distâncias de Rearranjos de Genomas
• Beneficiário: Ulisses Martins Dias
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado