# Efficient Structural Matching for RNA Secondary Structure Using Bit-Parallelism

**Authors:** Muhammad Yusuf Muhammad (American University of Nigeria, Yola, Nigeria); Salu George Thandekkattu (American University of Nigeria, Yola, Nigeria) — ORCID 0000-0003-3957-3554; Sandip Rakshit (American University of Nigeria, Yola, Nigeria) — ORCID 0000-0001-5735-983X; Narasimha Rao Vajjhala (University of New York Tirana, Tirana, Albania) — ORCID 0000-0002-8260-2392
**Type:** Conference paper
**Source:** High Performance Computing and Networking: Select Proceedings of CHSN 2021, Lecture Notes in Electrical Engineering, vol. 853, pp. 399–409, Springer Nature Singapore
**Published:** 2022-03-23
**DOI:** https://doi.org/10.1007/978-981-16-9885-9_33
**Canonical page:** https://www.narasimharao.net/research/rna-secondary-structure-matching-bit-parallelism/
**Indexing:** Scopus
**Keywords:** Parallelism; Parameterized matching; Structural matching; Encoding; RNA; Algorithm; Sequences
**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.

## Research summary

- **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, Debasis Samanta, Xiao-Zhi Gao, Rajiv Kumar 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

## Summary in detail

**Question.** 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?

**Finding.** 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 it matters.** 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.

## Key findings

1. Structural matching (s-matching) refers to matching parameters, complements and constant symbols; the paper applies it to RNA secondary structure queries.
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.
3. The algorithm addresses the exact s-matching problem on RNA secondary structure and is assumed to be optimal on average time.
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.

## Study at a glance

| Item | Detail |
|---|---|
| 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 |

## 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.

## 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.

## Limitations

- Average-time optimality is stated as an assumption in the abstract; no empirical benchmark figures are reported there.

## How to cite

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, Debasis Samanta, Xiao-Zhi Gao, Rajiv Kumar 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

```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 = {Ch. Satyanarayana and Debasis Samanta and Xiao-Zhi Gao and Rajiv Kumar Kapoor},
  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}
}
```