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 条

[11] UNITARY TORIC CLASSES, THE REALITY AND DESIRE DIAGRAM, AND SORTING BY TRANSPOSITIONS
Hausen, Rodrigo De A.
Faria, Luerbio
De Figueiredo, Celina M. H.
Kowada, Luis Antonio B.
[J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2010, 24 (03) : 792 - 807
[12] Kaplan H, 2003, LECT NOTES COMPUT SC, V2676, P170
[13] Kowada LAB, 2010, LECT N BIOINFORMAT, V6268, P35, DOI 10.1007/978-3-642-15060-9_4
[14] Lopes MP, 2011, LECT N BIOINFORMAT, V6832, P42, DOI 10.1007/978-3-642-22825-4_6
[15] GENE ORDER COMPARISONS FOR PHYLOGENETIC INFERENCE - EVOLUTION OF THE MITOCHONDRIAL GENOME
SANKOFF, D
LEDUC, G
ANTOINE, N
PAQUIN, B
LANG, BF
CEDERGREN, R
[J]. PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 1992, 89 (14) : 6575 - 6579

← 1 2 →