A 1.375-approximation algorithm for sorting by transpositions

被引：109

作者：

Elias, Isaac ^{[1
]}

Hartman, Tzvika

机构：

[1] Royal Inst Technol, Dept Numer Anal & Comp Sci, Stockholm, Sweden

[2] Bar Ilan Univ, Dept Comp Sci, IL-52900 Ramat Gan, Israel

来源：

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS | 2006年 / 3卷 / 04期

关键词：

computational biology; genome rearrangements; sorting permutations by transpositions;

D O I：

10.1109/TCBB.2006.44

中图分类号：

Q5 [生物化学];

学科分类号：

071010 ; 081704 ;

摘要：

Sorting permutations by transpositions is an important problem in genome rearrangements. A transposition is a rearrangement operation in which a segment is cut out of the permutation and pasted in a different location. The complexity of this problem is still open and it has been a 10-year-old open problem to improve the best known 1.5-approximation algorithm. In this paper, we provide a 1.375-approximation algorithm for sorting by transpositions. The algorithm is based on a new upper bound on the diameter of 3-permutations. In addition, we present some new results regarding the transposition diameter: We improve the lower bound for the transposition diameter of the symmetric group and determine the exact transposition diameter of simple permutations.

引用

页码：369 / 379

页数：11

共 25 条

[1] EVERY PLANAR MAP IS 4 COLORABLE .1. DISCHARGING [J].

APPEL, K ;

HAKEN, W .

ILLINOIS JOURNAL OF MATHEMATICS, 1977, 21 (03) :429-490

[2] A linear-time algorithm for computing inversion distance between signed permutations with an experimental study [J].

Bader, DA ;

Moret, BME ;

Yan, M .

JOURNAL OF COMPUTATIONAL BIOLOGY, 2001, 8 (05) :483-491

[3] Genome rearrangements and sorting by reversals [J].

Bafna, V ;

Pevzner, PA .

SIAM JOURNAL ON COMPUTING, 1996, 25 (02) :272-289

[4] Sorting by transpositions [J].

Bafna, V ;

Pevzner, PA .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 1998, 11 (02) :224-240

[5] A very elementary presentation of the Hannenhalli-Pevzner theory [J].

Bergeron, A .

DISCRETE APPLIED MATHEMATICS, 2005, 146 (02) :134-145

[6]

Berman P, 2002, LECT NOTES COMPUT SC, V2461, P200

[7] Sorting permutations by reversals and Eulerian cycle decompositions [J].

Caprara, A .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 1999, 12 (01) :91-110

[8]

Christie D. A., 1999, THESIS U GLASGOW

[9]

ELIAS I, 2005, P 5 WORKSH ALG BIOIN, P204

[10] Sorting a bridge hand [J].

Eriksson, H ;

Eriksson, K ;

Karlander, J ;

Svensson, L ;

Wästlund, J .

DISCRETE MATHEMATICS, 2001, 241 (1-3) :289-300

← 1 2 3 →