Combinatorial Pattern Matching Algorithms in Computational Biology using Perl and R

by Valiente; Gabriel

• ISBN13: 9781420069730
• ISBN10: 142006973X
• eBook ISBN(s): 9781040208847
• Edition: 1st
• Format: Hardcover
• Copyright: 2009-04-08
• Publisher: Chapman & Hall/
• More Book Details

Summary

Emphasizing the search for patterns within and between biological sequences, trees, and graphs, this book shows how combinatorial pattern matching algorithms can solve computational biology problems that arise in the analysis of genomic, transcriptomic, proteomic, metabolomic, and interactomic data. It provides an intuitive presentation of the algorithms, followed by a detailed exposition in pseudo-code. The author offers alternative implementations of the algorithms in Perl and R to enable the testing of algorithms and the building of projects based on the code. He also includes the Perl and R source code for all the algorithms on his website.

Table of Contents

Foreword
Preface
Introduction	p. 1
Combinatorial Pattern Matching	p. 3
Computational Biology	p. 4
A Motivating Example: Gene Prediction	p. 4
Bibliographic Notes	p. 17
Sequence Pattern Matching
Sequences	p. 21
Sequences in Mathematics	p. 21
Counting Labeled Sequences	p. 22
Sequences in Computer Science	p. 24
Traversing Labeled Sequences	p. 26
Sequences in Computational Biology	p. 29
Reverse Complementing DNA Sequences	p. 31
Counting RNA Sequences	p. 33
Generating DNA Sequences	p. 35
Representing Sequences in Perl	p. 38
Representing Sequences in R	p. 40
Bibliographic Notes	p. 42
Simple Pattern Matching in Sequences	p. 43
Finding Words in Sequences	p. 43
Word Composition of Sequences	p. 43
Alignment Free Comparison of Sequences	p. 49
Bibliographic Notes	p. 52
General Pattern Matching in Sequences	p. 53
Finding Subsequences	p. 53
Suffix Arrays	p. 56
Finding Common Subsequences	p. 67
Generalized Suffix Arrays	p. 74
Comparing Sequences	p. 86
Edit Distance-Based Comparison of Sequences	p. 86
Alignment-Based Comparison of Sequences	p. 95
Bibliographic Notes	p. 110
Tree Pattern Matching
Trees	p. 115
Trees in Mathematics	p. 115
Counting Labeled Trees	p. 115
Trees in Computer Science	p. 117
Traversing Rooted Trees	p. 118
Trees in Computational Biology	p. 118
The Newick Linear Representation	p. 123
Counting Phylogenetic Trees	p. 125
Generating Phylogenetic Trees	p. 126
Representing Trees in Perl	p. 128
Representing Trees in R	p. 131
Bibliographic Notes	p. 135
Simple Pattern Matching in Trees	p. 137
Finding Paths in Unrooted Trees	p. 137
Distances in Unrooted Trees	p. 138
The Partition Distance between Unrooted Trees	p. 140
The Nodal Distance between Unrooted Trees	p. 144
Finding Paths in Rooted Trees	p. 148
Distances in Rooted Trees	p. 150
The Partition Distance between Rooted Trees	p. 151
The Nodal Distance between Rooted Trees	p. 151
Bibliographic Notes	p. 152
General Pattern Matching in Trees	p. 155
Finding Subtrees	p. 155
Finding Subtrees Induced by Triplets	p. 156
Finding Subtrees Induced by Quartets	p. 159
Finding Common Subtrees	p. 161
Maximum Agreement of Rooted Trees	p. 161
Maximum Agreement of Unrooted Trees	p. 172
Comparing Trees	p. 172
The Triplets Distance between Rooted Trees	p. 172
The Quartets Distance between Unrooted Trees	p. 175
Bibliographic Notes	p. 178
Graph Pattern Matching
Graphs	p. 181
Graphs in Mathematics	p. 181
Counting Labeled Graphs	p. 182
Graphs in Computer Science	p. 183
Traversing Directed Graphs	p. 183
Graphs in Computational Biology	p. 184
The eNewick Linear Representation	p. 193
Counting Phylogenetic Networks	p. 195
Generating Phylogenetic Networks	p. 198
Representing Graphs in Perl	p. 202
Representing Graphs in R	p. 205
Bibliographic Notes	p. 208
Simple Pattern Matching in Graphs	p. 211
Finding Paths in Graphs	p. 211
Distances in Graphs	p. 214
The Path Multiplicity Distance between Graphs	p. 220
The Tripartition Distance between Graphs	p. 228
The Nodal Distance between Graphs	p. 234
Finding Trees in Graphs	p. 238
The Statistical Error between Graphs	p. 243
Bibliographic Notes	p. 246
General Pattern Matching in Graphs	p. 247
Finding Subgraphs	p. 247
Finding Subgraphs Induced by Triplets	p. 248
Finding Common Subgraphs	p. 259
Maximum Agreement of Rooted Networks	p. 259
Comparing Graphs	p. 269
The Triplets Distance between Graphs	p. 269
Bibliographic Notes	p. 273
Elements of Perl	p. 275
Perl Scripts	p. 275
Overview of Perl	p. 294
Perl Quick Reference Card	p. 297
Bibliographic Notes	p. 304
Elements of R	p. 305
R Scripts	p. 305
Overview of R	p. 323
R Quick Reference Card	p. 329
Bibliographic Notes	p. 336
References	p. 339
Index	p. 351
Table of Contents provided by Ingram. All Rights Reserved.