Abstract
Sequence alignment algorithms are a basic and critical component of many bioinformatics fields. With rapid development of sequencing technology, the fast growing reference database volumes and longer length of query sequence become new challenges for sequence alignment. However, the algorithm is prohibitively high in terms of time and space complexity. In this paper, we present DSA, a scalable distributed sequence alignment system that employs Spark to process sequences data in a horizontally scalable distributed environment, and leverages data parallel strategy based on Single Instruction Multiple Data (SIMD) instruction to parallelize the algorithm in each core of worker node. The experimental results demonstrate that 1) DSA has outstanding performance and achieves up to 201x speedup over SparkSW. 2) DSA has excellent scalability and achieves near linear speedup when increasing the number of nodes in cluster.
Introduction
Sequence alignment—the process of identifying similarities between DNA, RNA, or protein sequences—is the backbone of modern bioinformatics. However, the field is currently facing a "data deluge." Thanks to Next-Generation Sequencing (NGS), the cost of sequencing is dropping faster than Moore’s Law, leading to an exponential increase in genomic data.
The gold standard for local alignment is the Smith-Waterman (SW) algorithm. While highly accurate, SW is computationally expensive, with time and memory requirements that grow quadratically relative to sequence length. Existing distributed frameworks like SparkSW attempted to solve this using Apache Spark, but they often suffer from poor I/O performance, high network overhead, and a failure to leverage the low-level parallel processing capabilities of modern CPUs.
System Architecture
DSA was developed to bridge the gap between high-level distributed frameworks and low-level hardware acceleration. Its architecture consists of three key pillars:
- Hybrid Parallelism (Spark + SIMD): DSA uses Apache Spark to distribute data across a cluster (horizontal scaling). Within each worker node, it uses SIMD instructions (like SSE2 and AVX2) to process multiple data points in a single CPU cycle (vertical scaling). Since Spark is JVM-based and SIMD libraries are typically written in C, the system implements a Mediator using the Java Native Interface (JNI) to allow Spark to invoke high-performance C libraries like SSW and Parasail.
- Memory-Centric Storage (Alluxio): Instead of relying on traditional disk-based HDFS, which creates I/O bottlenecks, DSA employs Alluxio, a memory-speed distributed file system. This allows worker nodes to serve data from local RAM, drastically reducing network traffic and disk latency.
- Efficient Top-K Filtering: In bioinformatics, researchers often only care about the "Top-K" best matches. DSA replaces the standard, expensive Spark shuffle/sort approach with a more efficient algorithm. It uses a local
quickselecton each partition followed by a global reduction, reducing the time complexity and avoiding unnecessary data movement across the network.
Performance and Scalability
To evaluate DSA, the system was tested on a local cluster of 8 nodes against the previous state-of-the-art, SparkSW. The datasets included reference databases (R1–R10) ranging up to 16 GB and query sequences (Q1–Q10) up to 4,096 characters in length.
The results demonstrate massive performance gains. DSA outperformed SparkSW by up to 122x when scaling the reference database size and up to 201x when increasing query sequence lengths. Furthermore, the system demonstrated near-linear scalability. When the number of nodes in the cluster was increased from 1 to 8, the performance increased almost proportionally across various alignment types, including Smith-Waterman (DSW), Needleman-Wunsch (DNW), and Semi-Global (DSG) alignments.
Conclusion
DSA proves that combining high-level distributed scheduling with low-level hardware optimization is a viable path for large-scale bioinformatics. By addressing both computational complexity (via SIMD) and I/O bottlenecks (via Alluxio), the system achieves significant speedups while maintaining excellent scalability. Future work will focus on expanding support for newer instruction sets like AVX-512 and optimizing performance in elastic cloud environments.
Summary updated