Genomic Perl : from bioinformatics basics to working code /

Preface p. xiii
Acknowledgments p. xvii
The Central Dogma p. 1
DNA and RNA p. 1
Chromosomes p. 2
Proteins p. 4
The Central Dogma p. 5
Transcription and Translation in Perl p. 7
Exercise p. 12
Complete Program Listings p. 12
Bibliographic Notes p. 14
RNA Secondary Structure p. 16
Messenger and Catalytic RNA p. 16
Levels of RNA Structure p. 17
Constraints on Secondary Structure p. 18
RNA Secondary Structures in Perl p. 20
Counting Hydrogen Bonds p. 21
Folding RNA p. 24
Exercises p. 28
Complete Program Listings p. 29
Bibliographic Notes p. 29
Comparing DNA Sequences p. 30
DNA Sequencing and Sequence Assembly p. 30
Alignments and Similarity p. 32
Alignment and Similarity in Perl p. 36
Exercises p. 40
Complete Program Listings p. 42
Bibliographic Notes p. 43
Predicting Species: Statistical Models p. 44
Perl Subroutine Libraries p. 49
Species Prediction in Perl p. 51
Exercises p. 53
Complete Program Listings p. 53
Bibliographic Note p. 54
Substitution Matrices for Amino Acids p. 55
More on Homology p. 57
Deriving Substitution Matrices from Alignments p. 57
Substitution Matrices in Perl p. 60
The PAM Matrices p. 65
PAM Matrices in Perl p. 68
Exercises p. 70
Complete Program Listings p. 71
Bibliographic Notes p. 71
Sequence Databases p. 72
FASTA Format p. 73
GenBank Format p. 73
GenBank's Feature Locations p. 75
Reading Sequence Files in Perl p. 79
Object-Oriented Programming in Perl p. 80
The SimpleReader Class p. 81
Hiding File Formats with Method Inheritance p. 85
Exercises p. 89
Complete Program Listings p. 91
Bibliographic Notes p. 92
Local Alignment and the BLAST Heuristic p. 93
The Smith-Waterman Algorithm p. 94
The BLAST Heuristic p. 96
Preprocessing the Query String p. 98
Scanning the Target String p. 99
Implementing BLAST in Perl p. 100
Exercises p. 106
Complete Program Listings p. 108
Bibliographic Notes p. 108
Statistics of BLAST Database Searches p. 109
BLAST Scores for Random DNA p. 109
BLAST Scores for Random Residues p. 114
BLAST Statistics in Perl p. 116
Interpreting BLAST Output p. 123
Exercise p. 125
Complete Program Listings p. 126
Bibliographic Notes p. 126
Multiple Sequence Alignment I p. 127
Extending the Needleman-Wunsch Algorithm p. 128
NP-Completeness p. 131
Alignment Merging: A Building Block for Heuristics p. 132
Merging Alignments in Perl p. 133
Finding a Good Merge Order p. 137
Exercises p. 139
Complete Program Listings p. 139
Bibliographic Notes p. 139
Multiple Sequence Alignment II p. 141
Pushing through the Matrix by Layers p. 141
Tunnel Alignments p. 147
A Branch-and-Bound Method p. 149
The Branch-and-Bound Method in Perl p. 152
Exercises p. 153
Complete Program Listings p. 154
Bibliographic Notes p. 154
Phylogeny Reconstruction p. 155
Parsimonious Phylogenies p. 155
Assigning Sequences to Branch Nodes p. 157
Pruning the Trees p. 160
Implementing Phylogenies in Perl p. 162
Building the Trees in Perl p. 168
Exercise p. 171
Complete Program Listings p. 171
Bibliographic Notes p. 171
Protein Motifs and PROSITE p. 173
The PROSITE Database Format p. 174
Patterns in PROSITE and Perl p. 175
Suffix Trees p. 177
Suffix Links p. 184
The Efficiency of Adding p. 188
Suffix Trees for PROSITE Searching p. 189
Exercises p. 193
Complete Program Listings p. 195
Bibliographic Notes p. 195
Fragment Assembly p. 196
Shortest Common Superstrings p. 196
Practical Issues and the PHRAP Program p. 202
Reading Inputs for Assembly p. 204
Aligning Reads p. 207
Adjusting Qualities p. 212
Assigning Reads to Contigs p. 217
Developing Consensus Sequences p. 222
Exercises p. 227
Complete Program Listings p. 230
Bibliographic Notes p. 230
Coding Sequence Prediction with Dicodons p. 231
A Simple Trigram Model p. 232
A Hexagram Model p. 235
Predicting All Genes p. 237
Gene Finding in Perl p. 237
Exercises p. 244
Complete Program Listings p. 244
Bibliographic Notes p. 244
Satellite Identification p. 245
Finding Satellites Efficiently p. 246
Suffix Testing p. 247
Satellite Testing p. 249
Finding Satellites in Perl p. 251
Exercises p. 255
Complete Program Listings p. 256
Bibliographic Notes p. 256
Restriction Mapping p. 257
A Backtracking Algorithm for Partial Digests p. 258
Partial Digests in Perl p. 260
Uncertain Measurement and Interval Arithmetic p. 262
Backtracking with Intervals p. 263
Interval Arithmetic in Perl p. 265
Partial Digests with Uncertainty in Perl p. 267
A Final Check for Interval Consistency p. 269
Exercises p. 271
Complete Program Listings p. 273
Bibliographic Notes p. 274
Rearranging Genomes: Gates and Hurdles p. 275
Sorting by Reversals p. 276
Making a Wish List p. 278
Analyzing the Interaction Relation p. 279
Clearing the Hurdles p. 280
Happy Cliques p. 284
Sorting by Reversals in Perl p. 287
Exercise p. 297
Appendix: Correctness of Choice of Wish from Happy Clique p. 298
Complete Program Listings p. 298
Bibliographic Notes p. 298
Drawing RNA Cloverleaves p. 300
Exercises p. 304
Complete Program Listings p. 306
Bibliographic Notes p. 306
Space-Saving Strategies for Alignment p. 307
Finding Similarity Scores Compactly p. 307
Finding Alignments Compactly p. 309
Exercises p. 312
Complete Program Listings p. 312
Bibliographic Note p. 312
A Data Structure for Disjoint Sets p. 313
Union by Rank p. 314
Path Compression p. 315
Complete Program Listings p. 315
Bibliographic Note p. 317
Suggestions for Further Reading p. 318
Bibliography p. 319
Index p. 325