生物序列模式挖掘与识别算法的研究

摘要

生物信息学是综合运用生物学、数学、物学、信息科学以及计算机科学等诸多学科的? ? 论方法的崭新交叉学科，它是整个生命科学发展的重要组成部分，已成为生命科学研究的前沿。 生物信息学的核心是基因组信息学，包括基因组信息的获取、处、存储、分配和解释?，即以计算机、网络为工具，用数学等科学理论、方法和技术研究生物大分子，主要包括脱氧核糖核酸（DNA）和蛋白质（Protein）的序列、结构和功能。基因组信息学的关键是“读懂”基因组的核苷酸顺序，即全部基因在染色体上的确位置以及各? DNA 片段的功能，这对于人类疾病基因发现、基因与蛋白质的表达与功能研究、合理化药物设计等方面都有着重要的意义。为了能达到上述目的，生物序列模式挖掘和识别是其重要的两个关键技术。 本文针对生物序列模式挖掘和识别研究中的关键问题，主要研究了生物单序列、双序列频繁模式挖掘的研究和算法设计；生物数据的嵌入式频繁子树挖掘研究和算法设计；基因调控元件的识别以及CpG 岛的位置识别等问题。取得的研究成果如下： (1)提出了生物单序列及多序列频繁模式的快速挖掘算法。针对传统生物序列频繁模式挖掘算法会在挖掘过程中大量构建投影数据库并产生大量短的模式而导致的挖掘效率低下的问题，本文分别提出了基于基本模式前缀树的生物单序列频繁模式挖掘算法SSPM和多序列频繁模式挖掘算法MSPM。算法挖掘时能从基本模式长度开始，避免了产生大量的短的生物序列模式，同时运用基本频繁模式前缀树进行模式扩展，避免了不相关模式的干扰，实验结果证实这两个算法不仅明显提高了挖掘效率，并能得到有效的挖掘结果。 (2)提出了一种基于嵌入式子树结构的生物数据挖掘算法，应用嵌入式频繁子树算法挖掘RNA 分子的公共拓扑模式。针对目前生物数据挖掘过程中存在的生物数据量大、序列模式相似度高等问题，本文提出了一种快速高效的频繁嵌入式子树挖掘算法IRTM。该算法采用垂直方式挖掘，引入了独特的字符串编码方法表示树，同时利用域表（Scope-List）进行子串扩增和频繁性测试，加以优越的剪枝技术极大地压缩了搜索空间，加快了运行速度。通过与经典的Patternmatcher 算法以及TreeMiner 算法的对比实验表明本文算法极大提高了挖掘效率，具有更加优越的性能。 (3） 提出了一种基于蚁群优化的基因调控元件识别算法。针对已有的算法大都存在容易过早陷入局部最优以及时间复杂度过高等问题，本文提出了一种识别基因调控的新型优化算法ACRR （ant-colony-regulatory-recognition）。该算法利用蚁群优化算法能够较快求解复杂优化问题的优越性来解决此问题，不仅提高了解的质量，而且大大的降低了算法的时间复杂度。实验结果表明，与其他类似算法相比，本文算法所得结果的准确性更高，具有更快的识别速度。 (4） 提出了一种基于条件随机场模型的CpG 岛的位置识别新方法。为克服已有模型的标注偏差、需要独立假设等缺点，本文提出了用条件随机场（CRFs）模型来识别CpG 岛的位置的新方法。该方法将识别CpG 岛的位置的问题转化为序列标记问题，根据CpG 岛的位置的性质设计了相应的特征函数，通过对样本集的训练，得到样本序列和标签序列的联合概率中各个特征函数式的权重参数。然后根据所得到的分布模型，对于输入序列确定最有可能的标注序列，从而识别CpG 岛的位置。通过对标准数据库数据测试，本文算法是可行的、高效的，比HMM方法有更高的准确率。

目录

文摘

英文文摘

论文说明：图表目录

声明

第一章 绪 论

第二章 生物序列模式挖掘与识别技术的研究进展

第三章 基于模式前缀树的生物序列频繁模式快速挖掘算法

第四章 RNA 拓扑模式中的频繁子树挖掘算法

第五章 基于蚁群优化的基因调控元件识别算法

第六章 基于条件随机场模型的CpG 岛位置识别算法

第七章 总结和展望

参考文献

致 谢

在学期间的研究成果及发表的学术论文