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