Scalable Genome Assembly through Parallel de Bruijn Graph Construction for Multiple k-mers
Kanak Mahadik1, Christopher Wright2, Milind Kulkarni2
1Adobe Research, San Jose, USA. mahadik@adobe.com.
Scientific Reports
|October 18, 2019
Summary
ScalaDBG accelerates genome assembly by building de Bruijn graphs (DBGs) in parallel, unlike sequential methods. This novel approach significantly speeds up the assembly of complex genomes with high accuracy.
Area of Science:
- Genomics
- Bioinformatics
- Computational Biology
Background:
- High-throughput sequencing generates vast amounts of genomic data.
- Efficient de novo genome assembly is crucial for biological research.
- Current de Bruijn graph assemblers face scalability and speed limitations due to sequential k-value iteration.
Purpose of the Study:
- To develop a parallel and scalable de novo genome assembly algorithm.
- To overcome the speed limitations of existing de Bruijn graph assemblers.
- To improve the efficiency of complex genome assembly.
Main Methods:
- Proposed ScalaDBG, a novel algorithm that builds de Bruijn graphs (DBGs) for distinct k-values in parallel.
- Implemented a mechanism to 'patch' higher k-valued graphs with contigs from lower k-valued graphs.
- Leveraged multi-level parallelism for both intra-node (all cores) and inter-node (multiple nodes) scaling.
Main Results:
- ScalaDBG demonstrates significantly faster genome assembly compared to IDBA-UD.
- Achieved comparable accuracy to existing methods on diverse datasets.
- Showcased a 6.8X speedup for a highly complex genome assembly.
Conclusions:
- ScalaDBG offers a faster and scalable solution for de novo genome assembly.
- The parallelized approach and graph patching mechanism effectively address computational bottlenecks.
- This advancement facilitates quicker and more efficient analysis of complex genomes.
Related Concept Videos
03:36Genome Annotation and Assembly
20.4K
The genome refers to all of the genetic material in an organism. It can range from a few million base pairs in microbial cells to several billion base pairs in many eukaryotic organisms. Genome assembly refers to the process of taking the DNA sequencing data and putting it all back together in a correct order to create a close representation of the original genome. This is followed by the identification of functional elements on the newly assembled genome, a process called genome annotation.
20.4K
01:05Maxam-Gilbert Sequencing
12.5K
In the same year as the discovery of the Sanger sequencing method, another group of scientists, Allan Maxam and Walter Gilbert, demonstrated their chemical-cleavage method for DNA sequencing. The Maxam-Gilbert method relies on using different chemicals that can cleave the DNA sequence at specific sites, the separation of resulting DNA fragments of variable size using electrophoresis, and deciphering the DNA sequence from the resulting gel bands.
Challenges of the Maxam-Gilbert Method
The...
Challenges of the Maxam-Gilbert Method
The...
12.5K
02:54Evolutionary Relationships through Genome Comparisons
6.8K
Genome comparison is one of the excellent ways to interpret the evolutionary relationships between organisms. The basic principle of genome comparison is that if two species share a common feature, it is likely encoded by the DNA sequence conserved between both species. The advent of genome sequencing technologies in the late 20th century enabled scientists to understand the concept of conservation of domains between species and helped them to deduce evolutionary relationships across diverse...
6.8K
01:57Sanger Sequencing
772.6K
DNA sequencing is a fundamental technique that is routinely used in the biological sciences. This method can be applied to a range of questions at different scales - from the sequencing of a cloned DNA fragment or the study of a mutation in a gene up to whole-genome sequencing. However, despite the widespread use of sequencing today, it was not until 1977 that Fredrick Sanger and his collaborators developed the chain-termination method to decode DNA sequences. It relies on the separation of a...
772.6K