A Faster 1.375-Approximation Algorithm for Sorting by Transpositions

作者：Cunha Luis Felipe I^*; Kowada Luis Antonio B; Hausen Rodrigo De A; De Figueiredo Celina M H

来源：Journal of Computational Biology, 2015, 22(11): 1044-1056.

DOI：10.1089/cmb.2014.0298

• approximation algorithms
• genome rearrangement
• sorting by transpositions

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 O(n(3/2)root log n) 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.

• 出版日期2015-11-1