Analytic Combinatorics Applied to RNA Structures

TR Number
Date
2018-07-09
Journal Title
Journal ISSN
Volume Title
Publisher
Virginia Tech
Abstract

In recent years it has been shown that the folding pattern of an RNA molecule plays an important role in its function, likened to a lock and key system. γ-structures are a subset of RNA pseudoknot structures filtered by topological genus that lend themselves nicely to combinatorial analysis. Namely, the coefficients of their generating function can be approximated for large n. This paper is an investigation into the length-spectrum of the longest block in random γ-structures. We prove that the expected length of the longest block is on the order n - O(n^1/2). We further compare these results with a similar analysis of the length-spectrum of rainbows in RNA secondary structures, found in Li and Reidys (2018). It turns out that the expected length of the longest block for γ-structures is on the order the same as the expected length of rainbows in secondary structures.

Description
Keywords
RNA structures, fatgraphs, Analytic Combinatorics
Citation
Collections