有向基因组移位排序算法的比较与评测

摘要：

基因组重组是生物进化的一种重要模式.虽然其生物过程非常复杂,但可归结为三种基本操作:移位、反转和转位.移位排序问题要求计算从一个基因组转化为另一个基因组所需的最少移位次数以及相应的移位序列.对于有向基因组移位排序问题,目前有三个多项式时间算法.已有算法在分析偶隔离带时漏掉一种情况,从而导致对某些特殊实例的计算结果是不正确的.通过给出这种特殊情况下找有效移位的方法,用Java语言将三个算法实现为移位排序软件-SG-BT,其计算效率优于现有的移位排序软件CTRD.通过随机产生的实验数据对三个算法的计算性能进行了测试,结果表明,三个算法的计算效率在基因数为0-70000时基本相同,在基因数为80000-100000时才表现出差异,并且随着基因数的增加差异越发明显.通过进一步实验,分析了产生上述结果的原因.最后,用SGBT对人和老鼠的部分基因进行排序并给出排序结果.

关键词：算法、基因组重组、移位

所属期刊栏目：36

分类号：TP301.6(计算技术、计算机技术)

在线出版日期：2008-12-17（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：30-34,77