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

摘要

随着分子生物学和高通量基因测序技术的飞速发展，大量的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，同样获得了较好的优化效果。由此可见，本文为解决小系统发育问题提供了两种较优的求解方法。

目录

摘要

第1章 绪论

1．1 研究背景及意义

1．2 遗传学的相关概念

1．2．1 染色体

1．2．2 DNA和RNA

1．2．3 遗传物质

1．3 系统发育问题

1．3．1 系统发育问题概述

1．3．2 系统发育问题分类

1．3．3 研究现状

1．4 论文主要研究内容

1．5 论文结构安排

第2章 模拟退火算法基本原理

2．1 模拟退火算法基本原理

2．1．1 模拟退火算法的思想

2．1．2 模拟退火算法的描述

2．1．3 模拟退算法的核心技术

2．2 模拟退火算法的结构

第3章 SA2SP：求解DLA模型的模拟退火算法

3．1 问题以及符号定义

3．2 复制-丢失进化模型：DLA

3．3 问题求解方法

3．3．1 ALIGN算法

3．3．2 LABLE算法

3．3．3 模拟退火算法SA2SP

3．4 实验结果

3．4．1 实验数据

3．4．2 性能评价

3．5 本章小结

第4章 multiSA2SP：求解DLIA模型的模拟退火算法

4．1 复制-丢失-倒位进化模型：DLIA

4．2 问题求解方法

4．2．1 multiALIGN比对算法

4．2．2 multiLABLE算法

4．2．3 模拟退火算法multiSA2SP

4．3 实验结果

4．3．1 性能评价

4．4 本章小结

第5章 结束语

5．1 总结

5．2 展望

参考文献

攻读硕士期间发表论文

致谢

声明