DNA序列中基于后缀树的重复体识别算法

论文摘要

重复体识别是生物信息学中分析基因组序列的主要手段之一。在真核生物基因中重复体DNA占据了非常重要的地位。通过识别重复体可以发现基因组的进化规则和许多疾病的遗传规律。许多转位子重复体序列作为可编码区域重复出现在基因组序列中,识别这些重复体对基因组解码起到了很重要的作用。通过考虑重复体序列的长度和发生频率,提出了一种基于后缀树的识别初级重复体的RepSeeker算法。算法采用最低限制频率,并通过重叠性合并,最大程度地扩展了重复体的长度。算法以DNA序列所构造的后缀树作为输入,并以基于后缀树的查询算法作为手段,最终生成输入的DNA序列的初级重复体分类表。为了进一步地提高RepSeeker算法的效率,我们对后缀树构造算法进行了适应性改进。在构造后缀树时,给叶子节点编号,并在分支节点加入了叶子信息数组LL(LeafList)。在此基础上,改进了基于后缀树的查询算法,从而避免了RepSeeker算法进行高频度的子树遍历。对Ukkonen后缀树构造算法的改进所带来的问题是对空间要求加大,而构造后缀树算法的时间复杂度几乎没有受到影响。测试中使用了NCBI中的几条典型DNA序列作为测试对象,并与改进Ukkonen前的重复体识别算法做了比较分析。结果表明RepSeeker在没有损失精度的情况下很大程度地缩短了运行时间。

论文目录

• 摘要
• Abstract
• 目录
• 第一章 绪论
• 1.1 引言
• 1.2 重复序列识别算法研究现状
• 1.3 本文所做的工作
• 1.4 本文章节安排
• 第二章 后缀树
• 2.1 相关定义
• 2.2 后缀树
• 2.3 后缀树构造算法
• 2.3.1 Ukkonen后缀树构造
• 2.3.2 Ukkonen后缀树构造算法实现
• 2.3.3 一个构造后缀树的实例
• 2.4 基于后缀树的查询算法
• 2.5 后缀树适应性改进
• 2.6 基于改进后缀树的查询算法
• 2.7 本章小结
• 第三章 REPSEEKER重复体识别算法
• 3.1 引入初级重复体
• 3.2 初级重复体的定义及推论
• 3.3 REPSEEKER初级重复体识别算法
• 3.4 REPSEEKER算法实现
• 3.5 后缀树在REPSEEKER算法中所起的作用
• 3.5.1 求子串在输入序列中的发生频率
• 3.5.2 求子串在输入序列中的出现位置
• 3.6 后缀树的改进对REPSEEKER算法的影响
• 3.7 时间和空间复杂度分析
• 3.8 实验
• 3.8.1 实验参数设置
• 3.8.2 实验结果
• 3.8.3 结果分析
• 3.9 本章小结
• 第四章 结束语
• 致谢
• 参考文献
• 研究成果