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

A Faster Algorithm for Genomic Sorting Problem

寻找一个基因组(源基因组)转化成另一个基因组(目标基因组)所需最少数目移位和翻转的问题,称为基因组重组问题.此问题的“瓶颈”在于寻找源基因组的一个最优“联接”;若源基因组和目标基因组是“共尾”的,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）.