基于模拟退火算法的两物种小系统发育问题算法研究

发布时间：2017-10-10 06:41

  本文关键词：基于模拟退火算法的两物种小系统发育问题算法研究

  更多相关文章： 两物种小系统发育问题 复制 丢失 倒位 模拟退火算法 邻域函数

【摘要】：随着分子生物学和高通量基因测序技术的飞速发展,大量的DNA序列数据已被测定,这为研究基因家族分子进化提供了必要的前提条件。根据现有生物基因重建基因家族进化史可以推断出一个可靠的系统发生,这对揭示有关基因家族进化过程具有重要意义。重建基因家族进化史不仅有助于我们更好的研究生物进化的进化机制和历史,而且还可以帮助我们揭示显性的基因组学基础、研究基因的功能。近年来,重建基因家族进化史受到国内外众多学者的关注和研究,已经成为了比较基因组学中一个重要的研究方向。本文主要针对两物种小系统发育问题进行研究,并基于模拟退火算法提出求解该问题的SA2SP算法和multiSA2SP算法。具体工作如下：针对复制-丢失比对问题模型,对两物种小系统发育问题的算法进行研究,并提出解决该问题的模拟退火算法SA2SP。首先,算法SA2SP包含比对算法ALING,该算法通过对给定的两条基因序列有针对性的插入一定数量的字符‘-’,以获得使两条基因序列上基因最大匹配的一个序列比对。其次,对于给定的一个序列比对,算法SA2SP包括一种标记算法LABLE,该算法利用复制-丢失操作序列标记给定的序列比对,其最终问题解为对应标记代价最小的比对基因组。算法SA2SP利用ALIGN算法产生问题初始解,利用LABLE算法来衡量解的优劣,并在保持邻域解多样性的前提下,引入基因块智能移动、相邻基因块位置互换和重新匹配基因块3种智能邻域算子,以产生当前解较好的邻域解,提高算法寻找问题最优解的能力。通过对算法SA2SP与算法PBLP用4种菌属的真实RNA基因数据对进化代价与时间性能测试,实验结果表明,算法SA2SP能够获得较PBLP算法更小的进化代价,且其运行时间在实际应用中是可行的,是求解两物种小系统发育问题的一种有效方法。进一步,对仅考虑复制、丢失操作的复制-丢失比对问题模型进行研究,新添加倒位(Inversion)操作,提出复制-丢失-倒位比对问题模型,并提出求解该模型下两物种小系统发育问题的求解算法multiSA2SP。首先,提出基于动态规划求解最长公共子串问题的比对算法multiALING,通过在两条基因序列中不匹配位置插入字符‘-’,以得到两条基因序列的一个序列比对。其次,对于给定的一个序列比对,本文提出一种标记算法multiLABLE,该算法利用复制-丢失-倒位操作序列标记给定的序列比对,并获得对应标记进化代价较小的操作序列。论文基于提出的multiALING算法和multiLABLE算法,设计了一种求解复制-丢失-倒位演化模型下两物种小系统发育问题的模拟退火算法multiSA2SP。算法multiSA2SP通过multiALIGN产生初始解,利用multiLABLE来衡量产生邻域解的优劣,根据邻域解进化代价作为是否替换当前解为新解的重要依据。同时还引入基因块智能移动、相邻基因块位置互换、重新匹配基因块和倒位基因块智能组合4种智能邻域算子,以产生当前解较好的邻域解,提高算法寻找问题最优解的能力。算法multiSA2SP在仅考虑复制、丢失操作的前提下,利用4种真实菌属的RNA基因数据对算法进化代价和运行时间性能进行测试,实验结果表明,算法multiSA2SP在仅考虑考虑复制、丢失操作的情况下,能够获得较PBLP算法更小的进化代价,是求解复制-丢失-倒位模型下两物种小系统发育问题的一种有效方法。综上所述,针对两物种小系统发育问题,本文提出了求解复制-丢失比对问题模型下该问题的模拟退火算法SA2SP,并获得了较好的优化效果。此外,本文对复制-丢失比对问题模型进行扩展,不仅提出了复制-丢失-倒位比对问题模型,而且还提出了求解该问题的模拟退火算法multiSA2SP,同样获得了较好的优化效果。由此可见,本文为解决小系统发育问题提供了两种较优的求解方法。
【关键词】：两物种小系统发育问题 复制 丢失 倒位 模拟退火算法 邻域函数
【学位授予单位】：广西师范大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：Q811.4;TP18
【目录】：

