Efficient Structural Matching for RNA Secondary Structure Using Bit-Parallelism

Research summary

The summary, key findings, methodology and relevance notes below 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.

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 Copy APA

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.

Study at a glance

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.

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

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

@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}
}