基于海明距离的DNA序列中相似性重复片段查找技术研究

论文摘要

生物信息学是随着人类基因组计划的启动、基因序列和蛋白质序列等生物数据迅猛增加而逐渐兴起的一门通过综合运用数学、计算机科学和信息科学来研究生物系统中信息现象的科学。在其广泛的研究领域中,重复片段查找是一个重要的DNA序列分析基础问题,其中的相似性重复片段查找因具有重要的生物意义以及其问题本身的复杂性,一直以来都是广大生物信息学研究人员致力研究的重要课题之一。本文针对DNA序列中两类重要的相似性重复片段——相似性串联重复片段和相似性反向重复片段的查找技术进行了深入研究,在分别为两类重复片段进行形式化定义之后,设计了相应的索引技术和查找算法用于两类相似性重复片段的查找和识别。在相似性串联重复片段查找的研究中,首先在海明距离的基础上定义了模式相似度和相邻相似度的概念用于衡量相似性串联重复片段模式间的相似程度,并提出了新的相似性串联重复片段定义Largest Neighbor-similarity-based Approximate Tandem Repeats （LNATR）。之后,通过将DNA序列划分为模式单元,设计了模式单元数组（Pattern Unit Array, PUA）的索引结构用于LNATR的查找。最后在模式单元数组上,根据后继信息进行模式连接以及模式增长,设计了一种基于模式单元数组的LNATR查找算法,并与Gad M. Landau等人提出的查找算法进行了比较。在相似性反向重复片段查找的研究中,首先在海明距离的基础上定义了匹配度用于衡量相似性反向重复片段模式间的匹配相似程度,并综合考虑了反向重复片段模式间可能存在间隔的特点,提出了新的相似性反向重复片段定义Largest Matching-degree-based Approximate Inverted Repeats （LMAIR）。之后设计了边界索引（Boundary Index, BI）的索引技术用于LMAIR的查找。最后在边界索引的基础上,分别设计了基本LMAIR查找算法和优化的LMAIR查找算法,并对两种算法进行了比较。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 DNA序列中的重复片段
• 1.1.1 DNA序列
• 1.1.2 DNA序列中的重复片段
• 1.1.3 DNA序列中重复片段的查找
• 1.2 相似性串联重复片段查找相关研究
• 1.2.1 Gad M. Landau查找算法
• 1.2.2 Tandem Repeats Finder
• 1.3 相似性反向重复片段查找相关研究
• 1.3.1 Porto & Barbosa查找算法
• 1.3.2 Inverted Repeats Finder
• 1.4 本文研究工作
• 第二章 相似性串联重复片段查找研究
• 2.1 相似性串联重复片段的定义
• 2.2 模式单元数组
• 2.2.1 模式单元数组结构
• 2.2.2 模式单元数组的建立
• 2.3 相似性串联重复片段LNATR查找算法
• 2.4 本章小结
• 第三章 相似性反向重复片段查找研究
• 3.1 相似性反向重复片段的定义
• 3.2 反向重复片段索引技术
• 3.2.1 边界索引结构
• 3.2.2 边界索引的建立
• 3.3 相似性反向重复片段LMAIR查找算法
• 3.3.1 基本查找算法
• 3.3.2 算法优化
• 3.4 本章小结
• 第四章 实验与性能分析
• 4.1 LNATR查找的实验与性能分析
• 4.1.1 模式单元数组
• 4.1.2 LNATR查找
• 4.2 LMAIR查找的实验与性能分析
• 4.2.1 边界索引
• 4.2.2 LMAIR查找
• 4.3 本章小结
• 第五章 结束语
• 参考文献
• 致谢
• 攻读硕士期间发表的论文