|
|||||
|
|
| 基因组重组问题的一个更快算法 | |
| 引用本文： | 亓兴勤,李国君,李曙光.基因组重组问题的一个更快算法[J].应用数学,2006,19(1):66-74. |
| 作者姓名： | 亓兴勤 李国君 李曙光 |
| 作者单位： | 1. 山东大学数学与系统科学学院,山东,济南,250100 2. 山东大学数学与系统科学学院,山东,济南,250100;中国科学院软件所,北京,100080 3. 山东大学数学与系统科学学院,山东,济南,250100;烟台大学数学与信息科学系,山东,烟台,264005 |
| 基金项目： | SupportedbytheNSFC(10271065,60373025) |
| 摘 要： | 寻找一个基因组(源基因组)转化成另一个基因组(目标基因组)所需最少数目移位和翻转的问题,称为基因组重组问题.此问题的“瓶颈”在于寻找源基因组的一个最优“联接”;若源基因组和目标基因组是“共尾”的,Hannenhalli和Pevzner给出一个O(n2)算法得到源基因组的一个最优“联接”,本文将此算法复杂性将低到O(n),其中n为基因组中所含基因的个数.从而由Eric.T和MarieFrance的结果得到求“共尾”标号基因组间重组序列的一个O(nnlogn)算法. |
| 关 键 词： | 翻转 移位 重组序列 基因组 |
| 文章编号： | 1001-9847(2006)01-0066-09 |
| 收稿时间： | 2004-12-21 |
| 修稿时间： | 2004年12月21 |
A Faster Algorithm for Genomic Sorting Problem |
|
| QI Xing-qin,LI Guo-jun,LI Shu-guang.A Faster Algorithm for Genomic Sorting Problem[J].Mathematica Applicata,2006,19(1):66-74. | |
| Authors: | QI Xing-qin LI Guo-jun LI Shu-guang |
| Institution: | 1. School of Mathematics and System Science, Shandong University, Jinan 250100, China ; 2. Institute of Software, Chinese Academy of Science, Beijing 100080, China ; 3. Department of Mathematics and Information Science, Yantai University, Yantai 264005, China |
| Abstract: | 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(n 3/2 logn). |
| Keywords: | Reversal Translocation Genomic sorting |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ | |