Reidys Combinatorial Computational Biology of RNA

Pseudoknots and Neutral Networks
1. Auflage 2010
ISBN: 978-0-387-76731-4
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 258 Seiten

In this monograph, new combinatorial and computational approaches in the study of RNA structures are presented which enhance both mathematics and computational biology. It begins with an introductory chapter, which motivates and sets the background of this research. In the following chapter, all the concepts are systematically developed. The reader will find * integration of more than forty research papers covering topics like, RSK-algorithm, reflection principle, singularity analysis and random graph theory * systematic presentation of the theory of pseudo-knotted RNA structures including their generating function, uniform generation as well as central and discrete limit theorems * computational biology of pseudo-knotted RNA structures, including dynamic programming paradigms and a new folding algorithm * analysis of neutral networks of pseudo knotted RNA structures and their random graph theory, including neutral paths, giant components and connectivity All algorithms presented are freely available through springer.com and implemented in C. A proofs section at the end contains the necessary technicalities. This book will serve graduate students and researchers in the fields of discrete mathematics, mathematical and computational biology. It is suitable as a textbook for a graduate course in mathematical and computational biology.

Autoren/Hrsg.

Reidys, Christian

Inhaltsverzeichnis

1;Preface;5
2;Contents;7
3;1 Introduction;10
3.1;1.1 RNA secondary structures;12
3.2;1.2 RNA pseudoknot structures;17
3.3;1.3 Sequence to structure maps;19
3.4;1.4 Folding;24
3.5;1.5 RNA tertiary interactions: a combinatorial perspective;28
4;2 Basic concepts;31
4.1;2.1 k-Noncrossing partial matchings;31
4.1.1;2.1.1 Young tableaux, RSK algorithm, and Weyl chambers;32
4.1.2;2.1.2 The Weyl group;34
4.1.3;2.1.3 From tableaux to paths and back;36
4.1.4;2.1.4 The generating function via the reflection principle;42
4.1.5;2.1.5 D-finiteness;49
4.2;2.2 Symbolic enumeration;53
4.3;2.3 Singularity analysis;55
4.3.1;2.3.1 Transfer theorems;55
4.3.2;2.3.2 The supercritical paradigm;57
4.4;2.4 The generating function Fk(z);58
4.4.1;2.4.1 Some ODEs;58
4.4.2;2.4.2 The singular expansion of Fk(z);60
4.5;2.5 n-Cubes;64
4.5.1;2.5.1 Some basic facts;66
4.5.2;2.5.2 Random subgraphs of the n-cube;68
4.5.3;2.5.3 Vertex boundaries;69
4.5.4;2.5.4 Branching processes and Janson's inequality;70
4.6;2.6 Exercises;72
5;3 Tangled diagrams;74
5.1;3.1 Tangled diagrams and vacillating tableaux;74
5.2;3.2 The bijection;77
5.3;3.3 Enumeration;85
6;4 Combinatorial analysis;91
6.1;4.1 Cores and Shapes;94
6.1.1;4.1.1 Cores;94
6.1.2;4.1.2 Shapes;97
6.2;4.2 Generating functions;104
6.2.1;4.2.1 The GF of cores;105
6.2.2;4.2.2 The GF of k-noncrossing, -canonical structures;109
6.3;4.3 Asymptotics;115
6.3.1;4.3.1 k-Noncrossing structures;115
6.3.2;4.3.2 Canonical structures;120
6.4;4.4 Modular k-noncrossing structures;126
6.4.1;4.4.1 Colored shapes;129
6.4.2;4.4.2 The main theorem;134
6.5;4.5 Exercises;142
7;5 Probabilistic Analysis;149
7.1;5.1 Uniform generation;149
7.1.1;5.1.1 Partial matchings;151
7.1.2;5.1.2 k-Noncrossing structures;153
7.2;5.2 Central limit theorems;160
7.2.1;5.2.1 The central limit theorem;161
7.2.2;5.2.2 Arcs and stacks;165
7.2.3;5.2.3 Hairpin loops, interior loops, and bulges;174
7.3;5.3 Discrete limit laws;181
7.3.1;5.3.1 Irreducible substructures;184
7.3.2;5.3.2 The limit distribution of nontrivial returns;189
7.4;5.4 Exercises;192
8;6 Folding;193
8.1;6.1 DP folding based on loop energies;197
8.1.1;6.1.1 Secondary structures;197
8.1.2;6.1.2 Pseudoknot structures;200
8.2;6.2 Combinatorial folding;204
8.2.1;6.2.1 Some basic facts;205
8.2.2;6.2.2 Motifs;207
8.2.3;6.2.3 Skeleta;210
8.2.4;6.2.4 Saturation;214
9;7 Neutral networks;219
9.1;7.1 Neutral networks as random graphs;219
9.2;7.2 The giant;222
9.2.1;7.2.1 Cells;224
9.2.2;7.2.2 The number of vertices contained in cells;229
9.2.3;7.2.3 The largest component;235
9.3;7.3 Neutral paths;240
9.4;7.4 Connectivity;243
9.5;7.5 Exercises;247
10;References;250
11;Index;258