Motivation: Metagenomic sequencing allows reconstruction of microbial genomes directly from environmental samples. Omega (overlap-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 generated based on minimum cost flow analysis of the overlap graph and then merged to contigs and scaffolds using mate-pair information. In comparison with 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 with 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 metagenomic datasets.
Availability And Implementation: Implemented in C++ with source code and binaries freely available at http://omega.omicsbio.org.
Download full-text PDF |
Source |
|---|---|
| http://dx.doi.org/10.1093/bioinformatics/btu395 | DOI Listing |
Publication Analysis
Top Keywords
Similar Publications
Omega: an overlap-graph de novo assembler for metagenomics.
Bioinformatics
October 2014
Computer Science and Mathematics Division, Oak Ridge National Laboratory, Oak Ridge, TN 37831 and U.S. Department of Energy, Joint Genome Institute, Walnut Creek, CA, 94598 USA.
Motivation: Metagenomic sequencing allows reconstruction of microbial genomes directly from environmental samples. Omega (overlap-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.
A memory-efficient data structure representing exact-match overlap graphs with application for next-generation DNA assembly.
Bioinformatics
July 2011
Department of Computer Science and Engineering, University of Connecticut, Storrs, CT 06269, USA.
Motivation: Exact-match overlap graphs have been broadly used in the context of DNA assembly and the shortest super string problem where the number of strings n ranges from thousands to billions. The length ℓ of the strings is from 25 to 1000, depending on the DNA sequencing technologies. However, many DNA assemblers using overlap graphs suffer from the need for too much time and space in constructing the graphs.
View Article and Find Full Text PDFTwo notes on genome rearrangement.
J Bioinform Comput Biol
April 2003
School of Computer Science, Tel Aviv University, Israel.
A central problem in genome rearrangement is finding a most parsimonious rearrangement scenario using certain rearrangement operations. An important problem of this type is sorting a signed genome by reversals and translocations (SBRT). Hannenhalli and Pevzner presented a duality theorem for SBRT which leads to a polynomial time algorithm for sorting a multi-chromosomal genome using a minimum number of reversals and translocations.
View Article and Find Full Text PDFWant AI Summaries of new PubMed Abstracts delivered to your In-box?
Enter search terms and have AI summaries delivered each week - change queries or unsubscribe any time!