CAJ | 학술논문

寻找一个基因组(源基因组)转化成另一个基因组(目标基因组)所需最少数目移位和翻转的问题,称为基因组重组问题.此问题的"瓶颈"在于寻找源基因组的一个最优"联接";若源基因组和目标基因组是"共尾"的,Hannenhalli和Pevzner给出一个O(n2)算法得到源基因组的一个最优"联接",本文将此算法复杂性将低到O(n),其中n为基因组中所含基因的个数.从而由Eric.T和Marie-France的结果得到求"共尾"标号基因组间重组序列的一个O(n √nlogn)算法.
심조일개기인조(원기인조)전화성령일개기인조(목표기인조)소수최소수목이위화번전적문제,칭위기인조중조문제.차문제적"병경"재우심조원기인조적일개최우"련접";약원기인조화목표기인조시"공미"적,Hannenhalli화Pevzner급출일개O(n2)산법득도원기인조적일개최우"련접",본문장차산법복잡성장저도O(n),기중n위기인조중소함기인적개수.종이유Eric.T화Marie-France적결과득도구"공미"표호기인조간중조서렬적일개O(n √nlogn)산법.
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(n2) algorithm of Hannenhalli and Pevzner[1] ,so with a result of [5] we can compute the optimal genomic sequence between two co-tailed genomes in O(n3/2 √logn).