Algorithms in Bioinformatics: A Practical Introduction

by Sung; Wing-Kin

• ISBN13: 9781420070330
• ISBN10: 1420070339
• Edition: 1st
• Format: Hardcover
• Copyright: 2009-11-24
• Publisher: Chapman & Hall/

Summary

This text focuses on using algorithms and discrete mathematics to solve biological problems. It systematically describes biological applications, the corresponding mathematical/computational problems, and various algorithmic solutions. The author also discusses the practical use of many algorithmic methods and describes what algorithms should be used in different situations. Each chapter contains an overview of the biological problem, a precise definition of the computational problem, a description of various methods, practical issues and further research, references to further reading, and a set of knowledge-testing exercises. Instruction and data for practical exercises are provided on the author's website.

Table of Contents

Preface	p. xv
Introduction to Molecular Biology	p. 1
DNA, RNA, and Protein	p. 1
Proteins	p. 1
DNA	p. 4
RNA	p. 9
Genome, Chromosome, and Gene	p. 10
Genome	p. 10
Chromosome	p. 10
Gene	p. 11
Complexity of the Organism versus Genome Size	p. 11
Number of Genes versus Genome Size	p. 11
Replication and Mutation of DNA	p. 12
Central Dogma (from DNA to Protein)	p. 13
Transcription (Prokaryotes)	p. 13
Transcription (Eukaryote)	p. 14
Translation	p. 15
Post-Translation Modification (PTM)	p. 17
Population Genetics	p. 18
Basic Biotechnological Tools	p. 18
Restriction Enzymes	p. 19
Sonication	p. 19
Cloning	p. 19
PCR	p. 20
Gel Electrophoresis	p. 22
Hybridization	p. 23
Next Generation DNA Sequencing	p. 24
Brief History of Bioinformatics	p. 26
Exercises	p. 27
Sequence Similarity	p. 29
Introduction	p. 29
Global Alignment Problem	p. 30
Needleman-Wunsch Algorithm	p. 32
Running Time Issue	p. 34
Space Efficiency Issue	p. 35
More on Global Alignment	p. 38
Local Alignment	p. 39
Semi-Global Alignment	p. 41
Gap Penalty	p. 42
General Gap Penalty Model	p. 43
Affine Gap Penalty Model	p. 43
Convex Gap Model	p. 45
Scoring Function	p. 50
Scoring Function for DNA	p. 50
Scoring Function for Protein	p. 51
Exercises	p. 53
Suffix Tree	p. 57
Introduction	p. 57
Suffix Tree	p. 57
Simple Applications of a Suffix Tree	p. 59
Exact String Matching Problem	p. 59
Longest Repeated Substring Problem	p. 60
Longest Common Substring Problem	p. 60
Longest Common Prefix (LCP)	p. 61
Finding a Palindrome	p. 62
Extracting the Embedded Suffix Tree of a String from the Generalized Suffix Tree	p. 63
Common Substring of 2 or More Strings	p. 64
Construction of a Suffix Tree	p. 65
Step 1: Construct the Odd Suffix Tree	p. 68
Step 2: Construct the Even Suffix Tree	p. 69
Step 3: Merge the Odd and the Even Suffix Trees	p. 70
Suffix Array	p. 72
Construction of a Suffix Array	p. 73
Exact String Matching Using a Suffix Array	p. 73
FM-Index	p. 76
Definition	p. 77
The occ Data Structure	p. 78
Exact String Matching Using the FM-Index	p. 79
Approximate Searching Problem	p. 81
Exercises	p. 82
Genome Alignment	p. 87
Introduction	p. 87
Maximum Unique Match (MUM)	p. 88
How to Find MUMs	p. 89
MUMmer1: LCS	p. 92
Dynamic Programming Algorithm in 0(n2) Time	p. 93
An O (n log n)-Time Algorithm	p. 93
MUMmer2 and MUMmer3	p. 96
Reducing Memory Usage	p. 97
Employing a New Alternative Algorithm for Finding MUMs	p. 97
Clustering Matches	p. 97
Extension of the Definition of MUM	p. 98
Mutation Sensitive Alignment	p. 99
Concepts and Definitions	p. 99
The Idea of the Heuristic Algorithm	p. 100
Experimental Results	p. 102
Dot Plot for Visualizing the Alignment	p. 103
Further Reading	p. 105
Exercises	p. 105
Database Search	p. 109
Introduction	p. 109
Biological Database	p. 109
Database Searching	p. 109
Types of Algorithms	p. 110
Smith-Waterman Algorithm	p. 111
FastA	p. 111
FastP Algorithm	p. 112
FastA Algorithm	p. 113
Blast	p. 114
Blast1	p. 115
Blast2	p. 116
Blast1 versus Blast2	p. 118
Blast versus FastA	p. 118
Statistics for Local Alignment	p. 119
Variations of the Blast Algorithm	p. 120
MegaBlast	p. 120
Blat	p. 121
PatternHunter	p. 121
PSI-Blast (Position-Specific Iterated Blast)	p. 123
Q-gram Alignment based on Suffix A Rrays (QUASAR)	p. 124
Algorithm	p. 124
Speeding Up and Reducing the Space for QUASAR	p. 127
Time Analysis	p. 127
Locality-Sensitive Hashing	p. 128
BWT-SW	p. 130
Aligning Query Sequence to Suffix Tree	p. 130
Meaningful Alignment	p. 133
Are Existing Database Searching Methods Sensitive Enough?	p. 136
Exercises	p. 136
Multiple Sequence Alignment	p. 139
Introduction	p. 139
Formal Definition of the Multiple Sequence Alignment Problem	p. 139
Methods for Solving the MSA Problem	p. 141
Dynamic Programming Method	p. 142
Center Star Method	p. 143
Progressive Alignment Method	p. 146
ClustalW	p. 147
Profile-Profile Alignment	p. 147
Limitation of Progressive Alignment Construction	p. 149
Iterative Method	p. 149
Muscle	p. 150
Log-Expectation (LE) Score	p. 151
Further Reading	p. 151
Exercises	p. 152
Phylogeny Reconstruction	p. 155
Introduction	p. 155
Mitochondrial DNA and Inheritance	p. 155
The Constant Molecular Clock	p. 155
Phylogeny	p. 156
Applications of Phylogeny	p. 157
Phylogenetic Tree Reconstruction	p. 158
Character-Based Phylogeny Reconstruction Algorithm	p. 159
Maximum Parsimony	p. 159
Compatibility	p. 165
Maximum Likelihood Problem	p. 172
Distance-Based Phylogeny Reconstruction Algorithm	p. 178
Additive Metric and Ultrametric	p. 179
Unweighted Pan Group Method with Arithmetic Mean (UPGMA)	p. 184
Additive Tree Reconstruction	p. 187
Nearly Additive Tree Reconstruction	p. 189
Can We Apply Distance-Based Methods Given a Character-State Matrix?	p. 190
Bootstrapping	p. 191
Can Tree Reconstruction Methods Infer the Correct Tree?	p. 192
Exercises	p. 193
Phylogeny Comparison	p. 199
Introduction	p. 199
Similarity Measurement	p. 200
Computing MAST by Dynamic Programming	p. 201
MAST for Unrooted Trees	p. 202
Dissimilarity Measurements	p. 203
Robinson-Foulds Distance	p. 204
Nearest Neighbor Interchange Distance (NNI)	p. 209
Subtree Transfer Distance (STT)	p. 210
Quartet Distance	p. 211
Consensus Tree Problem	p. 214
Strict Consensus Tree	p. 215
Majority Rule Consensus Tree	p. 216
Median Consensus Tree	p. 218
Greedy Consensus Tree	p. 218
R* Tree	p. 219
Further Reading	p. 220
Exercises	p. 222
Genome Rearrangement	p. 225
Introduction	p. 225
Types of Genome Rearrangements	p. 225
Computational Problems	p. 227
Sorting an Unsigned Permutation by Reversals	p. 227
Upper and Lower Bound on an Unsigned Reversal Distance	p. 228
4-Approximation Algorithm for Sorting an Unsigned Permutation	p. 229
2-Approximation Algorithm for Sorting an Unsigned Permutation	p. 230
Sorting a Signed Permutation by Reversals	p. 232
Upper Bound on Signed Reversal Distance	p. 232
Elementary Intervals, Cycles, and Components	p. 233
The Hannenhalli-Pevzner Theorem	p. 238
Further Reading	p. 243
Exercises	p. 244
Motif Finding	p. 247
Introduction	p. 247
Identifying Binding Regions of TFs	p. 248
Motif Model	p. 250
The Motif Finding Problem	p. 252
Scanning for Known Motifs	p. 253
Statistical Approaches	p. 254
Gibbs Motif Sampler	p. 255
MEME	p. 257
Combinatorial Approaches	p. 260
Exhaustive Pattern-Driven Algorithm	p. 261
Sample-Driven Approach	p. 262
Suffix Tree-Based Algorithm	p. 263
Graph-Based Method	p. 265
Scoring Function	p. 266
Motif Ensemble Methods	p. 267
Approach of MotifVoter	p. 268
Motif Filtering by the Discriminative and Consensus Criteria	p. 268
Sites Extraction and Motif Generation	p. 270
Can Motif Finders Discover the Correct Motifs?	p. 271
Motif Finding Utilizing Additional Information	p. 274
Regulatory Element Detection Using Correlation with Expression	p. 274
Discovery of Regulatory Elements by Phylogenetic Footprinting	p. 277
Exercises	p. 279
RNA Secondary Structure Prediction	p. 281
Introduction	p. 281
Base Interactions in RNA	p. 282
RNA Structures	p. 282
Obtaining RNA Secondary Structure Experimentally	p. 285
RNA Structure Prediction Based on Sequence Only	p. 286
Structure Prediction with the Assumption That There is No Pseudoknot	p. 286
Nussinov Folding Algorithm	p. 288
ZUKER Algorithm	p. 290
Time Analysis	p. 292
Speeding up Multi-Loops	p. 292
Speeding up Internal Loops	p. 294
Structure Prediction with Pseudoknots	p. 296
Definition of a Simple Pseudoknot	p. 296
Akutsu's Algorithm for Predicting an RNA Secondary Structure with Simple Pseudoknots	p. 297
Exercises	p. 300
Peptide Sequencing	p. 305
Introduction	p. 305
Obtaining the Mass Spectrum of a Peptide	p. 306
Modeling the Mass Spectrum of a Fragmented Peptide	p. 310
Amino Acid Residue Mass	p. 310
Fragment Ion Mass	p. 310
De Novo Peptide Sequencing Using Dynamic Programming	p. 312
Scoring by Considering y-Ions	p. 313
Scoring by Considering y-Ions and b-Ions	p. 314
De Novo Sequencing Using Graph-Based Approach	p. 317
Peptide Sequencing via Database Search	p. 319
Further Reading	p. 320
Exercises	p. 321
Population Genetics	p. 323
Introduction	p. 323
Locus, Genotype, Allele, and SNP	p. 323
Genotype Frequency and Allele Frequency	p. 324
Haplotype and Phenotype	p. 325
Technologies for Studying the Human Population .	p. 325
Bioinformatics Problems	p. 325
Hardy-Weinberg Equilibrium	p. 326
Linkage Disequilibrium	p. 327
D and D'	p. 328
r2	p. 328
Genotype Phasing	p. 328
Clark's Algorithm	p. 329
Perfect Phylogeny Haplotyping Problem	p. 330
Maximum Likelihood Approach	p. 334
Phase Algorithm	p. 336
Tag SNP Selection	p. 337
Zhang et al's Algorithm	p. 338
IdSelect	p. 339
Association Study	p. 339
Categorical Data Analysis	p. 340
Relative Risk and Odds Ratio	p. 341
Linear Regression	p. 342
Logistic Regression	p. 343
Exercises	p. 344
References	p. 349
Index	p. 375
Table of Contents provided by Ingram. All Rights Reserved.