基于基因组移位排序算法的改进和评测

《基于基因组移位排序算法的改进和评测》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号丁单位代码学号功第另寒硕士学位论文论文题目基因组移位排序算法的改进和评测作者姓名尹晓专业计算机软件与理论指导教师姓名专业技术职务朱大铭教授年月日山东大学硕士学位论文目录摘，要………………，…工工第章绪论……，……、……背景介，，··，绍………………移位·……主要研究成果……，……第章有符号移位排序算法……相关符号和定义……移位距离的计算……移位序列的计算……、……不存在可行移位……，……、……，…，选择的可行移位不产生新的最小子排列也不产生偶隔离带…选择的可行移位会产生新的最小子排列……可行移位没有产生新的最小

2、子排列，但产生了偶隔离带……修正后的移位排序算法……对三个移位排序多项式算法的综合讨论……复杂度为勺的算法……复杂度为的算法……复杂度为的算法……第章有向基因组移位排序快速算法的实现评测……实现有向，基因组移位排序算法的数据结构…………断点图节点的实现……辅助数组的实现……可行灰边集合的实现……，……节点的实现……，……山东大学硕士学位论文结构的实现……算法理论描述……基因组转换条件判断位置计算工……建立灰边连接……保存可行灰边叩……存储所有最小子排列……三种移位操作……，·，寻找可用灰边…………匕门︻匕口︹八民了，

3、确定，以及………缩小最小子排列的范围，……寻找偶隔离带……寻找有效可行灰边…，……基因组变换……，……实验……，……程序……准备工作……，数据……分析……第章结论与展望参考文献二，……，···········致谢二……攻读硕士学位期间发表的学术论文山东大学硕士学位论文摘要基，因组重组问题是计算生物学中的常见问题基因组重组算法对分子生物学中生物进化的研究具有重要意义。早在六十年前，玲和发表，了一篇重要论文证明了两种不同物种和的染色体基因序列可以通过基因组的次反转操作相互转换。染色体由基因组成，基因组是染色体组成的集合。

4、基因组重组是微生物、植物、动物进化的一种重要模式。虽然基因组重组过程非常复杂，但根据基因重新排列的方式最终可将其归结为几种基本操作。其中，变异过程中的主要操作为反转、移位和转位。移位是哺乳动物印进化过程中最常见的基因组重组操作之一。移位操作将基因组中的两条染色体各自断为两段并相互交换其中的一段，形成两条新的染色体。基因组排序问题可描，述为给定两个基因组计算出从一个基因组转化到另外一个基因组所需操作的最少次数以及对应的最短重组序列。本论文主要讨论基因组的移位排序算法及其实现过程。对于该问题，与首先给出近似性能，比为的多

5、项式时间近似算法并进一步给出近似性能，比为的移位与反转同时存在的计算重组距离的近似算法最终在年由给出复杂度为口矿的移位排序的多项式算法。在此基，，、。，、础上年朱大铭马绍汉将其复杂度降为。扩年王鲁生，朱大铭又进一步将其复杂度降到了。矛这也是目前世界上最快的移位排序算法。本文对该问题的研究，首先发现了原有算法中存在的错误。原有的移位排序算法中均未考虑可行灰边会产生偶隔离带的情况。如果移位排序过程中出现这种情况，根据原有算法计算会得到错误的移位序列。本文给，出了这种情况的实例。另外，在修，并设计新算法修正了这一错误正算法

6、的基础上设计了详细的数据，、。，口，结构和实现方法对复杂度分别为矿和的三个移位排序多项式时间算法分别进行了实现和验证。并用其中效率最高的复杂度为矿的。在输入长度为，个基算法实现与前人的移位排序程序进行了对比因的情山东大学硕士学位论文，，，。况下运算时间仅需要秒比对比程序快约倍本文的主要成果和创新点如下·提出了准最小子排列的概念及其特殊性质。。给出了在可行移位产生偶隔离带的情况下找到一个有效移位的算法。。设计新的移位排序算法修正了原有算法中存在的错误。·，提出了复杂度为。矛的移位排序算法的数据结构和实现方法对该算法。，

7、进行了实验与前人根据复杂度为口矛的算法实现的程序对比效率有显著的提高。·，进一步实现了复杂度为口矿和口矛的两个算法对三个算法的实验结果进行了比较和分析。本文的实验结果和数据对分子生物学中研究生物的进化过程具有十分重要的意义。，，关键词计算生物学基因组重组移位山东大学硕士学位论文，琦·，，，，’知一流勺”而腼柳叭止帅，认叭小勿也一，小哪，，，哪呷—一山东大学硕士学位论文，认叭，，，，川而认叭一，加电知，，山东大学硕士学位论文第章绪论背景介绍随着生物技术尤其是基因技术的发展，人们对生命的认识不断深入。在过去的几年，，。里

8、科学家们完成了克隆实验并且完成了人类的染色体图谱计划科学家们通过实验获取了大量基因组的数据，如何快速有效地分析这些数据成为我们面对的一大课题。这也是计算生物学所要研究的一大课题。生物进化的主要形式是基因组重组。六十年前，材和发表，，了一篇重要论文提出对果蝇的对基因组进行重组的思想证明了两种不同物种和的染色体基因序列可以通过基因组的次反转进行相互