1 Genome Analysis Omega: an Overlap-graph de novo Assembler for Metagenomics

Motivation: Metagenomic sequencing allows reconstruction of mi-crobial genomes directly from environmental samples. Omega (over-lap-graph metagenome assembler) was developed for assembling and scaffolding Illumina sequencing data of microbial communities. Results: Omega found overlaps between reads using a prefix/suffix hash table. The overlap graph of reads was simplified by removing transitive edges and trimming short branches. Unitigs were generat-ed based on minimum-cost flow analysis of the overlap graph and then merged to contigs and scaffolds using mate-pair information. In comparison to three de Bruijn graph assemblers (SOAPdenovo, IDBA-UD, and MetaVelvet), Omega provided comparable overall performance on a HiSeq 100-bp dataset and superior performance on a MiSeq 300-bp dataset. In comparison to Celera on the MiSeq dataset, Omega provided more continuous assemblies overall using a fraction of the computing time of existing Overlap-Layout-Consensus assemblers. This indicates Omega can more efficiently assemble longer Illumina reads, and at deeper coverage, for meta-genomic datasets. Availability and Implementation: Implemented in C++ with source code and binaries freely available a