Vasimuddin, M. | bioRxiv Science

bioRxiv2024

Accelerating whole-genome alignment in the age of complete genome assemblies

Recent advancements in long-read sequencing and assembly methods have ushered in an era of high-quality genome assemblies. Modern assemblies commonly feature megabase-long sequences frequently spanning entire chromosomes. The increase in the assembly contiguity and the reduced number of assembly contigs also implies that whole-genome alignment is no longer an embarrassingly parallel problem. The conventional method of aligning sequences of the query genome in parallel is to utilize a single thread per sequence. This results in poor CPU utilization and long runtimes. In this work, we designed optimizations to accelerate whole-genome alignment on multi-core processors and implemented them in a commonly used aligner, minimap2. Our improvements include a fine-grained parallel chaining method and a fast mechanism for differentiating primary and secondary chains. Our approach accelerates alignment of human, plant, and primate genomes by 1.6x to 7.2x without compromising accuracy.

bioinformatics↗

bioRxiv2018

Identification of Significant Computational Building Blocks through Comprehensive Deep Dive of NGS Secondary Analysis Methods

Rapid advancements in next generation sequencing technologies have greatly improved the throughput of sequencing and reduced the cost to under $1000 per genome propelling ambitious projects across the globe that are pursuing sequencing million or more genomes. In addition, the sequencing throughput is increasing and the cost is decreasing at a rate much faster than the Moores law. This necessitates equivalent rate of acceleration of NGS secondary analysis that assembles the reads into full genomes and identifies variants between genomes. Conventional improvement in hardware can at best help accelerate this according to the Moores law if the corresponding software is able to use the hardware efficiently. This is currently not the case for majority of the dozens of software tools used for NGS secondary analysis. Thus, to keep pace with the rate of advancement of sequencers, we need - 1) hardware that is designed taking into account the computational requirements of NGS secondary analysis and 2) software tools that use the hardware efficiently.\n\nIn this work, we take the first step towards that goal by identifying the computational requirements of NGS secondary analysis. We surveyed dozens of software tools from all the three major problems in secondary analysis - sequence mapping, de novo assembly, and variant calling - to select seven popular tools and a workflow for an in depth analysis. We performed runtime profiling of the tools using multiple real datasets to find that the majority of the runtime is dominated by just four building blocks - Smith Waterman alignment, FM-index based sequence search, Debruijn graph construction and traversal and pairwise hidden markov model algorithm. Together, these building blocks cover 80.5%-98.2% of the runtime for sequence mapping, 63.9%-99.4% of the runtime for De novo assembly, and 72%-93% of the runtime for variant calling. The beauty of this result is that by just tailoring our software and hardware for these building blocks, we can get a major performance improvement of NGS secondary analysis.

genomics↗