用加强的后缀数组查找MUM

论文摘要

自第一个使用鸟枪法成功地完成流感嗜血杆菌完整的基因组测序以来,基因组被完全测序的物种数量每年都在飞速增长。当两个非常相近物种的完整基因组可以获得的时候,首要的问题是如何比较和注释这些基因组。对此,传统的序列比对算法已不能胜任这一工作。因此,人们提出了许多新的用于比对基因组规模序列的方法。MUMmer是最重要的用于比对整基因组序列的系统之一,它所采用的基于锚的方法以及使用后缀树查找潜在锚的算法被越来越多的基因组规模比对程序所采用。因此,在本文的开始,首先对整基因组比对系统MUMmer的算法、整体结构和系统的演化进行了分析,这为系统的改进以及提出新的基于锚的基因组规模的序列比对方法提供了参考依据。由于可获得的计算资源的限制以及所要处理序列数据规模的日益增长,尽管后缀树的构造以及查找最大唯一匹配(MUM)算法的时间和空间复杂度都是线性的,但其空间花费依然是个很大的问题。鉴于此,本文决定使用加强的后缀数组来替代后缀树查找两基因组间的MUM。本文实现了两个基于加强的后缀数组查找MUM的算法,它们分别基于加强的后缀数组的性质和对后缀树的工作方式的模拟,与对应的基于后缀树的方法具有相同的时间复杂度,实验表明它们比相应的基于后缀树的方法有更大的空间节省。此外,在使用加强的后缀数组模拟后缀树的流匹配算法的过程中,提出了一个新的为后缀数组添加后缀链的线性算法,并证明了算法的正确性。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 引言
• 1.2 本文的主要工作
• 第二章 整基因组比对
• 2.1 背景
• 2.2 MUMmer的产生
• 2.3 MUMmer的系统演化
• 2.3.1 MUM的定义
• 2.3.2 MUMmer1
• 2.3.3 MUMmer2
• 2.3.4 MUMmer3
• 2.4 总结
• 第三章 加强的后缀数组
• 3.1 概述
• 3.2 基本定义
• 3.3 后缀数组基本信息的计算
• 3.3.1 后缀数组的构造
• 3.3.2 线性时间的lcp计算
• 3.4 后缀数组的lcp-interval树
• 3.4.1 lcp interval
• 3.4.2 lcp-interval树
• 3.5 自顶向下遍历
• 3.5.1 child表的构造
• 3.5.2 以常量的时间确定孩子interval
• 3.5.3 一个例子：怎样确定串P在串S中的出现
• 3.6 加入后缀链
• 3.6.1 后缀链
• 3.6.2 一个简单的后缀链表的构造算法
• 3.7 实现细节
• 3.7.1 lcp表
• 3.7.2 child表
• 3.7.3 后缀链表
• 第四章 用加强的后缀数组替换后缀树查找MUM
• 4.1 概述
• 4.2 基于加强的后缀数组性质计算MUM的算法
• 4.2.1 查找两基因组间的MUM
• 4.2.2 查找多个基因组间的MUM
• 4.3 基于加强的后缀数组的流匹配算法
• 4.3.1 一个线性时间的后缀链interval的构造算法
• 4.3.2 计算MUM的流匹配算法
• 4.4 实验结果及分析
• 第五章 结束语
• 致谢
• 参考文献
• 研究成果