FastEtch: A Fast Sketch-Based Assembler for Genomes.

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• De novo genome assembly reconstructs genomes from sequencing reads.
• Next-Generation Sequencing (NGS) generates massive datasets, demanding significant computational resources.
• De Bruijn graphs are central to short-read assembly, but their construction and traversal are computationally intensive.

Purpose of the Study:

• To present FastEtch, a novel algorithm for efficient de novo genome assembly.
• To reduce the computational burden (memory and time) associated with de Bruijn graph construction and traversal.
• To explore the trade-offs between assembly performance and output quality using an approximate graph approach.

Main Methods:

• Developed FastEtch, an algorithm employing sketching with Count-Min sketch to build an approximate de Bruijn graph.
• Implemented an approach that stores information for selected nodes and detects contributing edges on-the-fly.
• Created multi-threaded parallel versions for enhanced scalability.

Main Results:

• FastEtch significantly improves execution time and memory footprint compared to traditional assemblers.
• Experimental results on diverse genomes (E. coli, Yeast, C. elegans, Human) demonstrate competitive performance.
• The method achieves a favorable time-memory-quality trade-off against state-of-the-art genome assemblers.

Conclusions:

• FastEtch offers a computationally efficient approach to de novo genome assembly.
• The use of sketching provides a viable strategy for handling large sequencing datasets.
• This method presents a promising alternative for researchers seeking to balance speed, memory usage, and assembly accuracy.