基因组中最大唯一匹配的查找算法研究

论文摘要

最大唯一匹配在基因序列比对中有着重要的作用。它可以从相互重叠的序列片断中重构DNA的完整序列,可在各种试验条件下从探测数据中决定物理和基因图存贮,可遍历和比较数据库中的DNA序列来判断两个或多个序列的相似性。本文首先简单介绍了国内外现有的部分研究成果,并在详细介绍后缀树和后缀数组的基础上,给出了一种基于后缀数组的最大唯一匹配(Maximal Unique Matches简写为MUM)查找及其排序的方法。算法首先构造出两条基因序列的后缀数组,然后通过两两比较后缀数组中相邻的后缀获得相邻后缀的最长公共前缀(Longest Common Prefixes简写为LCP)值,然后通过扫描满足MUM条件的LCP值求出MUM,最后利用最长递增子序列(Longest Increasing Subsequences简写为LIS)算法对获得的MUM进行排序。测试结果表明,在同等规模的数据量下,基于后缀数组的算法相比基于后缀树的算法在空间上具有显著优势,基于后缀数组的MUM查找及其排序方法可以节省28%的空间。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 背景介绍
• 1.2 研究现状
• 1.3 论文工作
• 第二章 后缀树
• 2.1 后缀树简介
• 2.2 后缀树的构造算法
• 2.2.1 构造后缀树的朴素算法
• 2.2.2 构造后缀树的Ukkonen算法
• 2.3 后缀树中的字符串匹配问题
• 2.4 本章小结
• 第三章 后缀数组
• 3.1 后缀数组简介
• 3.2 后缀数组构造算法
• 3.2.1 后缀数组的构造
• 3.2.2 查找LCP
• 3.3 本章小结
• 第四章 全基因序列比对
• 4.1 相关介绍
• 4.2 后缀树和后缀数组的联系
• 4.3 查找MUM
• 4.3.1 利用后缀树查找MUM
• 4.3.2 利用后缀数组查找MUM
• 4.4 MUM的排序
• 4.4.1 LIS问题描述
• 4.4.2 LIS算法的动态规划求解
• 4.4.3 改进的LIS算法
• 4.5 实验结果分析
• 4.5.1 实验环境
• 4.5.2 实验数据
• 4.5.3 实验结果
• 4.6 结论
• 4.7 本章小结
• 第五章 总结与展望
• 致谢
• 参考文献
• 研究成果