Combinatorial Computational Biology of RNA (eBook)

Pseudoknots and Neutral Networks

Christian Reidys (Autor)

eBook Download: PDF

2010 | 2011
X, 258 Seiten
Springer New York (Verlag)
978-0-387-76731-4 (ISBN)

Infos

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.

Inhalt

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

Produkt-Details

• Erscheint lt. Verlag: 29.10.2010
• Zusatzinfo: X, 258 p.
• Verlagsort: New York
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik ► Theorie / Studium
• Themenwelt: Mathematik / Informatik ► Mathematik ► Angewandte Mathematik
• Themenwelt: Mathematik / Informatik ► Mathematik ► Graphentheorie
• Themenwelt: Naturwissenschaften ► Biologie ► Evolution
• Themenwelt: Naturwissenschaften ► Biologie ► Genetik / Molekularbiologie
• Themenwelt: Technik
• Schlagworte: combinatorics • Computational Biology • Discrete Mathematics • Mathematical Biology • pseudo knots
• ISBN-10: 0-387-76731-2 / 0387767312
• ISBN-13: 978-0-387-76731-4 / 9780387767314