基因组重组问题的一个更快算法(英文)  

A Faster Algorithm for Genomic Sorting Problem

作　　者：亓兴勤[1] 李国君[1] 李曙光[1] 

机构地区：[1]山东大学数学与系统科学学院,山东济南250100

出　　处：《应用数学》2006年第1期66-74,共9页Mathematica Applicata

基　　金：SupportedbytheNSFC(10271065,60373025)

摘　　要：寻找一个基因组(源基因组)转化成另一个基因组(目标基因组)所需最少数目移位和翻转的问题,称为基因组重组问题.此问题的“瓶颈”在于寻找源基因组的一个最优“联接”;若源基因组和目标基因组是“共尾”的,Hannenhalli和Pevzner给出一个O(n2)算法得到源基因组的一个最优“联接”,本文将此算法复杂性将低到O(n),其中n为基因组中所含基因的个数.从而由Eric.T和MarieFrance的结果得到求“共尾”标号基因组间重组序列的一个O(nnlogn)算法.The genomic sorting problem is to find a minimum length sequence of rearrangements （reversals or translocations） by which source genome can be transformed into target genome. In this paper,we give a linear-time algorithm to get an optimal concatenate of the source genome when the source genome and the target genome are co-tailed which improves the O（n^2） algorithm of Hannenhalli and Pevzner , so with a result of [5] we can compute the optimal genomic sequence between two co-railed genomes in O（n^3/2 √logn）.

关 键 词：翻转 移位 重组序列 基因组 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]