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

《基于模拟退火算法的两物种小系统发育问题算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、单位代码１０６０２Ｉ学号２０１３０１１５１９分类号ＴＰ３９１密级公开心／＾喔）＾知序硕去学化冷文基于模拟退火算法的两物种小系统发育问题算法研究－Ｒｅｓｅａｒｃｈｏｎ化ｅＴｗｏＳｐｅｃｉｅｓＳｍａｌｌＰｈｙｌｏｇｅｎｙＰｒｏｂｌｅｍｂａｓｅｄｏｎＳｉｍｕｌａ化ｄＡｎｎｅａｌｉｎｇＡｌｇｏｒｉｔｈｍ学院；计算机科学与信息工程学院专业：计算机应用技术研究方向：智能优化算法年级；２０１３级研究生；李先成指导教师：吴瑪莉教授完成日期：２０１６年

2、４月基于摸據遷火其法的两物种小系统发育问题其法研究专业名称：计弊机应用技术申请人：李先成指导教师：吴環莉教授论文答辩委员会主席：手姜巧：乐私知帮冰ｆ、广西师范大学硕±研究生学位论父基于模拟退火算法的两物种小系统发育问题算法研究：李先成指导老师研巧生：吴環莉教授学科专业：计算机应用技术：智能优化算法年级３研究方向：２０１级中文摘要随着分子生物学和高通量基因测序技术的飞速发展，ＤＮＡ大量的序列数据己被测定，这为研究基因家族分子进化提供了必要的前提条件。根据现

3、有生物基因重建基因家族进化一个可靠的系统发生史可Ｗ推断出，这对揭示有关基因家族进化过程具有重要意义。重建基因家族进化史不仅有助于我们更好的研巧生物进化的进化机制和历史，而且还可Ｗ帮助我们揭示显性的基因组学基础、研究基因的功能。近年来，重建基因家族进化史受到国内外一众多学者的关注和研究，已经成为了比较基因组学中个重要的研究方向。本文主要针对两物种小系统发育问题进行研究，并基于模拟退火算法提出求解该问题的ＳＡ２ＳＰ算法和ｎｍ２ＳＰ－ｌｔｉＳＡ算法。具体工作如下：针对复制丢失比对问题模型，对两物种小系统发育问

4、题的算法进行研究，并提出解决该问题的模拟退火算法ＳＡ２ＳＰ，。首先算２ＳＰ一法ＳＡ包含比对算法ＡＬＩＮＧ，该算法通过对给定的两条基因序列有针对性的插入定数量的字符臥获得使两条基因序列上基因最大匹配的一个序列比对，。其次对于给定一一－，ＳＡ２ＳＰ的个序列比对算法包括种标记算法ＬＡＢＬＥ，该算法利用复制丢失操作序列，其最终问题解为对应标记代价最小的比对基因组标记给定的序列比对。算法ＳＡ２ＳＰ利用ＡＬＩＧＮ算法产生问题初始解，利用ＬＡＢＬＥ算法来衡量解的优劣，并在保持邻域解多样性的前提下，引入基因块智能移动、相邻

5、基因块位置互换和重新匹配基因块３种智能邻域算子，Ｗ产生当前解较好的邻域解，提富算法寻找问题最优解的能力。通过对算法ＳＡ２ＳＰ与算法ＰＢＬＰ用４种菌属的真实民ＮＡ基因数据对进化代价与时间性能测试，实验结果表明，算法ＳＡ２ＳＰ能够获得较ＰＢＬＰ算法更小的进化代价，且其运行时间在实际应用中是可行的，一种有效方法是求解两物种小系统发育问题的。一－进，对仅考虑复制步、丢失操作的复剌丢失比对问题模型进行研巧，新添加倒位－－（Ｉｎｖｅｒｓｉｏｎ）操作，提出复制丢失倒位比对问题模型，并提出求解该模型下两物种小系统发育问

6、题的求解算法ｍｕｌｔｉＳＡ２ＳＰ。首先提出基于动态规划求解最长公共子串问题的比对算，，’ｔＡＬＩＮＣ－，通过法ｍ山ｉ在两条基因序列中不匹配位置插入字符，得到两条基因序列的一一一个序列比对。其次，对于给定的个序列比对，本文提出种标记算法ｍｕ帕ＬＡＢＬＥ，该－算法利用复制丢失－倒位操作序列标记给定的序列比对，并获得对应标记进化代价较小的操Ｉ广西师范大学硕±研究生学位论义一－作序列。论文基于提出的ｍｕｌｔｉＡＬＩＮＧ算法和ｍｕｌｔｉＬＡＢＬＥ算法，设计了种求解复制丢失－ｍｕ出ＳＡ２ＳＰＳＡ２ＳＰ倒位演

7、化模型下两物种小系统发育问题的模拟退火算法。算法ｍｕＷ通过ｍｕ，ＬＡＢ化，ｌｔｉＡＬＩＧＮ产生初始解利用ｍｕ山来衡量产生邻域解的优劣根据邻域解进化代价作为是否替换当前解为新解的重要依据。同时还引入基因块智能移动、相邻基因块位置互换、重新匹配基因块和倒位基因块智能组合４种智能邻域算子，Ｗ产生当前解较好，提高算法寻找问题最优解的能力ｕｌｔｉＳＡ２ＳＰ的邻域解。算法ｍ在仅考虑复制、丢失操作的前提下，利用４种真实菌属的ＲＮＡ基因数据对算法进化代价和运行时间性能进行测试，实ｔＳＡ２ＳＰＰＢＬＰ验结果表明，算法ｍｕｌｉ

8、在仅考虑考虑复制，、丢失操作的情况下能骼获得较一－－算法更小的进化代价，是求解复制丢失倒位模型下两物种小系统发育问题的种有效方法。－综上所述，，针对两物种小系统发育问题本文提出了求解复制丢失比对问题模型下该－问题的模拟退火算法ＳＡ２ＳＰ