Accelerating DNA Pattern Matching: A Parallel Computing Study Using Consumer Hardware

Saadat Hussain; Aliza Salman; Karan Kumar; Arapna Bai; Pooja Kumari; Khalid Rasheed Shaikh; Syed Samar Yazdani

doi:10.33411/IJIST/ojs1829

Authors

Saadat Hussain Department of Computer Science, Shaheed Zulfiqar Ali Bhutto Institute of Science and Technology (SZABIST), Karachi, Pakistan
Aliza Salman Department of Computer Science, Shaheed Zulfiqar Ali Bhutto Institute of Science and Technology (SZABIST), Karachi, Pakistan
Karan Kumar Department of Computer Science, Shaheed Zulfiqar Ali Bhutto Institute of Science and Technology (SZABIST), Karachi, Pakistan
Arapna Bai Department of Computer Science, Shaheed Zulfiqar Ali Bhutto Institute of Science and Technology (SZABIST), Karachi, Pakistan
Pooja Kumari Department of Computer Science, Shaheed Zulfiqar Ali Bhutto Institute of Science and Technology (SZABIST), Karachi, Pakistan
Khalid Rasheed Shaikh Denning Karachi, Pakistan
Syed Samar Yazdani SZabist University

DOI:

https://doi.org/10.33411/IJIST/ojs1829

Keywords:

Bioinformatics, Parallel Computing, DNA Sequence Analysis, String Matching Algorithms, Multi-Core Processors, Performance Optimization, Genomic Databases

Abstract

The exponential growth of genomic databases has necessitated the development of efficient computational methods for DNA sequence pattern matching. Traditional sequential algorithms face significant performance bottlenecks when processing datasets containing millions of base pairs. This paper presents a comprehensive empirical evaluation of parallel computing strategies for accelerating DNA pattern matching on consumer-grade multi-core processors. Four fundamental string-matching algorithms—Naive Search, Knuth-Morris-Pratt (KMP), Boyer–Moore, and Suffix Array—were implemented with parallel processing capabilities and evaluated on synthetic DNA sequences ranging from 10 million to 100 million base pairs. Experiments were conducted on an AMD Ryzen 7 3800X processor utilizing an 8-thread data decomposition strategy. Our results demonstrate significant performance improvements: the parallelized Suffix Array achieved a speedup factor of 4.12x at 100 million bases compared to its sequential implementation, reducing execution time from 210 seconds to 51 seconds. The parallel Boyer-Moore algorithm maintained sub-second execution times even at maximum dataset sizes. Analysis of scalability characteristics reveals near-linear speedup up to 8 cores, with memory consumption scaling predictably to 17.8 GB at 100 million bases. These findings validate that high-performance genomic analysis is achievable on standard desktop workstations without requiring specialized supercomputing infrastructure, thereby democratizing access to large-scale bioinformatics research capabilities. Experiments were repeated five times per configuration; results are reported as mean values with dispersion indicators (standard deviation, coefficient of variation) and 95% confidence intervals. At 100 million bases, observed parallel speedups across the evaluated algorithms ranged from 4.12× to 5.84×, and the Suffix Array runtime decreased from 210,353±3,245 ms (95% CI ±2,842 ms) to 51,018±892 ms (95% CI ±781 ms). To formalize comparative significance, sequential vs. parallel runtimes were assessed using paired statistical tests across the five repeated runs for each algorithm. Paired t-tests confirmed statistically significant reductions in runtime for all evaluated algorithms (p < 0.01), and one-way ANOVA indicated significant performance differences across the four algorithms (F = 12.45, p < 0.001).

References

D. Gusfield, “Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology,” Algorithms Strings, Trees Seq., May 1997, doi: 10.1017/cbo9780511574931.

C. D. W. Saul B. Needleman, “A general method applicable to the search for similarities in the amino acid sequence of two proteins,” J. Mol. Biol., vol. 48, no. 3, pp. 443–45, 1970, [Online]. Available: https://www.sciencedirect.com/science/article/abs/pii/0022283670900574

“AMD ׀ together we advance_AI.” Accessed: Apr. 07, 2026. [Online]. Available: https://www.amd.com/en.html

“Sequencing technologies and hardware-accelerated parallel computing transform computational genomics research - PMC.” Accessed: Apr. 07, 2026. [Online]. Available: https://pmc.ncbi.nlm.nih.gov/articles/PMC10985184/

Mohammed Alser, Jeremy Rotman, Dhrithi Deshpande, Kodi Taraszka, Huwenbo Shi, Pelin Icer Baykal, “Technology dictates algorithms: recent developments in read alignment,” Genome Biol., vol. 22, 2021, [Online]. Available: https://link.springer.com/article/10.1186/s13059-021-02443-7

Safaa Diab, Amir Nassereldine, Mohammed Alser, Juan Gómez-Luna, Onur Mutlu, Izzat El Hajj, “A Framework for High-throughput Sequence Alignment using Real Processing-in-Memory Systems,” arXiv:2208.01243, 2023, [Online]. Available: https://arxiv.org/abs/2208.01243

Jamshed Khan, Tobias Rubel, Erin Molloy, Laxman Dhulipala & Rob Patro, “Fast, parallel, and cache-friendly suffix array construction,” Algorithms Mol. Biol., vol. 19, 2024, [Online]. Available: https://link.springer.com/article/10.1186/s13015-024-00263-5

E. Kohnert and C. Kreutz, “Computational Study Protocol: Leveraging Synthetic Data to Validate a Benchmark Study for Differential Abundance Tests for 16S Microbiome Sequencing Data,” F1000Research, vol. 13, 2025, doi: 10.12688/F1000RESEARCH.155230.2/DOI.

