Identifying and Analyzing RNA Pseudoknots based on Graph-theoretical Properties of Dual Graphs: a Partitioning Approach

Authors

Louis Petingi, CUNY College of Staten Island and CUNY Graduate CenterFollow

Document Type

Article

Publication Date

2-8-2015

Abstract

In this paper we propose the study of properties of RNA secondary structures modeled as dual graphs, by partitioning these graphs into topological components denominated blocks. We give a full characterization of possible topological configurations of these blocks, and, in particular we show that an RNA secondary structure contains a pseudoknot if and only if its corresponding dual graph contains a block having a vertex of degree at least 3. Once a dual graph has been partitioned via computationally-efficient well-known graph-theoretical algorithms, this characterization allow us to identify these sub-topologies and physically isolate pseudoknots from RNA secondary structures and analyze them for specific combinatorial properties (e.g., connectivity).

Comments

Graph-theoretical partitioning approach of dual graphs representing RNA 2D, into blocks, using Hopcroft and Tarjan's algorithm to detect bi-connected components. Mathematical characterization of these bocks to determine the existence (non-existence) of pseudoknots.