An Extended Genovo Metagenomic Assembler by Incorporating Paired-End Information


Metagenomes present assembly challenges, when assembling multiple genomes from mixed reads of multiple species. An assembler for single genomes can’t adapt well when applied in this case. A metagenomic assembler, Genovo, is a de novo assembler for metagenomes under a generative probabilistic model. Genovo assembles all reads without discarding any reads in a preprocessing step, and is therefore able to extract more information from metagenomic data and, in principle, generate better assembly results. Paired end sequencing is currently widely-used yet Genovo was designed for 454 single end reads. In this research, we attempted to extend Genovo by incorporating paired-end information, named Xgenovo, so that it generates higher quality assemblies with paired end reads.

First, we extended Genovo by adding a bonus parameter in the Chinese Restaurant Process used to get prior accounts for the unknown number of genomes in the sample. This bonus parameter intends for a pair of reads to be in the same contig and as an effort to solve chimera contig case. Second, we modified the sampling process of the location of a read in a contig. We used relative distance for the number of trials in the symmetric geometric distribution instead of using distance between the offset and the center of contig used in Genovo. Using this relative distance, a read sampled in the appropriate location has higher probability. Therefore a read will be mapped in the correct location.

Results of extensive experiments on simulated metagenomic datasets from simple to complex with species coverage setting following uniform and lognormal distribution showed that Xgenovo can be superior to the original Genovo and the recently proposed metagenome assembler for 454 reads, MAP. Xgenovo successfully generated longer N50 than Genovo and MAP while maintaining the assembly quality even for very complex metagenomic datasets consisting of 115 species. Xgenovo also demonstrated the potential to decrease the computational cost. This means that our strategy worked well. The software and all simulated datasets are publicly available online at

Afiahayati   afia{at}dna{dot}bio{dot}keio{dot}ac{dot}jp 
Kengo Sato satoken{at}bio{dot}keio{dot}ac{dot}jp 
Yasubumi Sakakibara yasu{at}bio{dot}keio{dot}ac{dot}jp 

Cite "An Extended Genovo" as :
Afiahayati, Sato K, Sakakibara Y. (2013) An extended genovo metagenomic assembler by incorporating paired-end information. PeerJ 1:e196

Published works of the past 12 months related to this research
  1. Lai B, Ding R, Li Y, Duan L, Zhu H: “A de novo metagenomic assembly program for 
    shotgun DNA reads”. Bioinformatics 2012, 28(11):1455–1462.
  2. Mende DR, Waller AS, Sunagawa S, J¨arvelin AI, Chan MM, Arumugam M, Raes J, Bork P: “Assessment of Metagenomic Assembly Using Simulated Next Generation Sequencing Data”. PLoS ONE 2012, 7(2): e31386:doi:10.1371/journal.pone.0031386
  3. Nagarajan N, Pop M: “Sequence assembly demystified”. Nature Reviews Genetics 2013, 14:157–167 doi:10.1038/nrg3367.
  4. Namiki T, Hachiya T, Tanaka H, Sakakibara Y: "MetaVelvet: an extension of Velvet assembler to de novo metagenome assembly from short sequence reads". Nucleic Acids Res. 2012, 40(20):e155.
  5. Peng Y, Leung HC, Yiu SM, Chin FY: "IDBA-UD: a de novo assembler for single-cell and metagenomic sequencing data with highly uneven depth". Bioinformatics 2012, 28(11):1420–1428.