A Scalable Distributed-Memory MPI Implementation of Smith-Waterman with Token-Passing Traceback
- 1University of Engineering and Technology, Lahore
Abstract
As genomic sequencing produces increasingly massive datasets, accurate local sequence alignment via the Smith-Waterman(SW) algorithm remains computationally prohibitive due to its space and quadratic time complexity O(mn). While parallelization addresses a path forward, existing MPI-based solutions present a critical bottleneck during the traceback phase, either omitting it entirely or gathering the entire direction matrix to a single root node, which severely limits scalability. To overcome this, we propose a fully distributed Message Passing Interface (MPI) implementation featuring a token passing traceback scheme. Our approach distributes the directional matrix across all participating ranks, reducing per-rank memory footprint from O(mn) to O(mn/p), thereby enabling the alignment of sequences far beyond the capacity of sequential or centralized parallel methods. We validate our method on real human DNA sequences (BRCA1, BRCA2, Titin, chr1, chr2) and synthetic datasets up to 50kx50k. Results demonstrate that this MPI implementation aligns 98kx98k real DNA (chr1xchr2) in 58.9160 seconds across 16 MPI processes, a task where the sequential baseline fails due to out-of-memory errors. We achieve best speedups on synthetic data of 19.30x (40kx40k, 16 MPI processes) and on real DNA data is 13.39x (BRCA1xTitin, 8 MPI processes), while capping per-rank memory for the largest dataset at just 573 MB. By enabling exact, memory-scalable alignment with fully distributed traceback on standard CPU MPI clusters, this work fills a critical gap in high-performance computational genomics.
Related
- Traditional Ecological Relationship Family sharing an abundant home within nature requires recurring mutual adaptation rather than the extraction of knowledge by passing visitors
- Genomic and ecological characterization of unclassified tetraploid Echinochloa plants distributed in northern Japan
- Distributed implantable microchips as wireless networks for neural sensing and stimulation
- Title: The Cyanobacterial dnaX Intein Encodes an Out-of-Frame Homing Endonuclease and is Sporadically Distributed in the Phylum
- Strategy-Dependent Recruitment of Distributed Cortical Circuits during Spatial Navigation
BibTeX
@misc{fatima2026scalable,
title = {{A Scalable Distributed-Memory MPI Implementation of Smith-Waterman with Token-Passing Traceback}},
author = {M. Fatima and W. Ali},
howpublished = {bioRxiv},
year = {2026},
month = sep,
doi = {10.64898/2026.09.08.750277},
url = {https://www.biorxiv.org/content/10.64898/2026.09.08.750277v1},
note = {CC BY-NC},
}
RIS
TY - UNPB
TI - A Scalable Distributed-Memory MPI Implementation of Smith-Waterman with Token-Passing Traceback
AU - M. Fatima
AU - W. Ali
PY - 2026
DA - 2026/09/08
PB - bioRxiv
DO - 10.64898/2026.09.08.750277
UR - https://www.biorxiv.org/content/10.64898/2026.09.08.750277v1
AB - As genomic sequencing produces increasingly massive datasets, accurate local sequence alignment via the Smith-Waterman(SW) algorithm remains computationally prohibitive due to its space and quadratic time complexity O(mn). While parallelization addresses a path forward, existing MPI-based solutions present a critical bottleneck during the traceback phase, either omitting it entirely or gathering the entire direction matrix to a single root node, which severely limits scalability. To overcome this, we propose a fully distributed Message Passing Interface (MPI) implementation featuring a token passing traceback scheme. Our approach distributes the directional matrix across all participating ranks, reducing per-rank memory footprint from O(mn) to O(mn/p), thereby enabling the alignment of sequences far beyond the capacity of sequential or centralized parallel methods. We validate our method on real human DNA sequences (BRCA1, BRCA2, Titin, chr1, chr2) and synthetic datasets up to 50kx50k. Results demonstrate that this MPI implementation aligns 98kx98k real DNA (chr1xchr2) in 58.9160 seconds across 16 MPI processes, a task where the sequential baseline fails due to out-of-memory errors. We achieve best speedups on synthetic data of 19.30x (40kx40k, 16 MPI processes) and on real DNA data is 13.39x (BRCA1xTitin, 8 MPI processes), while capping per-rank memory for the largest dataset at just 573 MB. By enabling exact, memory-scalable alignment with fully distributed traceback on standard CPU MPI clusters, this work fills a critical gap in high-performance computational genomics.
ER -