Linear time complexity de novo long read genome assembly with GoldRush.

Area of Science:

• Genomics
• Bioinformatics
• Computational Biology

Background:

• Current de novo long read genome assemblers rely on the Overlap-Layout-Consensus paradigm.
• The read-to-read overlap step is computationally expensive and requires significant RAM, limiting scalability for large datasets like the human genome.

Purpose of the Study:

• To develop a novel de novo long read genome assembly algorithm that overcomes the limitations of existing methods.
• To improve the efficiency and reduce the memory footprint of genome assembly.

Main Methods:

• Introduced GoldRush, a de novo long read genome assembly algorithm that utilizes a dynamic data structure.
• GoldRush foregoes all-vs-all sequence alignments, opting for a linear time complexity approach.
• Tested GoldRush on Oxford Nanopore Technologies long sequencing read datasets from human cell lines, rice, and tomato.

Main Results:

• Achieved assembly scaffold NGA50 lengths of 18.3-22.2 Mbp for human genomes.
• Obtained NGA50 lengths of 0.3 Mbp for rice and 2.6 Mbp for tomato genomes.
• Assembled each genome within a day using a maximum of 54.5 GB of RAM.

Conclusions:

• GoldRush demonstrates a scalable and memory-efficient paradigm for de novo long read genome assembly.
• The algorithm's performance across diverse genomes highlights its potential for large-scale genomic projects.
• This approach significantly reduces the computational resources required for high-quality genome assembly.