Summary: MEGAHIT is a NGS de novo assembler for assembling large and complex metagenomics data in a time- and cost-efficient manner. It finished assembling a soil metagenomics dataset with 252 Gbps in 44.1 and 99.6 h on a single computing node with and without a graphics processing unit, respectively. MEGAHIT assembles the data as a whole, i.e. no pre-processing like partitioning and normalization was needed. When compared with previous methods on assembling the soil data, MEGAHIT generated a three-time larger assembly, with longer contig N50 and average contig length; furthermore, 55.8% of the reads were aligned to the assembly, giving a fourfold improvement. Availability and implementation: The source code of MEGAHIT is freely available at https://github.com/voutcn/megahit under GPLv3 license. Contact:rb@l3-bioinfo.com or twlam@cs.hku.hk Supplementary information: Supplementary data are available at Bioinformatics online.

We propose new succinct representations of ordinal trees and match various space/time lower bounds. It is known that any n -node static tree can be represented in 2 n + o ( n ) bits so that a number of operations on the tree can be supported in constant time under the word-RAM model. However, the data structures are complicated and difficult to dynamize. We propose a simple and flexible data structure, called the range min-max tree , that reduces the large number of relevant tree operations considered in the literature to a few primitives that are carried out in constant time on polylog-sized trees. The result is extended to trees of arbitrary size, retaining constant time and reaching 2 n + O ( n /polylog( n )) bits of space. This space is optimal for a core subset of the operations supported and significantly lower than in any previous proposal. For the dynamic case, where insertion/deletion (indels) of nodes is allowed, the existing data structures support a very limited set of operations. Our data structure builds on the range min-max tree to achieve 2 n + O ( n /log n ) bits of space and O (log n ) time for all operations supported in the static scenario, plus indels. We also propose an improved data structure using 2 n + O ( n log log n /log n ) bits and improving the time to the optimal O (log n /log log n ) for most operations. We extend our support to forests, where whole subtrees can be attached to or detached from others, in time O (log ^1+ϵ n ) for any ϵ > 0. Such operations had not been considered before. Our techniques are of independent interest. An immediate derivation yields an improved solution to range minimum/maximum queries where consecutive elements differ by ± 1, achieving n + O ( n /polylog( n )) bits of space. A second one stores an array of numbers supporting operations sum and search and limited updates, in optimal time O (log n /log log n ). A third one allows representing dynamic bitmaps and sequences over alphabets of size σ, supporting rank/select and indels, within zero-order entropy bounds and time O (log n log σ/(log log n ) ² ) for all operations. This time is the optimal O (log n /log log n ) on bitmaps and polylog-sized alphabets. This improves upon the best existing bounds for entropy-bounded storage of dynamic sequences, compressed full-text self-indexes, and compressed-space construction of the Burrows-Wheeler transform.