PaSGAL

PaSGAL performs local sequence alignment of DNA reads to directed acyclic sequence graphs, including variation graphs and splicing graphs, to enable accurate genotyping and variant-aware read mapping.

Key Features:

• Parallel algorithm: Implements a multicore parallel algorithm that leverages single-instruction multiple-data (SIMD) operations to accelerate sequence-to-graph alignment.
• Blocked score-matrix computation: Uses a blocked approach for computing the dynamic-programming score matrix to improve memory locality and exploit inter-task parallelism.
• Scalability and performance: Demonstrates near-linear weak and strong scaling up to 48 cores, achieves 317 billion cell updates per second (GCUPS) on a 48-core Intel Xeon Skylake processor, and reduces runtime to about three hours for aligning high-coverage long (PacBio/ONT) or short (Illumina) reads to a human variation graph with 10 million vertices.

Scientific Applications:

• Genotyping and variant detection: Enables optimal alignment of sequencing data to variation graphs to support improved genetic variant detection and genotyping.
• Graph-based read mapping for genomics: Supports alignment of reads to annotated references such as splicing and variation graphs for studies of genetic diversity and disease mechanisms.

Methodology:

Finds the best-matching path in a directed acyclic string graph for an input query sequence using parallelized dynamic programming with a blocked score-matrix computation that exploits multicore and SIMD parallelism.