• 中文摘要3-5
• ABSTRACT5-9
• 第1章 绪论9-16
• 1.1 研究背景及意义9
• 1.2 遗传学的相关概念9-12
• 1.2.1 染色体10
• 1.2.2 DNA和RNA10-11
• 1.2.3 遗传物质11-12
• 1.3 系统发育问题12-14
• 1.3.1 系统发育问题概述12
• 1.3.2 系统发育问题分类12
• 1.3.3 研究现状12-14
• 1.4 论文主要研究内容14-15
• 1.5 论文结构安排15-16
• 第2章 模拟退火算法基本原理16-19
• 2.1 模拟退火算法基本原理16-17
• 2.1.1 模拟退火算法的思想16
• 2.1.2 模拟退火算法的描述16
• 2.1.3 模拟退算法的核心技术16-17
• 2.2 模拟退火算法的结构17-19
• 第3章 SA2SP：求解DLA模型的模拟退火算法19-34
• 3.1 问题以及符号定义19-20
• 3.2 复制-丢失进化模型：DLA20-21
• 3.3 问题求解方法21-28
• 3.3.1 ALIGN算法21-23
• 3.3.2 LABLE算法23-25
• 3.3.3 模拟退火算法SA2SP25-28
• 3.4 实验结果28-33
• 3.4.1 实验数据29-30
• 3.4.2 性能评价30-33
• 3.5 本章小结33-34
• 第4章 MULTISA2SP：求解DLIA模型的模拟退火算法34-46
• 4.1 复制-丢失-倒位进化模型：DLIA34-35
• 4.2 问题求解方法35-41
• 4.2.1 multiALIGN比对算法35-38
• 4.2.2 multiLABLE算法38-40
• 4.2.3 模拟退火算法multiSA2SP40-41
• 4.3 实验结果41-45
• 4.3.1 性能评价42-45
• 4.4 本章小结45-46
• 第5章 结束语46-47
• 5.1 总结46
• 5.2 展望46-47
• 参考文献47-49
• 攻读硕士期间发表论文49-50
• 致谢50-51

【相似文献】

中国期刊全文数据库 前10条

1 王晓东;解非线性0-1规划的一个算法及其在结构优化中的应用[J];数值计算与计算机应用;1988年01期

2 张晓;;基于密度聚类算法的异常检测[J];伊犁师范学院学报(自然科学版);2010年04期

3 陈沐天;找周期子字的算法[J];应用数学学报;1991年01期

4 丁才昌;方勃;鲁小平;;分布估计算法及其性能研究[J];武汉大学学报(理学版);2005年S2期

5 石明兰;杨晖;叶东毅;;面向目标的关联规则挖掘的一个FP增长算法[J];集美大学学报(自然科学版);2006年02期

6 张维群;;基于海量数据关联效应测度算法的设计[J];统计与信息论坛;2012年07期

7 罗蕾,徐洪利;构造Dn-最优确切设计的优化方法──离散算法[J];辽宁大学学报(自然科学版);1999年02期

8 贺永恒;王斌;;基于蚁群算法的候选标签子集构造方法研究[J];中国科技信息;2014年06期

9 武小悦,沙基昌;构造网络不交化最小路集的一种新算法[J];系统工程理论与实践;2000年01期

10 姜建国;刘永青;刘梦楠;王国林;李f ;;类电磁机制算法研究与改进[J];计算力学学报;2014年01期

中国重要会议论文全文数据库 前2条

1 潘志明;郑骏;钱卫宁;周傲英;;构造XML相似相关结构库的一种有效方法[A];第二十届全国数据库学术会议论文集（技术报告篇）[C];2003年

2 林景亮;董槐林;姜青山;吴书;;一种基于新增阈值的频繁模式挖掘算法[A];第二十三届中国数据库学术会议论文集（研究报告篇）[C];2006年

中国博士学位论文全文数据库 前7条

1 张磊;基于概念格的角色工程相关算法研究[D];哈尔滨工业大学;2015年

2 孟静;新型Krylov子空间算法及其应用研究[D];电子科技大学;2015年

3 胡芳;复杂网络节点中心性多元评估与社团探测新算法研究[D];华中师范大学;2015年

4 唐益明;（1，，2，2）型异蕴涵泛三I算法及其应用研究[D];合肥工业大学;2011年

5 牛云云;求解计算困难问题的膜计算模型与算法研究[D];华中科技大学;2012年

6 李冬冬;基因组序列标注的算法与理论研究[D];国防科学技术大学;2004年

7 周琨;航空公司航班运行调度模型与算法研究[D];南京航空航天大学;2012年

中国硕士学位论文全文数据库 前10条

1 彭辉辉;基于压缩感知的心电信号压缩算法研究[D];东南大学;2015年

2 葛娜;高效用项集动态挖掘算法的研究[D];中北大学;2016年

3 叶馨;闭项集挖掘算法在医保目录制定问题上的研究与应用[D];中国科学技术大学;2016年

4 张靓云;面向微博的事件摘要生成算法研究与实现[D];西南交通大学;2016年

5 朱睿;连续变量量子密钥分发误码协商算法研究[D];哈尔滨工业大学;2016年

6 徐猛;基于关联性挖掘的流形对齐算法研究[D];华侨大学;2016年

7 李昊;基于改进蚁群算法的无线传感器网络路由的研究[D];东北林业大学;2016年

8 李先成;基于模拟退火算法的两物种小系统发育问题算法研究[D];广西师范大学;2016年

9 陈红强;大规模并行排序学习算法研究[D];西安电子科技大学;2014年

10 白鹭;基于自适应人工免疫进化的网格聚类算法研究[D];沈阳大学;2010年

本文编号：1004893