一种用于无符号易位距离的(1.5 + ε)近似算法。

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

作者信息

Cui Yun, Wang Lusheng, Zhu Daming, Liu Xiaowen

机构信息

Shangdong University, Ji'nan, P.R. China.

出版信息

IEEE/ACM Trans Comput Biol Bioinform. 2008 Jan-Mar;5(1):56-66. doi: 10.1109/TCBB.2007.70216.

DOI:10.1109/TCBB.2007.70216

PMID:18245875

Abstract

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 + epsilon)-approximation algorithm for computing unsigned translocation distance which improves upon the best known 1.75-ratio. The running time of our algorithm is O(n2 + (4/epsilon)1.5 square root log(4/epsilon )2(4/epsilon), where n is the total number of genes in the genome.

摘要

基因组重排是计算生物学和生物信息学中的一个重要领域。易位操作是基因组重排中常用的操作之一。已证明计算无符号易位距离是NP难问题。在本文中，我们提出了一种用于计算无符号易位距离的(1.5 + ε)近似算法，该算法改进了已知的最佳1.75比率。我们算法的运行时间为O(n2 + (4/ε)1.5平方根log(4/ε)2(4/ε)，其中n是基因组中基因的总数。