Sketch-Based Algorithms for Genome-Scale Mapping

Tazin Rahman

After nearly four decades of breakthroughs in sequencing technologies and corresponding advances in genome assembly algorithms, genome biology is entering a new era of fully phased, chromosome-scale, telomere-to-telomere (T2T) assemblies. Long-read sequencing technologies, which obtain DNA fragments exceeding 10 kbp in length, are a key to this progress and continue to evolve rapidly. The latest high fidelity (HiFi) sequencing technologies offer a significant improvement over earlier error-prone PacBio or ONT platforms, delivering reads with high accuracy (99.9%). Given these sequencing reads, genome assemblers reconstruct genomes \textit{de novo}. Billions of reads can now be generated within hours, resulting in petabytes of data stored in sequence read archives. This massive volume of data creates unprecedented opportunities for genome assembly while simultaneously demanding highly efficient parallelization of the underlying assembly steps to keep pace with data growth. Classical long-read assemblers produce assemblies directly from long reads, necessitating the detection of overlaps between reads. Hybrid assembly workflows provide a way to combine partially constructed assemblies (or contigs) with newly sequenced long reads in order to generate improved and near-complete genomic scaffolds. Under either setting, the main computational bottleneck is the step of mapping the long reads---against other long reads or pre-constructed contigs. While many tools perform the mapping step using computationally intensive alignments, designing alignment-free approaches and efficiently parallelizing this step are essential for large-scale computations. In this dissertation, we visit the generic problem of mapping long reads to a database of subject sequences in a scalable, fast, and accurate manner. We present new methods for mapping long reads using sequence sketching, which generate a compact representation of longer sequences. Instead of comparing sequences directly, sketches allow comparisons to be performed on compact representations, thereby reducing both computational time and memory requirements in downstream applications. To address the classical read mapping, we make the following contributions: i) JEM-mapper- an efficient parallel algorithmic workflow that uses a novel sketch-based similarity estimation technique (minimizer-based Jaccard estimator or JEM sketch) to perform alignment-free mapping of long reads. ii) MHSketch- an efficient mapping algorithm that employs a MinHash-based downsampling strategy to construct a flexible sketch library using a sketching method of choice, while reducing sketch density and thereby lowering memory consumption. We present distributed-memory implementations for both of our algorithms. In addition, we implement an MPI+OpenMP version of both of the algorithms to enable parallelism at both the distributed-memory and shared-memory levels. We provide an extensive performance and qualitative evaluation of the proposed methods on a wide range of datasets, spanning bacterial, human, and complex plant genomes, and compare them against state-of-the-art long-read mapping tools. Our experiments reveal that JEM-mapper matches the accuracy of state-of-the-art long read mappers while reducing time-to-solution (speedups between 5x to 13x). MHSketch achieves high-quality long read mapping while drastically reducing memory usage (>90% savings) compared to state-of-the-art tools.

Sketch-Based Algorithms for Genome-Scale Mapping

Files and links (1)

Abstract

Metrics

Details