On the 1.375-Approximation Algorithm for Sorting by Transpositions in O(n log n) Time

被引：0

作者：

Cunha, Luis Felipe I. ^{[1
]}

Kowada, Luis Antonio B. ^{[2
]}

Hausen, Rodrigo de A. ^{[3
]}

de Figueiredo, Celina M. H. ^{[1
]}

机构：

[1] Univ Fed Rio de Janeiro, BR-21941 Rio De Janeiro, Brazil

[2] Univ Fed Fluminense, Niteroi, RJ, Brazil

[3] Univ Fed ABC, Santo Andre, Brazil

来源：

ADVANCES IN BIOINFORMATICS AND COMPUTATIONAL BIOLOGY | 2013年 / 8213卷

关键词：

comparative genomics; genome rearrangement; sorting by transpositions; approximation algorithms; SIGNED PERMUTATIONS; REVERSALS;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

Sorting by Transpositions is an NP-hard problem. Elias and Hartman proposed a 1.375-approximation algorithm, the best ratio so far, which runs in O(n(2)) time. Firoz et al. proposed an improvement to the running time, from O(n(2)) down to O(n log n), using Feng and Zhu's permutation trees. 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.

引用

页码：126 / 135

页数：10

共 15 条

[1] Sorting by transpositions
Bafna, V
Pevzner, PA
[J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 1998, 11 (02) : 224 - 240
[2] SORTING BY TRANSPOSITIONS IS DIFFICULT
Bulteau, Laurent
Fertin, Guillaume
Rusu, Irena
[J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2012, 26 (03) : 1148 - 1180
[3] Cunha L.F.I., 2012, LECT NOTES COMPUT SC, V7409, P1
[4] CUNHA L.M., 2013, THESIS
[5] Dias U., 2010, P 1 ACM INT C BIOINF, P334
[6] A 1.375-approximation algorithm for sorting by transpositions
Elias, Isaac
Hartman, Tzvika
[J]. IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS, 2006, 3 (04) : 369 - 379
[7] Feng J., 2007, ACM T ALGORITHMS, V3, P1549
[8] The 1.375 Approximation Algorithm for Sorting by Transpositions Can Run in O(n log n) Time
Firoz, Jesun Sahariar
Hasan, Masud
Khan, Ashik Zinnat
Rahman, M. Sohel
[J]. JOURNAL OF COMPUTATIONAL BIOLOGY, 2011, 18 (08) : 1007 - 1011
[9] Transforming cabbage into turnip: Polynomial algorithm for sorting signed permutations by reversals
Hannenhalli, S
Pevzner, PA
[J]. JOURNAL OF THE ACM, 1999, 46 (01) : 1 - 27
[10] A simpler and faster 1.5-approximation algorithm for sorting by transpositions
Hartman, T
Shamir, R
[J]. INFORMATION AND COMPUTATION, 2006, 204 (02) : 275 - 290

← 1 2 →