百万核扩展的基因组De Novo组装

With the increasing requirement on analysis of huge amount of sequencing data, scalable analysis model and computing algorithm are critical to bridge these two parts and help to acquire knowledge from these data. Genome assembly is one of the most important applications in sequencing data analysis, however it is still facing embarrassingly parallel sub-problem, huge amount of memory requirement and low parallel efficiency. With these difficulties, this project will focus on scalable genome assembly with millions of cores, and the main research area is: 1) scalable mathematical abstraction and computation model for de Bruijn graph simplification, 2) minimize memory usage by filtering low-frequency kmers in de Bruijn graph and graph structure compress, 3) IO and communication optimization with parameterization, streaming, overlapping technology for graph simplification. Finally the genome assembler will be developed and test on domestic supercomputer with 1000,000 cores and at least 30% efficiency. With the research work on these three parts, this project wishes to explore practical breakthrough solutions for this problem.

随着大规模基因数据分析应用压力的增长，高效的分析计算能力是从海量基因数据中获取知识的关键。然而基因数据分析的核心流程基因组De Novo组装却面临算法并行扩展难，内存资源需求大，系统并行效率低的问题。针对以上问题，本课题将围绕百万核扩展的基因组De Novo组装算法展开研究工作，主要研究(1)高可扩展De Bruijn图收缩算法的数学抽象与计算模型, (2)面向海量基因数据的De Bruijn图过滤和存储压缩技术, (3)图收缩算法底层IO和通讯调优策略及高效参数化，流水化，重叠化技术。本项目最终将研发面向百万核的高效可扩展基因组De Novo组装算法和软件，并在国产超级计算机上扩展到100万核，达到30%以上的并行效率。项目的实施将大大提高基因大数据分析的效率，同时也将为我国高性能研究领域国产开源软件的发展做出一定贡献。

我们从高可扩展DBG数学计算模型，DBG过滤和压缩， IO和通讯调优和并行化三个方面对基因组组装进行优化，包括各个流程的优化和功能延展提升。基于高可扩展的双向DBG模型和SWAP异步计算模型，在最新版本的SWAP-Assembler 2其扩展性能力求提高到近百万核心，并在最终在MIRA上实现了262144核心的性能扩展。 为了达到该扩展性能，我们嵌入计数bloom过滤器模块以提高DBG图的过滤压缩性能，以及内存和通信效率； 在IO和通信聚合优化方面我们运用了FAA算法，修改了SWAP的通信协议，将原协议中的4个工作循环优化为2个工作循环，从而提高消息通讯的并发度并通过消息聚集技术提高消息通讯的效率来提高系统通讯效率。 测试中我们使用Mira超算，SWAP-Assembler 2在组装现有最大的基因数据，4T的千人基因组数据时，可以扩展到262144核，并达到27.5%的系统并行效率。由于基因组装软件的可扩展性是由图的大小也即顶点数量所直接决定的，为了进一步测试SWAP Assembler 2的弱扩展性，我们进行了第二组测试，增加图本身的大小。在第二组扩展实验中，用人类基因组的参考序列模拟不同物种的测序数据来测试升级的SWAP-Assembler 2的扩展性，测试数据依然成比例从256G增长到4T，共5个数据，其中，4T的数据包含了500亿条kmer，也即对应的de Bruijn图有500亿个顶点。实验表明SWAP-Assembler 2的五个部分时间消耗综合几乎为固定大小，随着核数从1024增加到16384，时间消耗会降低到5分钟以内。