Exploiting sparseness in de novo genome assembly

Area of Science:

• Genomics
• Bioinformatics
• Computational Biology

Background:

• De novo genome assembly requires substantial computational resources, particularly memory, limiting its application to high-performance computing environments.
• Existing assembly graph algorithms face challenges with large datasets due to high memory demands.

Purpose of the Study:

• To develop a memory-efficient algorithm for de novo genome assembly.
• To enable genome assembly on standard computing hardware, such as laptops.

Main Methods:

• Construction of a sparse assembly graph storing a fraction of k-mers and their links.
• Implementation of the sparse graph concept in a software package, SparseAssembler.
• Utilizing a novel sparse k-mer graph structure derived from the de Bruijn graph.

Main Results:

• Demonstrated de novo assembly of moderately-sized genomes (~500 M) on a laptop.
• Achieved approximately 90% memory savings compared to traditional methods.
• Maintained high assembly accuracy and competitive speed.

Conclusions:

• Sparse assembly graphs offer a viable solution for memory-intensive genome assembly tasks.
• SparseAssembler facilitates accessible de novo genome assembly on common hardware.
• This method democratizes genome assembly by reducing computational barriers.