一种基于互信息以及期望最大化的下一代测序纠错算法

摘要

下一代测序(NGS)技术因其较高的测序速度和较低的测序成本，已经逐渐替代传统测序技术，成为生物信息学领域对基因序列进行测序的首选方法。但下一代测序技术经常会出现短序列结果，以及测序结果准确率不够高等问题。因此，下一代测序更依赖于通过各种纠错工具来进行序列纠错，以提高测序结果的正确率。近年来，随着计算机技术的不断发展，利用计算机上的纠错软件对测序结果进行纠错，已经成为生物研究领域的一种趋势与常态。
　　在所有的下一代测序平台中，Illumina测序平台因其相对其它测序平台，拥有较低的测序成本，以及较好的测序质量，目前已经成为领域内最受欢迎的测序平台。但Illumina平台由于测序技术限制的原因，随着测序长度的增长，其测序的精度会逐渐降低。这也使得测序结果经常会产生短读段，难以保证测序结果的准确度。因此，本论文根据以上研究背景和研究现状，决定基于Illumina测序平台，研究出一种基于互信息以及期望最大化的下一代测序纠错算法，用以提高该平台测序结果的质量。
　　本论文介绍了下一代测序技术和基因纠错方法的相关背景和研究现状，以及本论文所需的相关技术和算法，提出了一种基于互信息以及期望最大化的下一代测序纠错算法，对下一代测序的测序结果进行纠错。
　　同时，利用下一代测序技术对基因组进行测序，测序完成后将会获得一系列的k-mer序列。k-met序列在基因纠错的过程中具有举足轻重的作用，许多纠错算法都需要使用这些序列来进行纠错过程。而测序结果产生的k-met序列数量十分庞大，如果不将这些k-mer序列进行正确地保存，将会影响后续纠错过程的速度和精度。针对这一情况，本文提出利用Bloom Filter数据结构对k-mer序列集合进行存储，以降低集合的存取时间及占用空间。
　　我们将使用本文提出的算法和其它常用的基因纠错算法进行对比实验。实验结果表明，本文提出的算法相比于其它常用方法，在纠错正确率方面有较大程度的提高。同时，使用Bloom Filter数据结构对k-met序列集合进行存储，有效地降低了基因纠错的时间复杂度和空间复杂度。

目录

声明

摘要

第一章 绪论

1．1 研究背景及意义

1．2 DNA测序技术介绍

1．2．1 第一代测序技术——桑格测序

1．2．2 下一代测序技术

1．2．3 下一代测序优点

1．3 本文的研究目的和内容

第二章 下一代测序纠错相关技术分析

2．1 下一代测序纠错过程

2．2 基于不同底层的下一代测序纠错算法

2．3 常用基因数据存储方式分析

2．3．1 线性数组

2．3．2 链表

2．3．3 散列表／散列集合

2．4 传统区分正误基因序列方法分析——基于汉明距离的区分方法

2．5 传统基因纠错方法分析——基于k-频率的错误纠正算法

3．1 Bloom Filter介绍

3．2 Bloom Filter原理

3．3 Bloom Filter特点

3．4 Bloom Filter的错误率、哈希函数数量以及数组长度的确定

第四章 改进区分正误k-met序列的方法

4．1 互信息相关介绍

4．1．1 皮尔森相关系数

4．1．2 互信息

4．2 期望最大化算法相关介绍

4．2．1 最大似然估计

4．2．2 期望最大化算法介绍

4．2．3 期望最大化算法简介

4．2．4 期望最大化算法计算过程

4．3 改进方法——基于互信息以及期望最大化的区分方法

4．3．1 计算k-mer序列的互信息值

4．3．2 利用期望最大化算法区分受信任和不受信任的k-mer序列

第五章 改进基因纠错方法

5．1 改进基因纠错方法——多序列比对和k-频率方法相结合的错误纠正算法

5．2 利用改进基因纠错方法对测序结果进行纠正

6．1 实验环境

6．2 实验数据

6．3 实验过程

6．3．1 将待纠错读段集合切分成k-met序列

6．3．2 计算k-met序列集合的互信息

6．3．3 利用期望最大化算法拟合k-mer序列集合的频率分布

6．3．4 获得受信任的k-mer序列集合

6．3．5 使用Bloom Filter存储受信任的k-met序列

6．3．6 使用多序列比对和k-频率方法相结合的错误纠正算法进行纠错

7．1 论文总结

7．2 论文的不足与展望

参考文献

致谢

攻读硕士学位期间参与项目和发表论文情况