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

基因组重排问题的一个近似算法 An Approximation Algorithm for Genome Rearrangement Problem 陶玉敏 TAO Yu-min 1 2 first-author 莫忠息 MO Zhong-xi 1 2 刘扬 LIU Yang 1 2 任清华 REN Qing-hua 1 2 李素贞 LI Su-zhen 1 2 武汉大学数学与统计学院 武汉大学数学与统计学院 School of Mathematics and Statistics, Wuhan University School of Mathematics and Statistics, Wuhan University 武汉大学数学与统计学院,湖北,武汉,430072 武汉大学数学与统计学院,湖北,武汉,430072 分子生物学中基因无方向的反向基因组重排问题在数学上已被证明是一个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. 基因组重排 反向排序 断点图 近似算法 genome rearrangement sorting by reversals breakpoint graph approximation algorithm O212.2 国家自然科学基金（30170214）;武汉大学自强基金资助 2003-05-01 2021-04-01 5