DNA片段拼接中的重复序列预归并方法研究

摘要

本文在分析了传统的Overlap-Layout-Consensus方式和Euler方式对重复序列的处理策略之后，重点研究了基于定长子串和变长子串的两种Repeats预处理方法。并在这两种方法的基础上，提出了构建不同的数据结构，定长子串统计表和变长子串统计表，详细记录两种方法各自扫描shotgun集合所得到的信息。然后，根据各自表中记录的具有相同定长子串或者变长子串的shotgun片段可能来自目标序列同一个位置或者相同repeats的原理，将这些shotgun片段进行预归并操作，并给出了各自具体算法。 通过预归并一方面可以还原出DNA目标序列中的重复序列的形状；另一方面还可以大大减少shotgun集合中的片段数目，从而降低将来拼接时的计算复杂度。使之既适用于采用Overlap-Layout-Consensus方式，又适用于采用Euler方式的序列拼接算法的重复序列预处理工作。 最后，进行了本文算法的计算机模拟分析。计算机模拟分析结果表明，本文算法不仅识别重复序列率较高，并且由于通过预归并缩减了shotgun集合的规模，有效地降低了拼接时的计算复杂度。

目录

文摘

英文文摘

声明

第1章引言

1.1研究背景

1.2 DNA序列拼接

1.3国内外研究现状

1.3.1 Overlap-Layout-Consensus方式

1.3.2 Euler方式

1.3.3重复序列预屏蔽方式

1.4本文所做工作

1.5本文的组织结构

第2章DNA序列拼接中的重复序列处理

2.1重复序列(Repeats)引发的问题

2.2 Overlap-Layout-Consensus方式对重复序列的处理

2.3 Euler方式对重复序列的处理

2.4对重复序列的预处理

2.5小结

第3章基于定长子串的重复序列预归并方法

3.1基本思想

3.2构建k-mer子串统计表S

3.3预归并特征子串

3.4预归并并识别重复序列

3.5小结

第4章基于变长子串的重复序列预归并方法

4.1基本思想

4.2构建变长子串h×w统计表S

4.3变长子串的直接预归并

4.4预归并并识别重复序列

4.5小结

第5章计算机模拟分析

5.1两种方法的计算复杂性

5.2两种方法的模拟分析

5.3小结

第6章总结和展望

6.1全文总结

6.2展望

参考文献

在校期间发表的论文

致谢