Open-access journal article · 2023
Comparative Analysis of Bit-Parallel String Pattern Matching Algorithms for Biological Sequences
Operational Research in Engineering Sciences: Theory and Applications, 6(1), pp. 322–331 · Published
The journal prints the DOI 10.31181/oresta/0601131 for this article, but that DOI is not registered with a DOI agency and does not currently resolve, so it is not used as an identifier here. Use the publisher page above.
Summary
Muhammad et al. (2023) reviewed the literature on bit-parallel string matching for biological sequences such as DNA, RNA and protein, comparing 11 published algorithms by time complexity, drawbacks and application areas. They conclude that bit-parallelism is versatile for biological sequence analysis but is mostly hampered by the requirement that the pattern length be less than or equal to the computer word length, with the BNDM (Backward Non-deterministic Matching) family most efficient within that limit. They add that optimal performance requires designing algorithms around the nature of the target sequence.
Practical implication. Researchers analyzing DNA, RNA or protein sequences can use the comparison of 11 bit-parallel algorithms to select the most appropriate method for a particular application area.
- The Problem
- Bioinformatics needs fast pattern matching over DNA, RNA and protein sequences, but the many bit-parallel string-matching algorithms have not been compared side by side for biological data.
- The Methodology
- Comparative literature review of bit-parallel exact and approximate string matching algorithms (Shift-Or/Shift-And, BNDM, TNDM, SBNDM and parameterized variants) with a tabulated comparison of 11 algorithms by complexity, drawbacks and application area.
- The Core Finding
- A comparison of 11 bit-parallel algorithms shows that bit-parallelism is versatile for biological sequence analysis but is limited mainly by the requirement that pattern length not exceed the computer word length. The BNDM family is most efficient within that limit, and optimal performance requires designing algorithms around the nature of the target sequence.
- The Citation
- Muhammad, M. Y., Fonkam, M., Thandekatu, S. G., Rakshit, S., & Vajjhala, R. N. (2023). Comparative Analysis of Bit-Parallel String Pattern Matching Algorithms for Biological Sequences. Operational Research in Engineering Sciences: Theory and Applications, 6(1), 322–331. https://oresta.org/article-view/?id=554
The summary, key findings, methods, implications and relevance notes on this page are this website’s own description of the paper, written from the published abstract and text. The official abstract and citation details are given further down.
Key findings
- Finding 1. The review compares 11 published bit-parallel string matching algorithms for biological sequences by performance, drawback and application area.
- Finding 2. The comparison reports, for example, O(n⌈m/w⌉) worst-case time for one Grabowski and Fredriksson (2008) algorithm (not good for long sequences), and pre-processing O(mδ) with searching O(nm) for Zhang et al. (2009), whose performance degrades with changes in pattern length.
- Finding 3. According to the review, parameterized algorithms such as Prasad and Agarwal (2008) and Prasad (2016) run in linear time and are suited to parameterized strings across all biosequences.
- Finding 4. The review finds that the BNDM (Backward Non-deterministic Matching) family is most efficient when the pattern length is not longer than the computer word size.
- Finding 5. The authors conclude that the application of bit-parallelism to biological sequence analysis is mostly hampered by the limitation that pattern length must be less than or equal to the computer word length.
- Finding 6. The review notes that implementing benchmark bit-parallel algorithms on RNA sequences without modification was theoretically bad, because RNA and protein fold into complex structures and their nucleotide strings are complementary.
- Finding 7. The authors state that optimal performance can only be achieved when bit-parallel algorithms are developed around the nature of the target biological sequence, and identify finding structural similarities between RNA sequences as a task for future research.
Source: Muhammad et al. (2023), Operational Research in Engineering Sciences: Theory and Applications, 6(1), pp. 322–331. Publisher’s page
The study in detail
What question does this paper answer?
How do bit-parallel string pattern matching algorithms work, and how do they compare in performance, drawbacks and application areas when used to analyze biological sequences such as DNA, RNA and protein?
What did the study find, in detail?
The review explains the Shift-Or/Shift-And, BNDM, TNDM and SBNDM families and their parameterized variants, and compares 11 published bit-parallel algorithms by time complexity, drawbacks and application areas (Table 1). It concludes that bit-parallelism is versatile for biological sequence analysis but is mostly hampered by the requirement that the pattern length be less than or equal to the computer word length, and that optimal performance requires designing algorithms around the nature of the target sequence.
Why does it matter?
Because biological sequence data is generated rapidly and matching involves large amounts of computation, choosing an appropriate algorithm is difficult; the comparison is intended to help researchers select the most appropriate method for a particular application area. The authors note that benchmark algorithms applied to RNA without modification perform poorly, pointing to structure-aware bit-parallel methods as future work.
Methods and data
| Research question | Which bit-parallel string pattern matching algorithms suit which biological sequence analysis tasks? |
|---|---|
| Design | Comparative literature review of bit-parallel string matching algorithms |
| Data | Published algorithms, 11 of which are compared in a performance table |
| Methods | Description of algorithm mechanics (bit masks, state vectors, prev-encoding) and comparison of complexity, drawbacks and application areas |
| Main result | Bit-parallelism is versatile for DNA, RNA and protein analysis but limited by pattern length relative to computer word length |
| Implication | Algorithm choice should be based on applicability and complexity in the target application area; RNA structural similarity is a future research task |
| Citation | Muhammad et al. (2023) |
Definitions and key terms
- Bit parallelism
- The inherent parallelism in a bit operation like AND/OR inside a computer word, used to simulate a non-deterministic automaton during string matching. — as used in Muhammad et al. (2023)
- Parameterized matching
- Matching in which two strings are equivalent if one can be obtained from the other by renaming parameter symbols through a bijective mapping while constant symbols match exactly. — as used in Muhammad et al. (2023)
- Prev-encoding
- An encoding scheme introduced by Baker that keeps each constant symbol and replaces each parameter symbol with the distance from its previous occurrence. — as used in Muhammad et al. (2023)
Abstract
The inherent parallelism in a bit operation like AND/OR inside a computer word is known as bit parallelism. It plays a greater role in string pattern matching and has good application in the analysis of biological data. The use of recently developed bit parallel string matching algorithms approaches help in improving the efficiency of the other string pattern matching algorithms. This paper discusses the working of some of these bit parallel string matching algorithms and their application on biological sequences. It also shows how bit-parallelism can be efficiently used to address various matching problems in Bioinformatics to analyze biological sequences such as Deoxyribonucleic acid (DNA), Ribonucleic acid (RNA) and Protein with examples. It can also serve as greater tool for the researchers when looking for the appropriate method to us on Biological sequences.
Abstract as published in Operational Research in Engineering Sciences: Theory and Applications.
Keywords: Bit-parallelism; Automaton; Pattern matching; Ribonucleic acid; Parameterized matching
Practical implications
- Researchers choosing a bit-parallel string matching algorithm should base the choice on its applicability and complexity in the target application area.
- Researchers applying bit-parallel algorithms to biological sequences face a word-length constraint: the BNDM family is most efficient when the pattern length is not longer than the computer word size.
- The review notes that implementing benchmark bit-parallel algorithms on RNA sequences without modification was theoretically bad, because RNA and protein fold into complex structures and their nucleotide strings are complementary.
- Researchers developing bit-parallel algorithms should design them around the nature of the target biological sequence, which the authors state is the only way to achieve optimal performance.
Drawn from Muhammad et al. (2023), Operational Research in Engineering Sciences: Theory and Applications, 6(1), pp. 322–331.
When this research may be relevant
This article may be relevant to researchers surveying string pattern matching algorithms for DNA, RNA and protein sequences, bit-parallelism and word-length constraints in sequence analysis, or the choice of matching algorithm for bioinformatics pipelines. It is a review, not a new benchmark.
Research topics addressed: bioinformatics; bit-parallelism; string pattern matching; exact and approximate string matching; DNA sequence analysis; RNA secondary structure; protein sequences; Shift-Or and Shift-And algorithms; BNDM (Backward Non-deterministic DAWG Matching); parameterized matching; prev-encoding; algorithm time complexity; literature review
How to cite
- APA 7
- Muhammad, M. Y., Fonkam, M., Thandekatu, S. G., Rakshit, S., & Vajjhala, R. N. (2023). Comparative Analysis of Bit-Parallel String Pattern Matching Algorithms for Biological Sequences. Operational Research in Engineering Sciences: Theory and Applications, 6(1), 322–331. https://oresta.org/article-view/?id=554
- MLA 9
- Muhammad, Muhammad Yusuf, et al. “Comparative Analysis of Bit-Parallel String Pattern Matching Algorithms for Biological Sequences.” Operational Research in Engineering Sciences: Theory and Applications, vol. 6, no. 1, 2023, pp. 322–31. https://oresta.org/article-view/?id=554.
- IEEE
- M. Y. Muhammad, M. Fonkam, S. G. Thandekatu, S. Rakshit, and R. N. Vajjhala, “Comparative Analysis of Bit-Parallel String Pattern Matching Algorithms for Biological Sequences,” Operational Research in Engineering Sciences: Theory and Applications, vol. 6, no. 1, pp. 322–331, Apr. 2023. [Online]. Available: https://oresta.org/article-view/?id=554
BibTeX
@article{muhammad2023bit,
title = {Comparative Analysis of Bit-Parallel String Pattern Matching Algorithms for Biological Sequences},
author = {Muhammad, Muhammad Yusuf and Fonkam, Mathias and Thandekatu, Salu George and Rakshit, Sandip and Vajjhala, Rao Narasimha},
journal = {Operational Research in Engineering Sciences: Theory and Applications},
volume = {6},
number = {1},
pages = {322--331},
year = {2023},
publisher = {Regional Association for Security and Crisis Management (RABEK)},
url = {https://oresta.org/article-view/?id=554}
}RIS
TY - JOUR TI - Comparative Analysis of Bit-Parallel String Pattern Matching Algorithms for Biological Sequences AU - Muhammad, Muhammad Yusuf AU - Fonkam, Mathias AU - Thandekatu, Salu George AU - Rakshit, Sandip AU - Vajjhala, Rao Narasimha JO - Operational Research in Engineering Sciences: Theory and Applications PY - 2023 DA - 2023/04/15 VL - 6 IS - 1 SP - 322 EP - 331 PB - Regional Association for Security and Crisis Management (RABEK) SN - 2620-1747 UR - https://www.narasimharao.net/research/bit-parallel-string-matching-algorithms-biological-sequences/ LA - en ER -
Links and files
- Publisher’s page: https://oresta.org/article-view/?id=554
- This page as text: https://www.narasimharao.net/research/bit-parallel-string-matching-algorithms-biological-sequences/paper.md
- Permanent address of this page: https://www.narasimharao.net/research/bit-parallel-string-matching-algorithms-biological-sequences/
Related research
Related publications
The authors developed a bit-parallel structural matching (s-matching) algorithm that extends Shift-Or with encoding techniques for s-strings, solving exact s-matching on RNA secondary structure with assumed average-time optimality.
The review shows that statistical relational learning — probabilistic relational models, relational dependency networks and relational Markov networks — suits genomics tasks from sequence annotation to GWAS, and identifies the computational complexity of inference, followed by graph size, as the main limitation shared by most methods.
The review shows that DEA is widely applied in hospital management, nursing and outpatient services for efficiency measurement, benchmarking, resource allocation and performance evaluation, and identifies six limitations, including input/output selection, outlier sensitivity, inability to handle statistical noise and the static nature of traditional models.
A critical review of 2015–2020 empirical studies identifies lack of modern-method training, corrupt input dissemination, poor infrastructure, terrorism-driven insecurity, lack of credit and weak strategic planning as the key problems, and finds only weak evidence of significant information-system use in agriculture.