基因组重排的反转排序的近似算法

An Approximation Algorithm for Sorting by Reversals of Genome Rearrangement

本文主要研究基因无方向的基因组重排的反转排序问题.本文算法基于断点图的概念,给出一个时间复杂性为O(maxb3(π),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.Based on the concept of a breakpoint graph,we develop an approximation algorithm for problem.The algorithm has an O（maxb^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 better solution.