Topological language for RNA

DOI10.1016/J.MBS.2016.10.006zbMATH Open1352.92113arXiv1605.02628OpenAlexW2963017572WikidataQ39257154 ScholiaQ39257154MaRDI QIDQ343072FDOQ343072

Authors: Fenix W. D. Huang, Christian M. Reidys 

Publication date: 21 November 2016

Published in: Mathematical Biosciences (Search for Journal in Brave)

Abstract: In this paper we introduce a novel, context-free grammar, {it RNAFeatures${}^{\ast }$}, capable of generating any RNA structure including pseudoknot structures (pk-structure). We represent pk-structures as orientable fatgraphs, which naturally leads to a filtration by their topological genus. Within this framework, RNA secondary structures correspond to pk-structures of genus zero. {it RNAFeatures${}^{\ast }$} acts on formal, arc-labeled RNA secondary structures, called $lambda$-structures. $lambda$-structures correspond one-to-one to pk-structures together with some additional information. This information consists of the specific rearrangement of the backbone, by which a pk-structure can be made cross-free. {it RNAFeatures${}^{\ast }$} is an extension of the grammar for secondary structures and employs an enhancement by labelings of the symbols as well as the production rules. We discuss how to use {it RNAFeatures${}^{\ast }$} to obtain a stochastic context-free grammar for pk-structures, using data of RNA sequences and structures. The induced grammar facilitates fast Boltzmann sampling and statistical analysis. As a first application, we present an $O(nlog(n))$ runtime algorithm which samples pk-structures based on ninety tRNA sequences and structures from the Nucleic Acid Database (NDB).

Full work available at URL: https://arxiv.org/abs/1605.02628

Recommendations

• Generation of RNA pseudoknot structures with topological genus filtration
• RNA secondary structures: an approach through pseudoknots and fatgraphs
• Fatgraph models of RNA structure
• Statistics of topological RNA structures
• Shapes of topological RNA structures

zbMATH Keywords

context-free grammarfatgraphRNA pseudoknot structurestochastic context-free grammartopological RNA structure

Mathematics Subject Classification ID

Protein sequences, DNA sequences (92D20)

Cites Work

• Biological Sequence Analysis
• Title not available (Why is that?)
• Algebraic Statistics for Computational Biology
• Title not available (Why is that?)
• Topological classification and enumeration of RNA structures by genus
• Title not available (Why is that?)
• RNA folding and large \(N\) matrix theory
• Rapid dynamic programming algorithms for RNA secondary structure
• RNA secondary structure: a complete mathematical analysis
• On some new sequences generalizing the Catalan and Motzkin numbers
• Spaces of RNA secondary structures
• Generation of RNA pseudoknot structures with topological genus filtration
• The chromatic polynomial of fatgraphs and its categorification
• Fatgraph models of proteins
• Title not available (Why is that?)
• Algorithms for Loop Matchings
• RNA sequence, structure, and function: computational and bioinformatic methods
• Boltzmann Samplers for the Random Generation of Combinatorial Structures
• Structural Alignment of RNAs Using Profile-csHMMs and Its Application to RNA Homology Search: Overview and New Results
• Proportions of Irreducible Diagrams
• A new combinatorial identity for unicellular maps, via a direct bijective approach
• Efficient sampling of RNA secondary structures from the Boltzmann ensemble of low-energy

Cited In (7)

• Generation of RNA pseudoknot structures with topological genus filtration
• Loop homology of bi-secondary structures
• Statistics of topological RNA structures
• TPstructure
• Topological Classification of RNA Structures via Intersection Graph
• Loop homology of bi-secondary structures. II
• Fatgraph models of RNA structure

Uses Software

• NNDB
• Pfold

This page was built for publication: Topological language for RNA

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q343072)