基于短序列比对的InDel检测算法研究

摘要

随着下一代测序技术即高通量测序技术的诞生和迅猛发展，测序成本越来越低，通量越来越大，极大地促进了对生物信息学的研究。基于序列比对，对插入和删除（Insertion and Deletion，InDel）的检测和分析有助于找到与疾病相关的一些位点，为后续的疾病病理确定，治疗方案探索有重要意义。但是海量的高通量数据以及对检测结果的准确性要求使得InDel检测面临着巨大的挑战。因此本课题基于DNA短序列比对，并针对InDel检测算法研究存在的困难进行了探讨和研究。
　　若直接将短序列比对到参考序列上会出现两个问题，一个是映射过程中计算复杂度高，另一个是如果read在参考序列上存在匹配，则该read将会映射到其在参考序列的第一个匹配，这一般不是最优的匹配。为了解决以上两个问题，本课题先对滑窗方法产生的参考序列的seed集合进行构建哈希表，然后在比对过程中便可利用哈希表对read进行定位。值得注意的是，由于参考序列长度比较长，而哈希表构建比较耗内存，因此本课题在构建哈希表的同时对序列进行了二进制压缩，使得内存占用减少至四分之一。
　　在InDel检测过程中存在同样存在两个问题，一个是高通量测序技术产生的read的长度很短，更不用说作为read的子序列的种子（seed），因此一个seed在定位时往往会定位到参考序列的多个位置上，另一个是InDel在read上的分布是随机的，可能出现seed覆盖了InDel的位置，而使得seed错误地定位到参考序列上的某个位点。为了提升InDel检测的正确性，本课题提出先对read采用滑窗方法选出多个子序列分别比对到参考序列上得到各自的候选位点，并且为了降低候选位点的假阳性，本课题引入supportNum，在后续的评估过程中基于supportNum设定阈值，缩小了最终InDel候选集的范围。
　　在比对方法的选择上，由于本课题针对的InDel很小，只有1-2bp，故只要截取参考序列上从定位位点开始的一段比长2bp的连续序列就可以完成比对，比较适合用全局比对方法进行比对，因此本课题中使用基于Needleman-Wunsch的比对方法。为了进一步提升算法的性能，本课题提出了对优秀检测结果求交集，并对交集进行二次评估。最后的实验结果证明，本文提出的算法对InDel检测效果良好。

目录

第1章 绪 论

1.1 课题研究的背景、目的和意义

1.2 课题的研究现状

1.3 课题的研究内容

1.4 本文结构安排

第2章 序列比对概念及相关知识

2.1 引言

2.2 相关背景知识

2.3 DNA序列比对

2.4 InDel检测

2.5 本章小结

第3章 基于DNA短read数据的InDel检测算法研究

3.1 引言

3.2 InDel检测研究背景

3.3 InDel检测算法设计

3.4 整体实现

3.5 本章小结

第4章 算法实验分析

4.1 引言

4.2 模拟实验数据

4.3 实验

4.4 本章小结

结论

参考文献

攻读硕士期间发表的论文及其它成果

声明

致谢