Izaskun Mallona , Charlotte Soneson, Ben Carrillo, Almut Lütge, Daniel Incicau, Reto Gerber, Anthony Sonrel, Mark D. Robinson, “Building a continuous benchmarking ecosystem in bioinformatics,” Plosone, 2025, doi: https://doi.org/10.1371/journal.pcbi.1013658.

“G^3SA: A GPU-Accelerated Gold Standard Genomics Library for End-to-End Sequence Alignment | Request PDF.” Accessed: Apr. 07, 2026. [Online]. Available: https://www.researchgate.net/publication/394867590_G3SA_A_GPU-Accelerated_Gold_Standard_Genomics_Library_for_End-to-End_Sequence_Alignment

Zeyu Xia, Canqun Yang, Chenchen Peng, Yifei Guo, Yufei Guo, Tao Tang & Yingbo Cui, “Fast noisy long read alignment with multi-level parallelism,” BMC Bioinformatics, vol. 26, no. 118, 2025, [Online]. Available: https://link.springer.com/article/10.1186/s12859-025-06129-w

H. Sadasivan, M. Maric, E. Dawson, V. Iyer, J. Israeli, and S. Narayanasamy, “Accelerating Minimap2 for Accurate Long Read Alignment on GPUs,” J. Biotechnol. Biomed., vol. 6, no. 1, 2023, doi: 10.26502/JBB.2642-91280067.

“Introduction to Algorithms, fourth edition - Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein - Google Books.” Accessed: Mar. 30, 2026. [Online]. Available: https://books.google.com.pk/books?id=HOJyzgEACAAJ&printsec=frontcover&redir_esc=y#v=onepage&q&f=false

“Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.” Accessed: Feb. 11, 2026. [Online]. Available: https://algs4.cs.princeton.edu/home/

D. E. Knuth, J. H. Morris, Jr., and V. R. Pratt, “Fast Pattern Matching in Strings,” SIAM J. Comput., vol. 6, no. 2, pp. 323–350, Jun. 1977, doi: 10.1137/0206024.

R. S. Boyer and J. S. Moore, “A Fast String Searching Algorithm,” Program. Tech., vol. 20, no. 10, 1977, [Online]. Available: https://www.cs.utexas.edu/~moore/publications/fstrpos.pdf

Udi Manber Gene Myers, Udi Manber, “Suffix arrays: a new method for on-line string searches,” SODA ’90 Proc. first Annu. ACM-SIAM Symp. Discret. algorithms, pp. 319–327, 1990, [Online]. Available: https://dl.acm.org/doi/10.5555/320176.320218

S. A. Pang Ko, “Space efficient linear time construction of suffix arrays,” J. Discret. Algorithms, vol. 3, no. 2–4, pp. 143–156, 2005, [Online]. Available: https://www.sciencedirect.com/science/article/pii/S1570866704000498

“Using OpenMP: Portable Shared Memory Parallel Programming - Barbara Chapman, Gabriele Jost, Ruud Van Der Pas - Google Books.” Accessed: Feb. 11, 2026. [Online]. Available: https://books.google.com.pk/books/about/Using_OpenMP.html?id=MeFLQSKmaJYC&redir_esc=y

M. J. . Quinn, “Parallel programming in C with MPI and openMP,” p. 529, 2004.

P. K. Essam Mansour, Amin Allam, Spiros Skiadopoulos, “ERA: Efficient Serial and Parallel Suffix Tree Construction for Very Long Strings,” Proc. VLDB Endow., 2011, [Online]. Available: https://arxiv.org/abs/1109.6884

Md Momin Al Aziz, Parimala Thulasiraman & Noman Mohammed, “Parallel and private generalized suffix tree construction and query on genomic data,” BMC Genomic Data, vol. 23, no. 45, 2022, [Online]. Available: https://link.springer.com/article/10.1186/s12863-022-01053-x

E. A. Sitaridi and K. A. Ross, “GPU-accelerated string matching for database applications,” VLDB J., vol. 25, no. 5, pp. 719–740, Oct. 2016, doi: 10.1007/s00778-015-0409-y.

S. F. Altschul, W. Gish, W. Miller, E. W. Myers, and D. J. Lipman, “Basic local alignment search tool,” J. Mol. Biol., vol. 215, no. 3, pp. 403–410, 1990, doi: 10.1016/S0022-2836(05)80360-2.

Abdullah Ammar Karcioglu, Hasan Bulut, “The WM-q multiple exact string matching algorithm for DNA sequences,” Comput. Biol. Med., vol. 136, no. 9, 2021, [Online]. Available: https://pubmed.ncbi.nlm.nih.gov/34333228/

“BLAST® Command Line Applications User Manual - NCBI Bookshelf.” Accessed: Apr. 07, 2026. [Online]. Available: https://www.ncbi.nlm.nih.gov/books/NBK279690/

“Metagenomics - BLAST word-size.” Accessed: Apr. 07, 2026. [Online]. Available: https://www.metagenomics.wiki/tools/blast/default-word-size

“BLAST: Basic Local Alignment Search Tool.” Accessed: Feb. 11, 2026. [Online]. Available: https://blast.ncbi.nlm.nih.gov/Blast.cgi

“Bowtie2 - Bioinformatics Notebook.” Accessed: Apr. 07, 2026. [Online]. Available: https://rnnh.github.io/bioinfo-notebook/docs/bowtie2.html

B. Langmead and S. L. Salzberg, “Fast gapped-read alignment with Bowtie 2,” Nat. Methods 2012 94, vol. 9, no. 4, pp. 357–359, Mar. 2012, doi: 10.1038/nmeth.1923.

Jonathan LoTempio, Emmanuele Delot, “Benchmarking long-read genome sequence alignment tools for human genomics applications,” PeerJ, 2023, [Online]. Available: https://pubmed.ncbi.nlm.nih.gov/38130927/