Graph-Theoretic Partitioning of RNAs and Classification of Pseudoknots

Louis Petingi, Tamar Schlick

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Dual graphs have been applied to model RNA secondary structures with pseudoknots, or intertwined base pairs. In a previous work, a linear-time algorithm was introduced to partition dual graphs into maximal topological components called blocks and determine whether each block contains a pseudoknot or not. This characterization allowed us to efficiently isolate smaller RNA fragments and classify them as pseudoknotted or pseudoknot-free regions, while keeping these sub-structures intact. In this paper we extend the partitioning algorithm by classifying a pseudoknot as either recursive or non-recursive. A pseudoknot is recursive if it contains independent regions or fragments. Each of these regions can be also identified by the modified algorithm, continuing with our current research in the development of a library of building blocks for RNA design by fragment assembly. Partitioning and classification of RNAs using dual graphs provide a systematic way for study of RNA structure and prediction.

Original languageEnglish (US)
Title of host publicationAlgorithms for Computational Biology - 6th International Conference, AlCoB 2019, Proceedings
EditorsMiguel A. Vega-Rodríguez, Ian Holmes, Carlos Martín-Vide
PublisherSpringer Verlag
Number of pages12
ISBN (Print)9783030181734
StatePublished - 2019
Event6th International Conference on Algorithms for Computational Biology, AlCoB 2019 - Berkeley, United States
Duration: May 28 2019May 30 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11488 LNBI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference6th International Conference on Algorithms for Computational Biology, AlCoB 2019
Country/TerritoryUnited States


  • Bi-connectivity
  • Graph theory
  • Partitioning
  • Pseudoknots
  • RNA secondary structures

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Graph-Theoretic Partitioning of RNAs and Classification of Pseudoknots'. Together they form a unique fingerprint.

Cite this