DNA序列中串联重复体查找算法研究

摘要

在DNA序列分析中，串联重复体查找是一个重要的基础性问题。人类DNA序列50％以上是由串联重复体组成的。串联重复体在基因表达、调控和遗传等方面起着十分重要的作用，同时它是产生多种疾病的病因。另外以串联重复体为基础的“DNA指纹技术”在法医学等领域广泛应用。因此关于串联重复的研究具有十分重要的意义。
　　 本文主要研究了串联重复体查找算法。⑴针对精确串联重复体提出了一种基于LZ分解查找串联重复体的算法。对于存储在后缀树上的字符串S，该算法能在线性的时间找到所有出现在S中的串联重复体。为了进一步提高算法的效率，我们对后缀树进行了改进，给中间节点加入了叶子信息数组，这样就避免了算法对子树的遍历。⑵引入了一种新类型的近似串联重复体-进化串联重复体，由于以前提出的算法都不能解决进化串联重复体的查找问题，因此提出了基于海明距离的查找算法。对于给定的重复单元的长度Z，该算法的时间复杂度为O(ln2)，解决了进化串联重复体的查找问题。为了说明算法的正确性和有效性，本文将这两种分别应用于实际的基因组DNA序列，结果表明基于LZ分解的查找串联重复体方法能找到更多的串联重复体，基于海明距离的查找方法则解决了进化串联重复体的查找问题。

目录

文摘

英文文摘

第一章 绪论

1.1 引言

1.2 重复体查找的生物意义及研究现状

1.2.1 重复体查找的生物意义

1.2.2重复体查找的研究现状

1.3 本文的研究工作

1.4 本文的章节安排

第二章 重复体查找方法

2.1 重复体查找的数据结构

2.1.1 后缀树

2.1.2 改进的后缀树

2.2 重复体查找算法介绍

2.2.1 Tandem repeat finder

2.2.2 REPuter

2.2.3 ML算法

2.3 本章小结

第三章 基于LZ分解的串联重复体查找方法

3.1 基本概念

3.2 基于LZ分解的串联重复体查找方法

3.2.1 LZ分解及串联重复体在LZ分解块上的性质

3.2.2 查找最左覆盖集

3.2.3 标注串联重复体

3.2.4 得到Occurrence集

3.3 算法描述

3.3 算法分析

3.4 实验结果分析

3.5 本章小结

第四章 基于海明距离查找进化串联重复体的算法

4.1 基本概念

4.2 基于海明距离查找进化串联重复体的算法

4.2.1 计算等价类

4.2.2 构造等价类图

4.2.3 构造位置图

4.2.4 求最大进化串联重复体

4.3 HDETR算法描述

4.4 算法分析

4.5 实验结果分析

4.6 本章小结

第五章 结束语

致谢

参考文献

研究成果