NDLI: Valid Plane Trees: Combinatorial Models for RNA Secondary Structures with Watson--Crick Base Pairs

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Drellich, Elizabeth Black, Francis Tymoczko, Julianna
Copyright Year	2017
Abstract	The combinatorics of RNA plays a central role in biology. Mathematical biologists have several commonly used models for RNA: words in a fixed alphabet (representing the primary sequence of nucleotides) and plane trees (representing the secondary structure, or folding of the RNA sequence). This paper considers an augmented version of the standard model of plane trees, specifically one that incorporates some observed constraints on how the folding can occur. In particular we assume the alphabet consists of complementary pairs, for instance the Watson--Crick pairs A-U and C-G of RNA. Given a word in the alphabet, a valid plane tree is a tree for which, when the word is folded around the tree, each edge matches two complementary letters. Consider the graph whose vertices are valid plane trees for a fixed word and whose edges are given by Condon, Heitsch, and Hoos's local moves (see [C. E. Heitsch, Combinatorics on Plane Trees, Motivated by RNA Secondary Structure Configurations, preprint, Genome Center of Wisconsin and Department of Mathematics, University of Wisconsin--Madison]). We prove that this graph is connected. We give an explicit algorithm to construct a valid plane tree from a primary sequence, assuming that at least one valid plane tree exists. The tree produced by our algorithm has other useful characterizations, including a uniqueness condition defined by local moves. We also study enumerative properties of valid plane trees, analyzing how the number of valid plane trees depends on the choice of sequence length and alphabet size. Finally, we show that the proportion of words with at least one valid plane tree goes to zero as the word size increases. We also present some open questions.
Sponsorship	National Science Foundation
Starting Page	2586
Ending Page	2602
Page Count	17
File Format	PDF
ISSN	08954801
DOI	10.1137/15M1008841
e-ISSN	10957146
Journal	SIAM Journal on Discrete Mathematics (SJDMEC)
Issue Number	4
Volume Number	31
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2017-11-14
Access Restriction	Subscribed
Subject Keyword	plane trees Enumeration in graph theory Biochemistry, molecular biology noncrossing matchings RNA folding
Content Type	Text
Resource Type	Article
Subject	Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Valid plane trees: Combinatorial models for RNA secondary structures with Watson-Crick base pairs

Geometric nomenclature and classification of RNA base pairs

RNA folding: beyond Watson-Crick pairs.

An innate twist between Crick's wobble and Watson-Crick base pairs.

Covalently Cross-Linked Watson-Crick Base Pair Models

Non-Watson-Crick base associations in DNA and RNA revealed by single crystal x-ray diffraction methods: Mismatches, modified bases, and nonduplex DNA

Solution Structure of n-Type DNA Oligomers Possessing a Covalently Cross-Linked Watson–Crick Base Pair Model

Central and local limit theorems for RNA structures (2007)

Non-Watson-Crick base pairs in RNA-protein recognition.

Valid Plane Trees: Combinatorial Models for RNA Secondary Structures with Watson--Crick Base Pairs

Similar Documents

Valid plane trees: Combinatorial models for RNA secondary structures with Watson-Crick base pairs

Geometric nomenclature and classification of RNA base pairs

RNA folding: beyond Watson-Crick pairs.

An innate twist between Crick's wobble and Watson-Crick base pairs.

Covalently Cross-Linked Watson-Crick Base Pair Models

Non-Watson-Crick base associations in DNA and RNA revealed by single crystal x-ray diffraction methods: Mismatches, modified bases, and nonduplex DNA

Solution Structure of n-Type DNA Oligomers Possessing a Covalently Cross-Linked Watson–Crick Base Pair Model

Central and local limit theorems for RNA structures (2007)

Non-Watson-Crick base pairs in RNA-protein recognition.

Valid Plane Trees: Combinatorial Models for RNA Secondary Structures with Watson--Crick Base Pairs