Conference paper · 2022
Efficient Structural Matching for RNA Secondary Structure Using Bit-Parallelism
High Performance Computing and Networking: Select Proceedings of CHSN 2021, Lecture Notes in Electrical Engineering, vol. 853, pp. 399–409, Springer Nature Singapore · Published
Summary
Muhammad et al. (2022) proposed an exact, bit-parallel pattern matching algorithm to address RNA secondary structure queries using structural matching (s-matching), which refers to matching parameters, complements and constant symbols. The algorithm extends the well-known Shift-Or algorithm with coding techniques for s-strings and is intended to answer queries such as discovering exactly similar and structurally similar RNA sequences. It addresses the exact s-matching problem on RNA secondary structure and is assumed to be optimal on average time; the abstract reports no empirical benchmark figures.
Practical implication. Researchers working on functional annotation in bioinformatics may use the proposed bit-parallel s-matching algorithm to find exactly similar and structurally similar RNA sequences, which could help infer biological function.
- The Problem
- Annotating the function of newly discovered RNA requires finding exactly and structurally similar RNA secondary structures, which existing exact-matching algorithms do not handle efficiently.
- The Methodology
- Algorithm design: a bit-parallel exact structural matching (s-matching) algorithm for RNA secondary structure that advances the Shift-Or algorithm with encoding techniques for s-strings; average-time optimality is stated as an assumption.
- The Core Finding
- 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 Citation
- Muhammad, M. Y., Thandekkattu, S. G., Rakshit, S., & Vajjhala, N. R. (2022). Efficient Structural Matching for RNA Secondary Structure Using Bit-Parallelism. In Ch. Satyanarayana, D. Samanta, X.-Z. Gao, & R. K. Kapoor (Eds.), High Performance Computing and Networking: Select Proceedings of CHSN 2021 (pp. 399–409). Springer Nature Singapore. https://doi.org/10.1007/978-981-16-9885-9_33
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. Structural matching (s-matching) refers to matching parameters, complements and constant symbols; the paper applies it to RNA secondary structure queries.
- Finding 2. A new bit-parallel algorithm is developed that advances the Shift-Or algorithm by adding a transformative approach to working with s-strings through coding techniques portable to s-matching.
- Finding 3. The algorithm addresses the exact s-matching problem on RNA secondary structure and is assumed to be optimal on average time.
- Finding 4. It is intended to answer RNA matching queries — discovering exactly similar and structurally similar RNA sequences — that are critical to characterising the functional annotation of newly discovered RNA.
Source: Muhammad et al. (2022), High Performance Computing and Networking: Select Proceedings of CHSN 2021, Lecture Notes in Electrical Engineering, vol. 853, pp. 399–409, Springer Nature Singapore. DOI: 10.1007/978-981-16-9885-9_33
The study in detail
What question does this paper answer?
Can an exact, bit-parallel pattern matching algorithm answer RNA secondary structure queries using structural matching (s-matching) efficiently enough to support inference of biological function?
What did the study find, in detail?
The authors develop a new bit-parallel algorithm that extends the well-known Shift-Or algorithm with a transformative approach to s-strings, using coding techniques portable to the s-matching domain. The algorithm addresses the exact s-matching problem on RNA secondary structure and is assumed to be optimal on average time. It is intended to answer queries such as discovering exactly similar and structurally similar RNA sequences, which is critical to functional annotation of newly discovered RNA.
Why does it matter?
Structural similarity between RNA sequences helps infer their biological function. An efficient exact structural matching algorithm gives bioinformatics pipelines a fast way to find structurally similar RNA, complementing sequence-level matching.
Methods and data
| Problem | Exact structural matching (s-matching: parameters, complements and constant symbols) of RNA secondary structure queries |
|---|---|
| Design | Algorithm development |
| Methods | Bit-parallelism; extension of the Shift-Or algorithm with coding techniques for s-strings |
| Main result | A new bit-parallel s-matching algorithm for RNA secondary structure, assumed optimal on average time |
| Implication | Supports queries for exactly and structurally similar RNA, aiding functional annotation of newly discovered RNA |
| Citation | Muhammad et al. (2022) · DOI 10.1007/978-981-16-9885-9_33 |
Abstract
The idea of matching parameters, complements, and constants symbols is referred to as structural matching or s-matching for short. In this paper, an efficient exact pattern matching bit-parallel algorithm is proposed to address RNA secondary structure queries using the concept of s-matching. This algorithm has good application in finding structural similarity between RNA sequences which could help in infer its biological function. We developed a new bit-parallel algorithm that can be implemented and advance the well-known shift-OR algorithm by adding a transformative approach of working with s-strings through coding techniques that were portable in the area of s-matching. Our algorithm advances for the exact s-matching problem on RNA secondary structure assumed to be optimal on average time. The proposed algorithm could help answer RNA matching queries, such as discovering precisely similar RNA and structurally similar RNA sequences, critical to the characterization of functional annotation of a newly discovered RNA.
Abstract as published in High Performance Computing and Networking: Select Proceedings of CHSN 2021.
Keywords: Parallelism; Parameterized matching; Structural matching; Encoding; RNA; Algorithm; Sequences
Limitations
- Average-time optimality is stated as an assumption in the abstract; no empirical benchmark figures are reported there.
Practical implications
- Researchers annotating newly discovered RNA may use the proposed bit-parallel s-matching algorithm to answer RNA matching queries, such as discovering exactly similar and structurally similar RNA sequences.
- An efficient exact structural matching algorithm may give bioinformatics pipelines a fast way to find structurally similar RNA, complementing sequence-level matching.
Drawn from Muhammad et al. (2022), High Performance Computing and Networking: Select Proceedings of CHSN 2021, Lecture Notes in Electrical Engineering, vol. 853, pp. 399–409, Springer Nature Singapore.
When this research may be relevant
This paper may be relevant to researchers working on RNA secondary structure comparison, structural or parameterized string matching, bit-parallel algorithms derived from Shift-Or, and algorithmic tools for functional annotation in bioinformatics. It extends the comparative review of bit-parallel algorithms listed under related research.
Research topics addressed: RNA secondary structure; structural matching; s-matching; bit-parallel algorithms; Shift-Or algorithm; parameterized string matching; exact pattern matching; bioinformatics; sequence similarity; functional annotation
How to cite
- APA 7
- Muhammad, M. Y., Thandekkattu, S. G., Rakshit, S., & Vajjhala, N. R. (2022). Efficient Structural Matching for RNA Secondary Structure Using Bit-Parallelism. In Ch. Satyanarayana, D. Samanta, X.-Z. Gao, & R. K. Kapoor (Eds.), High Performance Computing and Networking: Select Proceedings of CHSN 2021 (pp. 399–409). Springer Nature Singapore. https://doi.org/10.1007/978-981-16-9885-9_33
- MLA 9
- Muhammad, Muhammad Yusuf, et al. “Efficient Structural Matching for RNA Secondary Structure Using Bit-Parallelism.” High Performance Computing and Networking: Select Proceedings of CHSN 2021, edited by Ch. Satyanarayana et al., Springer Nature Singapore, 2022, pp. 399–409. https://doi.org/10.1007/978-981-16-9885-9_33.
- IEEE
- M. Y. Muhammad, S. G. Thandekkattu, S. Rakshit, and N. R. Vajjhala, “Efficient Structural Matching for RNA Secondary Structure Using Bit-Parallelism,” in High Performance Computing and Networking: Select Proceedings of CHSN 2021, Ch. Satyanarayana, D. Samanta, X.-Z. Gao, and R. K. Kapoor, Eds. Springer Nature Singapore, 2022, pp. 399–409, doi: 10.1007/978-981-16-9885-9_33.
BibTeX
@inproceedings{muhammad2022rna,
title = {Efficient Structural Matching for RNA Secondary Structure Using Bit-Parallelism},
author = {Muhammad, Muhammad Yusuf and Thandekkattu, Salu George and Rakshit, Sandip and Vajjhala, Narasimha Rao},
booktitle = {High Performance Computing and Networking: Select Proceedings of CHSN 2021},
series = {Lecture Notes in Electrical Engineering},
editor = {Satyanarayana, Ch. and Samanta, Debasis and Gao, Xiao-Zhi and Kapoor, Rajiv Kumar},
pages = {399--409},
year = {2022},
publisher = {Springer Nature Singapore},
doi = {10.1007/978-981-16-9885-9_33},
url = {https://doi.org/10.1007/978-981-16-9885-9_33}
}RIS
TY - CPAPER TI - Efficient Structural Matching for RNA Secondary Structure Using Bit-Parallelism AU - Muhammad, Muhammad Yusuf AU - Thandekkattu, Salu George AU - Rakshit, Sandip AU - Vajjhala, Narasimha Rao ED - Satyanarayana, Ch. ED - Samanta, Debasis ED - Gao, Xiao-Zhi ED - Kapoor, Rajiv Kumar T2 - High Performance Computing and Networking: Select Proceedings of CHSN 2021 T3 - Lecture Notes in Electrical Engineering PY - 2022 DA - 2022/03/23 VL - 853 SP - 399 EP - 409 PB - Springer Nature Singapore SN - 1876-1100 DO - 10.1007/978-981-16-9885-9_33 UR - https://www.narasimharao.net/research/rna-secondary-structure-matching-bit-parallelism/ LA - en ER -
Links and files
- DOI: https://doi.org/10.1007/978-981-16-9885-9_33
- Publisher’s page: https://link.springer.com/chapter/10.1007/978-981-16-9885-9_33
- This page as text: https://www.narasimharao.net/research/rna-secondary-structure-matching-bit-parallelism/paper.md
- Permanent address of this page: https://www.narasimharao.net/research/rna-secondary-structure-matching-bit-parallelism/
Related research
Related publications on algorithms and bioinformatics
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 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.