A Novel Approach for Accurate Sequence Assembly Using de Bruijn graphs
Preprint
Abstract
Sequence assembly methods are valuable for reconstructing genomes from shorter read fragments. Modern nucleic acid sequencing instruments produce quality scores associated with each reported base; however, these quality scores are not generally used as a core part of sequence assembly or alignment algorithms. Here, we leverage weighted de Bruijn graphs as graphical probability models representing the relative abundances and qualities of kmers within FASTQ-encoded observations. We then utilize these weighted de Bruijn graphs to identify alternate, higher-likelihood candidate sequences compared to the original observations, which are known to contain errors. By improving the original observations with these resampled paths, iteratively across increasing k-lengths, we can use this expectation-maximization approach to “polish” read sets from any sequencing technology according to the mutual information shared in the reads. We use this polishing approach to probabilistically correct simulated short- and long-read datasets of lower coverages and higher error rates than some algorithms can produce satisfactory assemblies for. We find that this approach corrects sequencing errors at rates that are able to produce error-free and nearly-error-free de Bruijn assembly graphs for simulated read-set challenges.Keywords
This publication has 45 references indexed in Scilit:
- metaFlye: scalable long-read metagenome assembly using repeat graphsNature Methods, 2020
- Complete, closed bacterial genomes from microbiomes using nanopore sequencingNature Biotechnology, 2020
- Assembly of long, error-prone reads using repeat graphsNature Biotechnology, 2019
- Errors in long-read assemblies can critically affect protein predictionNature Biotechnology, 2019
- Variation graph toolkit improves read mapping by representing genetic variation in the referenceNature Biotechnology, 2018
- MEGAHIT v1.0: A fast and scalable metagenome assembler driven by advanced methodologies and community practicesMethods, 2016
- High-Throughput Sequencing TechnologiesMolecular Cell, 2015
- How to apply de Bruijn graphs to genome assemblyNature Biotechnology, 2011
- The Original Michaelis Constant: Translation of the 1913 Michaelis–Menten PaperBiochemistry, 2011
- RNA-Seq: a revolutionary tool for transcriptomicsNature Reviews Genetics, 2009