FastEtch: A Fast Sketch-Based Assembler for Genomes

Priyanka Ghosh; Ananth Kalyanaraman

doi:10.1109/TCBB.2017.2737999

Back

FastEtch: A Fast Sketch-Based Assembler for Genomes

Journal article

Open access

FastEtch: A Fast Sketch-Based Assembler for Genomes

Priyanka Ghosh and Ananth Kalyanaraman

IEEE/ACM transactions on computational biology and bioinformatics, Vol.16(4), pp.1091-1106

07/2019

DOI: https://doi.org/10.1109/TCBB.2017.2737999

Handle:

https://hdl.handle.net/2376/115992

PMID: 28910776

Files and links (1)

url

https://doi.org/10.1109/TCBB.2017.2737999View

Published (Version of record) Open

Abstract

count-min sketch

Sequential analysis

Image edge detection

Memory management

Genomics

DNA

de Bruijn graph

Data structures

Approximation algorithms

Genome assembly

approximation methods

De novo genome assembly describes the process of reconstructing an unknown genome from a large collection of short (or long) reads sequenced from the genome. A single run of a Next-Generation Sequencing (NGS) technology can produce billions of short reads, making genome assembly computationally demanding (both in terms of memory and time). One of the major computational steps in modern day short read assemblers involves the construction and use of a string data structure called the de Bruijn graph. In fact, a majority of short read assemblers build the complete de Bruijn graph for the set of input reads, and subsequently traverse and prune low-quality edges, in order to generate genomic "contigs"-the output of assembly. These steps of graph construction and traversal, contribute to well over 90 percent of the runtime and memory. In this paper, we present a fast algorithm, FastEtch, that uses sketching to build an approximate version of the de Bruijn graph for the purpose of generating an assembly. The algorithm uses Count-Min sketch, which is a probabilistic data structure for streaming data sets. The result is an approximate de Bruijn graph that stores information pertaining only to a selected subset of nodes that are most likely to contribute to the contig generation step. In addition, edges are notstored; instead that fraction which contribute to our contig generation are detected on-the-fly. This approximate approach is intended to significantly improve performance (both execution time and memory footprint) whilst possibly compromising on the output assembly quality. We present two main versions of the assembler-one that generates an assembly, where each contig represents a contiguous genomic region from one strand of the DNA, and another that generates an assembly, where the contigs can straddle either of the two strands of the DNA. For further scalability, we have implemented a multi-threaded parallel code. Experimental results using our algorithm conducted on E. coli, Yeast, C. elegans, and Human (Chr2 and Chr2+3) genomes show that our method yields one of the best time-memory-quality trade-offs, when compared against many state-of-the-art genome assemblers.

Metrics

11 Record Views

Details

Title: FastEtch: A Fast Sketch-Based Assembler for Genomes
Creators: Priyanka Ghosh - Washington State University, Pullman, WA
Ananth Kalyanaraman - Washington State University, Pullman, WA
Publication Details: IEEE/ACM transactions on computational biology and bioinformatics, Vol.16(4), pp.1091-1106
Academic Unit: Electrical Engineering and Computer Science, School of
Publisher: IEEE
Grant note: DE-AC02-05CH11231 / U.S. Department of Energy (10.13039/100000015) DE-SC-0006516 / U.S. Department of Energy (10.13039/100000015)
Identifiers: 99900547331601842
Language: English
Resource Type: Journal article