Graph-Theoretic Partitioning of RNAs and Classification of Pseudoknots-II
Dual graphs have been applied to model RNA secondary structures with pseudoknots, or intertwined base pairs. In previous works, a linear-time algorithm was introduced to partition dual graphs into maximally connected components called blocks and determine whether each block contains a pseudoknot or not. As pseudoknots can not be contained into two different blocks, this characterization allow us to efficiently isolate smaller RNA fragments and classify them as pseudoknotted or pseudoknot-free regions, while keeping these sub-structures intact. Moreover we have extended the partitioning algorithm by classifying a pseudoknot as either recursive or non-recursive in order to continue with our research in the development of a library of building blocks for RNA design by fragment assembly. In this paper we present a methodology that uses our previous results and classify pseudoknots into the classical H,K,L, and M types, based upon a novel representation of RNA secondary structures as dual directed graphs (i.e., digraphs). This classification would help the systematic analysis of RNA structure and prediction as for example the implementation of more accurate folding algorithms.
Code (0)
등록된 구현이 없습니다.
Tasks
ClassificationSimilar Papers 제목 키워드 기반
Partitioning RNAs into pseudonotted and pseudoknot-free regions modeled as Dual Graphs
Dual graphs have been applied to model RNA secondary structures. The purpose of the paper is two-fold: we present new graph-theoretic properties of dual graphs to validate the further analysis and classification of RNAs …
Improved RNA pseudoknots prediction and classification using a new topological invariant
We propose a new topological characterization of RNA secondary structures with pseudoknots based on two topological invariants. Starting from the classic arc-representation of RNA secondary structures, we consider a mode…
ARCA HyperGraphMamba-Based Multichannel Adaptive Model for ncRNA Classification
Non-coding RNAs (ncRNAs) play pivotal roles in gene expression regulation and the pathogenesis of various diseases. Accurate classification of ncRNAs is essential for functional annotation and disease diagnosis. To addre…
Uplifting the Expressive Power of Graph Neural Networks through Graph Partitioning
Graph Neural Networks (GNNs) have paved its way for being a cornerstone in graph related learning tasks. From a theoretical perspective, the expressive power of GNNs is primarily characterised according to their ability …
graph partitioningConsistency of Spectral Hypergraph Partitioning under Planted Partition Model
Hypergraph partitioning lies at the heart of a number of problems in machine learning and network sciences. Many algorithms for hypergraph partitioning have been proposed that extend standard approaches for graph partiti…
graph partitioninghypergraph partitioningStochastic Block Model