On the complexity of unsigned translocation distance

被引：21

作者：

Zhu, DM

Wang, LS ^{[1
]}

机构：

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

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

来源：

THEORETICAL COMPUTER SCIENCE | 2006年 / 352卷 / 1-3期

基金：

中国国家自然科学基金;

关键词：

unsigned translocation; NP-hardness; inapproximability;

D O I：

10.1016/j.tcs.2005.09.078

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Translocation is one of the basic operations for genome rearrangement. Translocation distance is the minimum number of translocations required to transform one genome into the other. In this paper, we show that computing the translocation distance for unsigned genomes is NP-hard. Moreover, we show that approximating the translocation distance for unsigned genomes within ratio 1.00017 is NP-hard. (c) 2005 Elsevier B.V. All rights reserved.

引用

页码：322 / 328

页数：7

共 16 条

[1] Genome rearrangements and sorting by reversals
Bafna, V
Pevzner, PA
[J]. SIAM JOURNAL ON COMPUTING, 1996, 25 (02) : 272 - 289
[2] BAFNA V, 1995, MOL BIOL EVOL, V12, P239
[3] BERMAN P, 1998, 65 ECCC U TRIER
[4] Caprara A., 1997, P 1 ANN INT C COMP M, P75, DOI DOI 10.1145/267521.267531
[5] GENOME SEQUENCE COMPARISON AND SCENARIOS FOR GENE REARRANGEMENTS - A TEST-CASE
HANNENHALLI, S
CHAPPEY, C
KOONIN, EV
PEVZNER, PA
[J]. GENOMICS, 1995, 30 (02) : 299 - 311
[6] 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
[7] Hannenhalli S, 1995, LECT NOTES COMPUT SC, V1000, P184
[8] Hannenhalli S, 1996, PROCEEDINGS OF THE SEVENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P304
[9] Polynomial-time algorithm for computing translocation distance between genomes
Hannenhalli, S
[J]. DISCRETE APPLIED MATHEMATICS, 1996, 71 (1-3) : 137 - 151
[10] KAPLAN H, 1997, P 8 ACM SIAM S DISCR

← 1 2 →