Partitioning and classification of RNA secondary structures into pseudonotted and pseudoknot-free regions using a graph-theoretical approach

Louis Petingi, Tamar Schlick

Research output: Contribution to journalArticlepeer-review

Abstract

Dual graphs have been applied to model RNA secondary structures with pseudoknots, or intertwined base pairs. In this paper we present a linear-time algorithm to partition dual graphs into maximal topological components called blocks and determine whether each block contains a pseudoknot or not. We show that a block contains a pseudoknot if and only if the block has a vertex of degree 3 or more; this characterization allows us to efficiently isolate smaller RNA fragments and classify them as pseudoknotted or pseudoknot-free regions, while keeping these sub-structures intact. Applications to RNA design can be envisioned since modular building blocks with intact pseudoknots can be combined to form new constructs.

Original languageEnglish (US)
Pages (from-to)241-246
Number of pages6
JournalIAENG International Journal of Computer Science
Volume44
Issue number2
StatePublished - 2017

Keywords

  • Graph theory
  • Pseudoknots
  • RNAs secondary structures

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Partitioning and classification of RNA secondary structures into pseudonotted and pseudoknot-free regions using a graph-theoretical approach'. Together they form a unique fingerprint.

Cite this