基因组重排问题的一个近似算法

An Approximation Algorithm for Genome Rearrangement Problem

分子生物学中基因无方向的反向基因组重排问题在数学上已被证明是一个NP困难问题.基于断点图的概念,给出一个时间复杂性为O(max{b3(π),nb(π)}),空间复杂性为O(n)的求其近似最优解的算法.其中n为基因组中基因个数,π=(π1,π2,…,πn)表示n个基因的一种排列,b(π)表示排列π中的断点数.数据实验的结果表明,该近似算法可以求得较好的结果.

In the paper we consider the problem of genome rearrangements of the unoriented gene by reversals in molecular biology.It is a NP-hard problem.Based on the concept of a breakpoint graph, we develop an approximation algorithm for problem.The algorithm has an O(max{b^3(π),nb(π)}) time complexity and an O(n) space complexity, where n is the number of genes in genome,π=(π_1,π_2,...,π_n) is a permutation of n genes and b(π) is the number of breakpoints in permutation π.The experiments show that in most cases, our approximation algorithm can find a better solution than the one obtained by the approximation algorithm of Kececioglu and Sankoff.