应用数学
應用數學
응용수학
MATHEMATICA APPLICATA
2006年
1期
66-74
,共9页
翻转%移位%重组序列%基因组
翻轉%移位%重組序列%基因組
번전%이위%중조서렬%기인조
Reversal%Translocation%Genomic sorting
寻找一个基因组(源基因组)转化成另一个基因组(目标基因组)所需最少数目移位和翻转的问题,称为基因组重组问题.此问题的"瓶颈"在于寻找源基因组的一个最优"联接";若源基因组和目标基因组是"共尾"的,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)算法.
심조일개기인조(원기인조)전화성령일개기인조(목표기인조)소수최소수목이위화번전적문제,칭위기인조중조문제.차문제적"병경"재우심조원기인조적일개최우"련접";약원기인조화목표기인조시"공미"적,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).