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

摘要

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

目录

文摘

英文文摘

声明

第一章绪论

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本章小结

第四章结束语

致谢

参考文献

研究成果