基于云计算平台的下一代测序数据错误修正算法研究与实现

Next-generation sequencing data is making essential impact on the biological and biomedical studies due to its ability in discovering the relationship between genotypes and phenotypes per se. However, the data contains sequencing errors inevitably because of the bias introduced by the sequencing platforms and approaches. These errors, substitutions, insertions and deletions, pose great challenge for data analysis. Existing error correction approaches partially solve the problem by only handling small data or reduce the performance to cope with large data. To solve this problem, we propose an algorithm that can handle large dataset while keep good performance running on cloud computing platform. This algorithm smoothly combines MapReduce and overlap-layout-consensus model together, and corrects errors by a classical statistical model. The advantages of the model are in three fold: MapReduce model can handle huge volume of dataset; overlap-layout-consensus model keeps the intactness of input data and; the statistical model guarantees the good performance.

下一代测序数据正以革新化的态势影响着生命科学、医学等相关领域的研究，因其能从根本上揭示这些外在表象的内在本质。然而，由于受到测序平台、测序方法以及基因自身序列结构的影响，测序数据都或多或少存在着替换错误和插入删除错误。这些错误对后续数据分析提出了极大挑战。现有错误修正方法要么只能处理小数据，要么降低准确度来处理大规模数据。鉴于此，该课题设计一种基于云计算平台的、可处理超大规模数据集的、同时保证处理精确度的分布式并行算法。该算法把MapReduce分布式思想和overlap-layout-consensus数据处理模型有机的结合起来，同时利用统计模型修改测序错误。其主要优点体现在：MapReduce思想可以分布式并行处理超大规模数据；overlap-layout-consensus模型可以保持数据的完整型；利用统计模型修改错误碱基保证算法准确性。

基因组是解密生命奥秘、剖析疾病产生机制的核心要素，而获得高质量基因测序数据是实现解密的关键。现有技术能够产生大规模测序数据，但是所有测序数据都存在错误：插入、删除和替换。纠正测序错误是获得高质量测序数据的前提。本课题重在研究如何纠正测序错误，同时降低大规模测序数据对时间和空间的限制。简要来说包含三个层次：大规模测序数据的压缩存储以及快速访问技术；测序错误的修正算法；云平台下算法实现。探索数据压缩技术可以将超大规模数据对内存的依赖大大降低，甚至在普通电脑上能处理大规模测序数据；而快速访问技术可以使得大规模数据操作在极短的时间内完成，降低大规模数据对超级计算机的依赖。测序错误修正主要从统计和覆盖度角度处理，进一步提高错误修正的准确性。云平台主要承担大规模测序数据并行化探索。基于以上研究，我们发表了4篇SCI论文，其中3篇Bioinformatics（SCI一区），1篇BMC Genomics（SCI二区）；以主持人身份成功申请到3项省部级自然科学基金项目；获得一项国际大会最佳论文奖。简单来说，在测序数据压缩方面，我们提出了耦合Bloom Filter用来存储计数k单体。该算法在频度为1的k单体上压缩比达到20倍，对于大于1的k单体压缩比达到8倍，综合压缩比达到16倍。对比现有最好算法，我们能将压缩比提高近3倍。除此以外，该算法对数据访问的时间复杂度为常数。在错误修正方面，我们提出了以k单体为种子重组测序读长和z-score为依据的两种测序错误修正算法。前一种算法由于考虑了位点的全覆盖能将单位点错误率从1.28%降低到0.17%；后一种算法用z-score能将覆盖度低（通常小于等于5）的k单体从假阳性数据中区分出来，实验表明该算法能将k单体纯度平均提升11.25%。在云平台方面，我们采用MapReduce策略用以分布式处理错误修正，并实现在云平台上运行的错误修正算法，能将错误修正时间线性降低。该课题对基因测序的错误修正以及时间和空间上优化算法对序列分析起到一定的促进作用，为下游数据分析提供了更多选择。