| 标号基因组间重组距离的一个线性时间算法 |
| |
| 引用本文： | 亓兴勤,王骁力,李国君.标号基因组间重组距离的一个线性时间算法[J].山东大学学报(理学版),2005,40(1):22-28,34. |
| |
| 作者姓名： | 亓兴勤 王骁力 李国君 |
| |
| 作者单位： | 1. 山东大学,数学与系统科学学院,山东,济南,250100
2. 山东大学,数学与系统科学学院,山东,济南,250100;南阳师范学院数学系,河南,南阳,473061 |
| |
| 基金项目： | 国家自然科学基金资助项目 (10 2 710 65，60 3 73 0 2 5 ) |
| |
| 摘 要： | 考虑的基因组的进化基于两种形式：基因组中染色体之间的移位(translocation)和染色体内部的翻转(reversal)．研究了标号基因组间的重组问题：求一个标号基因组进化成另一个标号基因组所需最少数目的移位和翻转，这个数目叫做重组距离．给出了求“共尾”标号基因组间重组距离的一个线性时间算法，从而改进了Hannenhalli和Pevzner的O(n^2)算法，其中n是基因组中基因的个数．
|
| 关 键 词： | 翻转 移位 重组距离 断点图 交叠图 |
| 文章编号： | 1671-9352(2005)01-0022-07 |
A Linear-time algorithm for computing genomic distance between signed genomes |
| |
| QI Xing-qin,WANG Xiao-li,LI Guo-jun.A Linear-time algorithm for computing genomic distance between signed genomes[J].Journal of Shandong University,2005,40(1):22-28,34. |
| |
| Authors: | QI Xing-qin WANG Xiao-li LI Guo-jun |
| |
| Institution: | QI Xing qin 1,WANG Xiao li 1,2 & LI Guo jun 1 |
| |
| Abstract: | The rearrangements between genomes considered here are translocations and reversals. The genomic sorting problem is to find a sequence of reversals and translocations with minimum length. By this sequence, one genome can be transformed into another genome. The minimum number is called genomic distance. A linear time algorithm is given for computing the genomic distance between two signed co tailed genomes so that it improves the O(n 2) algorithm of Hannenhalli and Pevzner wherein n is the number of genes in the genome. |
| |
| Keywords: | reversal translocation genomic distance cycle graph interleaving graph |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
