HINGE: Long-Read Assembly Achieves Optimal Repeat Resolution
Preprint
Abstract
Long-read sequencing technologies have the potential to produce gold-standard de novo genome assemblies, but fully exploiting error-prone reads to resolve repeats remains a challenge. Aggressive approaches to repeat resolution often produce mis-assemblies, and conservative approaches lead to unnecessary fragmentation. We present HINGE, an assembler that seeks to achieve optimal repeat resolution by distinguishing repeats that can be resolved given the data from those that cannot. This is accomplished by adding "hinges" to reads for constructing an overlap graph where only unresolvable repeats are merged. As a result, HINGE combines the error resilience of overlap-based assemblers with repeat-resolution capabilities of de Bruijn graph assemblers. HINGE was evaluated on the long-read bacterial datasets from the NCTC project. HINGE produces more finished assemblies than Miniasm and the manual pipeline of NCTC based on the HGAP assembler and Circlator. HINGE also allows us to identify 40 datasets where unresolvable repeats prevent the reliable construction of a unique finished assembly. In these cases, HINGE outputs a visually interpretable assembly graph that encodes all possible finished assemblies consistent with the reads, while other approaches such as the NCTC pipeline and FALCON either fragment the assembly or resolve the ambiguity arbitrarily.Keywords
All Related Versions
- Published version: Genome Research, 27 (5), 747.
This publication has 27 references indexed in Scilit:
- Reducing assembly complexity of microbial genomes with single-molecule sequencingGenome Biology, 2013
- Nonhybrid, finished microbial genome assemblies from long-read SMRT sequencing dataNature Methods, 2013
- Aggressive assembly of pyrosequencing reads with matesBioinformatics, 2008
- ALLPATHS: De novo assembly of whole-genome shotgun microreadsGenome Research, 2008
- The fragment assembly string graphBioinformatics, 2005
- A Whole-Genome Assembly of DrosophilaScience, 2000
- DNA physical mapping and alternating Eulerian cycles in colored graphsAlgorithmica, 1995
- Toward Simplifying and Accurately Formulating Fragment AssemblyJournal of Computational Biology, 1995
- Approximate string-matching with q-grams and maximal matchesTheoretical Computer Science, 1992
- A greedy approximation algorithm for constructing shortest common superstringsTheoretical Computer Science, 1988