title: A faster 1.375-approximation algorithm for sorting by transpositions.
abstract: Sorting by Transpositions is an NP-hard problem for which several polynomial-time approximation algorithms have been developed. Hartman and Shamir (2006) developed a 1.5-approximation [Formula: see text] algorithm, whose running time was improved to O(nlogn) by Feng and Zhu (2007) with a data structure they defined, the permutation tree. Elias and Hartman (2006) developed a 1.375-approximation O(n(2)) algorithm, and Firoz et al. (2011) claimed an improvement to the running time, from O(n(2)) to O(nlogn), by using the permutation tree. We provide counter-examples to the correctness of Firoz et al.'s strategy, showing that it is not possible to reach a component by sufficient extensions using the method proposed by them. In addition, we propose a 1.375-approximation algorithm, modifying Elias and Hartman's approach with the use of permutation trees and achieving O(nlogn) time.
authors.affiliation: 1 COPPE - Programa de Engenharia de Sistemas e Computação, Universidade Federal do Rio de Janeiro , Rio de Janeiro, Brazil .
authors.forename: Luís Felipe I
authors.initials: LF
authors.lastname: Cunha
authors.affiliation: 2 Instituto de Computação, Universidade Federal Fluminense , Rio de Janeiro, Brazil .
authors.forename: Luis Antonio B
authors.initials: LA
authors.lastname: Kowada
authors.affiliation: 3 Centro de Matemática, Computação e Cognição, Universidade Federal do ABC , São Paulo, Brazil .
authors.forename: Rodrigo de A
authors.initials: Rde A
authors.lastname: Hausen
authors.affiliation: 1 COPPE - Programa de Engenharia de Sistemas e Computação, Universidade Federal do Rio de Janeiro , Rio de Janeiro, Brazil .
authors.forename: Celina M H
authors.initials: CM
authors.lastname: de Figueiredo
mesh_terms: D000465:Algorithms; D019295:Computational Biology; D015321:Gene Rearrangement; D008957:Models, Genetic; D017422:Sequence Analysis, DNA
keywords: approximation algorithms; genome rearrangement; sorting by transpositions