Combinatorial Pattern Matching Algorithms in Computational Biology using Perl and R Book

Foreword

Preface

1 Introduction 1

1.1 Combinatorial Pattern Matching 3

1.2 Computational Biology 4

1.3 A Motivating Example: Gene Prediction 4

Bibliographic Notes 17

I Sequence Pattern Matching

2 Sequences 21

2.1 Sequences in Mathematics 21

2.1.1 Counting Labeled Sequences 22

2.2 Sequences in Computer Science 24

2.2.1 Traversing Labeled Sequences 26

2.3 Sequences in Computational Biology 29

2.3.1 Reverse Complementing DNA Sequences 31

2.3.2 Counting RNA Sequences 33

2.3.3 Generating DNA Sequences 35

2.3.4 Representing Sequences in Perl 38

2.3.5 Representing Sequences in R 40

Bibliographic Notes 42

3 Simple Pattern Matching in Sequences 43

3.1 Finding Words in Sequences 43

3.1.1 Word Composition of Sequences 43

3.1.2 Alignment Free Comparison of Sequences 49

Bibliographic Notes 52

4 General Pattern Matching in Sequences 53

4.1 Finding Subsequences 53

4.1.1 Suffix Arrays 56

4.2 Finding Common Subsequences 67

4.2.1 Generalized Suffix Arrays 74

4.3 Comparing Sequences 86

4.3.1 Edit Distance-Based Comparison of Sequences 86

4.3.2 Alignment-Based Comparison of Sequences 95

Bibliographic Notes 110

II Tree Pattern Matching

5 Trees 115

5.1 Trees in Mathematics 115

5.1.1 Counting Labeled Trees 115

5.2 Trees in Computer Science 117

5.2.1 Traversing Rooted Trees 118

5.3 Trees in Computational Biology 118

5.3.1 The Newick Linear Representation 123

5.3.2 Counting Phylogenetic Trees 125

5.3.3 Generating Phylogenetic Trees 126

5.3.4 Representing Trees in Perl 128

5.3.5 Representing Trees in R 131

Bibliographic Notes 135

6 Simple Pattern Matching in Trees 137

6.1 Finding Paths in Unrooted Trees 137

6.1.1Distances in Unrooted Trees 138

6.1.2 The Partition Distance between Unrooted Trees 140

6.1.3 The Nodal Distance between Unrooted Trees 144

6.2 Finding Paths in Rooted Trees 148

6.2.1 Distances in Rooted Trees 150

6.2.2 The Partition Distance between Rooted Trees 151

6.2.3 The Nodal Distance between Rooted Trees 151

Bibliographic Notes 152

7 General Pattern Matching in Trees 155

7.1 Finding Subtrees 155

7.1.1 Finding Subtrees Induced by Triplets 156

7.1.2 Finding Subtrees Induced by Quartets 159

7.2 Finding Common Subtrees 161

7.2.1 Maximum Agreement of Rooted Trees 161

7.2.2 Maximum Agreement of Unrooted Trees 172

7.3 Comparing Trees 172

7.3.1 The Triplets Distance between Rooted Trees 172

7.3.2 The Quartets Distance between Unrooted Trees 175

Bibliographic Notes 178

III Graph Pattern Matching

8 Graphs 181

8.1 Graphs in Mathematics 181

8.1.1 Counting Labeled Graphs 182

8.2 Graphs in Computer Science 183

8.2.1 Traversing Directed Graphs 183

8.3 Graphs in Computational Biology 184

8.3.1 The eNewick Linear Representation 193

8.3.2 Counting Phylogenetic Networks 195

8.3.3 Generating Phylogenetic Networks 198

8.3.4 Representing Graphs in Perl 202

8.3.5 Representing Graphs in R 205

Bibliographic Notes 208

9 Simple Pattern Matching in Graphs 211

9.1 Finding Paths in Graphs 211

9.1.1 Distances in Graphs 214

9.1.2 The Path Multiplicity Distance between Graphs 220

9.1.3 The Tripartition Distance between Graphs 228

9.1.4 The Nodal Distance between Graphs 234

9.2 Finding Trees in Graphs 238

9.2.1 The Statistical Error between Graphs 243

Bibliographic Notes 246

10 General Pattern Matching in Graphs 247

10.1 Finding Subgraphs 247

10.1.1 Finding Subgraphs Induced by Triplets 248

10.2 Finding Common Subgraphs 259

10.2.1 Maximum Agreement of Rooted Networks 259

10.3 Comparing Graphs 269

10.3.1 The Triplets Distance between Graphs 269

Bibliographic Notes 273

A Elements of Perl 275

A.1 Perl Scripts 275

A.2 Overview of Perl 294

A.3 Perl Quick Reference Card 297

Bibliographic Notes 304

B Elements of R 305

B.1 R Scripts 305

B.2 Overview of R 323

B.3 R Quick Reference Card 329

Bibliographic Notes 336

References 339

Index 351