A (1.5+ε)-approximation algorithm for unsigned translocation distance

被引：12

作者：

Cui, Yun ^{[1
]}

Wang, Lusheng ^{[2
]}

Zhu, Daming ^{[1
]}

Liu, Xiaowen ^{[2
]}

机构：

[1] Shandong Univ, Sch Comp Sci & Technol, Jinan, Peoples R China

[2] City Univ Hong Kong, Dept Comp Sci, Kowloon, Hong Kong, Peoples R China

来源：

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS | 2008年 / 5卷 / 01期

基金：

中国国家自然科学基金;

关键词：

genome rearrangement; unsigned translocation; approximation algorithms;

D O I：

10.1109/TCBB.2007.70216

中图分类号：

Q5 [生物化学];

学科分类号：

071010 ; 081704 ;

摘要：

Genome rearrangement is an important area in computational biology and bioinformatics. The translocation operation is one of the popular operations for genome rearrangement. It was proved that computing the unsigned translocation distance is NP-hard. In this paper, we present a (1.5 + E)-approximation algorithm for computing the unsigned translocation distance that 4), improves upon the best known 1.75-ratio. The runtime of our algorithm is O(n(2) + (4/epsilon)(1.5) root log(4/epsilon)2(4/epsilon)), where n is the total number of genes in the genome.

引用

页码：56 / 66

页数：11

共 12 条

[1] On sorting by translocations
Bergeron, A
Mixtacki, J
Stoye, J
[J]. JOURNAL OF COMPUTATIONAL BIOLOGY, 2006, 13 (02) : 567 - 578
[2] A very elementary presentation of the Hannenhalli-Pevzner theory
Bergeron, A
[J]. DISCRETE APPLIED MATHEMATICS, 2005, 146 (02) : 134 - 145
[3] Common intervals and sorting by reversals: a marriage of necessity
Bergeron, A
Heber, S
Stoye, J
[J]. BIOINFORMATICS, 2002, 18 : S54 - S63
[4] CUI Y, 2005, P 16 INT S ALG COMP, P392
[5] CUI Y, IN PRESS J COMPUTER
[6] Hannenhalli S., 1995, Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, P178, DOI 10.1145/225058.225112
[7] HANNENHALLI S, 1995, P 6 ANN S COMB PATT, P162
[8] KECECIOGLU JD, 1995, PROCEEDINGS OF THE SIXTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P604
[9] Ozery-Flato M., 2006, P 17 ANN S COMB PATT, P258
[10] Plummer MichaelD., 1986, Matching theory, V29

← 1 2 →