Li Dinghua, Luo Ruibang, Liu Chi-Man, Leung Chi-Ming, Ting Hing-Fung, Sadakane Kunihiko, Yamashita Hiroshi, Lam Tak-Wah
Department of Computer Science, University of Hong Kong, Hong Kong.
Department of Computer Science, University of Hong Kong, Hong Kong; L3 Bioinformatics Limited, Hong Kong.
Methods. 2016 Jun 1;102:3-11. doi: 10.1016/j.ymeth.2016.02.020. Epub 2016 Mar 21.
The study of metagenomics has been much benefited from low-cost and high-throughput sequencing technologies, yet the tremendous amount of data generated make analysis like de novo assembly to consume too much computational resources. In late 2014 we released MEGAHIT v0.1 (together with a brief note of Li et al. (2015) [1]), which is the first NGS metagenome assembler that can assemble genome sequences from metagenomic datasets of hundreds of Giga base-pairs (bp) in a time- and memory-efficient manner on a single server. The core of MEGAHIT is an efficient parallel algorithm for constructing succinct de Bruijn Graphs (SdBG), implemented on a graphical processing unit (GPU). The software has been well received by the assembly community, and there is interest in how to adapt the algorithms to integrate popular assembly practices so as to improve the assembly quality, as well as how to speed up the software using better CPU-based algorithms (instead of GPU). In this paper we first describe the details of the core algorithms in MEGAHIT v0.1, and then we show the new modules to upgrade MEGAHIT to version v1.0, which gives better assembly quality, runs faster and uses less memory. For the Iowa Prairie Soil dataset (252Gbp after quality trimming), the assembly quality of MEGAHIT v1.0, when compared with v0.1, has a significant improvement, namely, 36% increase in assembly size and 23% in N50. More interestingly, MEGAHIT v1.0 is no slower than before (even running with the extra modules). This is primarily due to a new CPU-based algorithm for SdBG construction that is faster and requires less memory. Using CPU only, MEGAHIT v1.0 can assemble the Iowa Prairie Soil sample in about 43h, reducing the running time of v0.1 by at least 25% and memory usage by up to 50%. MEGAHIT v1.0, exhibiting a smaller memory footprint, can process even larger datasets. The Kansas Prairie Soil sample (484Gbp), the largest publicly available dataset, can now be assembled using no more than 500GB of memory in 7.5days. The assemblies of these datasets (and other large metgenomic datasets), as well as the software, are available at the website https://hku-bal.github.io/megabox.
宏基因组学的研究从低成本、高通量测序技术中受益匪浅，然而，由此产生的海量数据使得从头组装等分析消耗过多的计算资源。2014年末，我们发布了MEGAHIT v0.1（同时附带Li等人（2015年）[1]的简短说明），它是首个能在单台服务器上以高效利用时间和内存的方式，从数百吉碱基对（bp）的宏基因组数据集中组装基因组序列的二代测序（NGS）宏基因组组装器。MEGAHIT的核心是一种用于构建简洁德布鲁因图（SdBG）的高效并行算法，该算法在图形处理单元（GPU）上实现。该软件已受到组装领域的广泛认可，人们感兴趣的是如何调整算法以整合流行的组装方法来提高组装质量，以及如何使用更好的基于CPU的算法（而非GPU）来加速软件。在本文中，我们首先描述MEGAHIT v0.1中核心算法的细节，然后展示将MEGAHIT升级到v1.0版本的新模块，v1.0版本具有更好的组装质量、更快的运行速度且内存使用更少。对于爱荷华草原土壤数据集（质量修剪后为252Gbp），与v0.1相比，MEGAHIT v1.0的组装质量有显著提升，即组装大小增加36%，N50增加23%。更有趣的是，MEGAHIT v1.0并不比以前慢（即使运行额外的模块）。这主要归功于一种新的基于CPU的SdBG构建算法，该算法更快且所需内存更少。仅使用CPU，MEGAHIT v1.0就能在约43小时内组装爱荷华草原土壤样本，将v0.1的运行时间至少减少25%，内存使用最多减少50%。MEGAHIT v1.0内存占用更小，能够处理甚至更大的数据集。堪萨斯草原土壤样本（484Gbp），即最大的公开可用数据集，现在可以在7.5天内使用不超过500GB的内存进行组装。这些数据集（以及其他大型宏基因组数据集）的组装结果和该软件可在网站https://hku-bal.github.io/megabox上获取。
