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
Summary
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?
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.
Key findings
- The review compares 11 published bit-parallel string matching algorithms for biological sequences by performance, drawback and application area.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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. DOI: 10.31181/oresta/0601131
Study at a glance
| 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) · DOI 10.31181/oresta/0601131 |
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
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.
- 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.
- 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.
How to cite
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://doi.org/10.31181/oresta/0601131
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)},
doi = {10.31181/oresta/0601131},
url = {https://doi.org/10.31181/oresta/0601131}
}Related research