论文部分内容阅读
新测序技术的数据产生能力已经超越著名的摩尔定律,当前基因组数据正以12-18个月10倍以上的速度增长。数据处理所耗费的时间、人力与经济开销在整个测序流程中所占的比重越来越大。我国十三五期间将对150万人进行基因组测序,每个人将产生300-500GB的数据,基因数据总量在十三五末期将达到EB级别。而对于宏基因组学,仅1克土壤样品的宏基因组测序就可以产生50TB的原始数据。如何高效处理超大规模生物序列数据是高性能处理生物信息分析必须面对的课题。生物序列聚类分析是生物信息学和现代生命科学研究中一个基本且重要的问题,在冗余去除、序列分类和物种分析等方面具有重要意义。本文的研究内容是超大规模生物数据的聚类以及如何利用高性能计算技术来加速聚类的过程,本文主要解决了四个方面的挑战:一、超大规模生物序列数据的I/O问题:在超大规模序列数据聚类分析中本文面临的首要问题是如何高效解析规模如此之大的生物序列数据,这是后续序列数据处理和分析的前提。为此本文提出了一个专门用于生物序列数据处理的高性能I/O框架。本文充分利用了 FASTA以及FASTQ格式的特性,设计并开发了一套面向多核平台的、支持轻量级格式化的I/O框架,消除了大规模生物序列处理中 I/O性能瓶颈,并且该框架已经应用于本文开发的高性能序列相似度计算软件RabbitMash中。该框架的提出为后续的序列聚类分析奠定了基础。另外本文还将该框架推广应用于I/O密集的测序数据质量控制软件RabbitQC中,得益于这个高效率的I/O框架,RabbitQC取得了较大性能提升。二、超大规模以及超长生物序列的相似度计算问题:如何度量序列之间的相似度是生物数据聚类分析中的核心问题。在超大规模以及超长序列相似度计算方面,本文介绍了一个面向多核计算平台的高性能序列相似度分析软件RabbitMash。RabbitMash采用了最小哈希(MinHash)算法并且使用Jaccard Index来评估基因组或者序列之间的相似度。MinHash算法的复杂度远远低于基于动态规划的比对算法以及非基于比对的kmer方法,该算法是处理超大规模数据以及超长序列的一种行之有效的手段。在算法实现上,RabbitMash充分利用了现代高性能多核计算平台上的快速存储设备以及具备强大计算能力的向量处理单元。在单个计算节点上,RabbitiMash成功地将1.1TB生物序列的距离矩阵计算时间缩短到5分钟,相对于其它基于比对的计算方法,RabbitMash的性能提升可以达到2-3个数量级。在RabbitMash的基础上,本文继续开发了RabbitSketch 软件库。除 MinHash 算法外,RabbitSketch 中还支持 HistoSketch、OrderMinHash 以及 HyperLogLog 等一系列 sketch 算法,RabbitSketch 是后续聚类工作中相似度计算的核心。同时本文将RabbitSketch封装为一个独立的软件库提供给其他科研人员使用,并且针对不同的用户群体提供了 C++和Python两种语言的API。三、层次聚类在大规模生物序列数据处理上的拓展性问题:为了解决层次聚类算法的数据拓展性问题,本文实现了一种支持超长序列的、基于稀疏距离矩阵的层次聚类方法,该方法使用RabbitMash计算稀疏距离矩阵,然后将这个稀疏矩阵按距离从小到大的顺序排序,最后使用hcluster算法对已排序的稀疏矩阵进行聚类。这个方法中除了计算稀疏距离矩阵之外另一个性能热点就是稀疏矩阵的排序操作。针对这个比较耗时的排序操作本文提出了一个基于归并排序和排序网络的混合并行排序算法,并介绍了其在多核和众核平台上的优化实现。四、贪心增量聚类算法在分布式环境下的拓展性问题:本文还介绍了一个面向分布式环境下的贪心增量聚类框架,该框架将贪心增量聚类方法拓展到了集群环境上,打破了单节点计算资源不足对聚类分析数据规模的限制。该框架采用了“MPI+Pthread”的混合并行编程模型,并且使用计算通信掩盖的技术来降低节点间通信带来的额外开销。最终,该框架能够充分利用分布式计算集群对更大规模的生物序列数据进行聚类分析。拓展性测试表明该框架在200个CPU核心的分布式测试环境下取得了接近线性的拓展性。综合上述的研究内容以及所取得成果,本文中所提出的方法在现代多核与众核平台以及分布式集群平台上基本完成了超大规模生物序列数据的聚类分析工作,可以在可控时间内完成对TB级数据的聚类分析工作。另外,本文所述的工作成功地将高性能计算的相关技术应用于超大规模生物序列分析中,并且将其中通用的方法封装为相应的软件包和软件库。本文已经将高性能I/O框架RabbitIO、高性能测序数据质控软件RabbitQC、高效基因组分析软件RabbitMash、高性软件库RabbitSketch以及分布式贪心增量聚类框架DGCF发布到开源软件平台Github和Bitbucket上,这些高性能软件能够极大提高相关数据分析工作的效率。