Bioinformatics: Sequence Alignment and Markov Models

by Sharma, Kal

• ISBN13: 9780071593069
• ISBN10: 0071593063
• Edition: 1st
• Format: Hardcover
• Copyright: 2008-09-04
• Publisher: McGraw-Hill Education

Summary

GET FULLY UP-TO-DATE ON BIOINFORMATICS-THE TECHNOLOGY OF THE 21ST CENTURYBioinformaticsshowcases the latest developments in the field along with all the foundational information you'll need. It provides in-depth coverage of a wide range of autoimmune disorders and detailed analyses of suffix trees, plus late-breaking advances regarding biochips and genomes.Featuring helpful gene-finding algorithms,Bioinformaticsoffers key information on sequence alignment, HMMs, HMM applications, protein secondary structure, microarray techniques, and drug discovery and development. Helpful diagrams accompany mathematical equations throughout, and exercises appear at the end of each chapter to facilitate self-evaluation.This thorough, up-to-date resource features: Worked-out problems illustrating concepts and models End-of-chapter exercises for self-evaluation Material based on student feedback Illustrations that clarify difficult math problems A list of bioinformatics-related websitesBioinformaticscovers: Sequence representation and alignment Hidden Markov models Applications of HMMs Gene finding Protein secondary structure prediction Microarray techniques Drug discovery and development Internet resources and public domain databases

Author Biography

Kal Renganathan Sharma, Ph.D., P.E., has written five books, 11 journal articles, and hundreds of conference papers. He has held a number of high-level positions at engineering colleges and universities. Dr. Sharma currently teaches at Prairie View AAndM University in Prairie View, Texas.

Table of Contents

Preface	p. xi
Acknowledgments	p. xv
Preliminaries	p. 1
Molecular Biology	p. 2
Amino Acids and Proteins	p. 2
Structures of Proteins	p. 3
Sequence Distribution of Insulin	p. 6
Bioseparation Techniques	p. 9
Nucleic Acids and Genetic Code	p. 12
Genomes-Diversity, Size, and Structure	p. 20
Probability and Statistics	p. 23
Three Definitions of Probability	p. 24
Bayes' Theorem and Conditional Probability	p. 25
Independent Events and Bernoulli's Theorem	p. 25
Discrete Probability Distributions	p. 26
Continuous Probability Distributions	p. 28
Statistical Inference and Hypothesis Testing	p. 30
Which Is Larger, 2[superscript n] or n[superscript 2]?	p. 31
Big O Notation and Asymptotic Order of Functions	p. 32
Summary	p. 33
References and Sources	p. 34
Exercises	p. 35
Sequence Alignment and Representation
Alignment of a Pair of Sequences	p. 41
Objectives	p. 41
Introduction to Pairwise Sequence Alignment	p. 41
Why Study Sequence Alignment	p. 43
Alignment Grading Function	p. 47
Optimal Global Alignment of a Pair of Sequences	p. 51
Needleman and Wunsch Algorithm	p. 51
Dynamic Programming	p. 55
Time Analysis and Space Efficiency	p. 56
Dynamic Arrays and O(N) Space	p. 56
Subquadratic Algorithms for Longest Common Subsequence Problems	p. 57
Optimal Local Alignment of a Pair of Sequences	p. 59
Smith and Waterman Algorithm	p. 59
Affine Gap Model	p. 60
Greedy Algorithms for Pairwise Alignment	p. 63
Other Alignment Methods	p. 65
Pam and Blosum Matrices	p. 66
Summary	p. 69
References	p. 70
Further Reading	p. 71
Exercises	p. 71
Sequence Representation and String Algorithms	p. 85
Objectives	p. 85
Suffix Trees	p. 85
Overview of Suffix Trees in Sequence Analysis	p. 85
Algorithm for Suffix Tree Representation of a Sequence	p. 88
Streaming a Sequence Against a Suffix Tree	p. 89
String Algorithms	p. 91
Rabin-Karp Algorithm	p. 92
Knuth-Morris-Pratt (KMP) Algorithm	p. 92
Boyer-Moore Algorithm	p. 94
Finite Automaton	p. 96
Suffix Trees in String Algorithms	p. 97
Look-up Tables	p. 99
Summary	p. 100
References	p. 101
Exercises	p. 102
Multiple-Sequence Alignment	p. 115
Objectives	p. 115
What Is Multiple-Sequence Alignment?	p. 115
Defenitions of Multiple Global Alignment and Sum of Pairs	p. 117
Multiple Global Alignment	p. 117
Sum of Pairs	p. 117
Optimal MSA by Dynamic Programming	p. 117
Theorem of Wang and Jiang [2]	p. 118
What Are NP Complete Problems?	p. 118
Center-Star-Alignment Algorithm [4]	p. 119
Time Analysis	p. 119
Progressive Alignment Methods	p. 121
The Consensus Sequence	p. 122
Greedy Method	p. 123
Geometry of Multiple Sequences	p. 123
Summary	p. 125
References	p. 125
Exercises	p. 126
Probability Models
Hidden Markov Models and Applications	p. 133
Objectives	p. 133
Introduction	p. 133
kth-order Markov Chain	p. 134
DNA Sequence and Geometric Distribution [2-4]	p. 135
Three Questions in the HMM	p. 143
Evaluation Problem and Forward Algorithm	p. 146
Decoding Problem and Viterbi Algorithm	p. 146
Relative Entropy	p. 147
Probabilistic Approach to Phylogeny	p. 149
Sequence Alignment Using HMMs	p. 152
Protein Families	p. 153
Wheel HMMs to Model Periodicity in DNA	p. 156
Generalized HMM (GHMM)	p. 157
Database Mining	p. 160
Multiple Alignments	p. 160
Classification Using HMMs	p. 161
Signal Peptide and Signal Anchor Prediction by HMMs	p. 162
Markov Model and Chargaff's Parity Rules	p. 163
Summary	p. 164
References	p. 165
Exercises	p. 166
Gene Finding, Protein Secondary Structure	p. 179
Objectives	p. 179
Introduction	p. 179
Relative Entropy Site-Selection Problem	p. 180
Greedy Approach	p. 180
Gibbs Sampler	p. 181
Maximum-Subsequence Problem	p. 182
Bates and Constable Algorithm	p. 182
Binomial Heap [4-7]	p. 182
Interpolated Markov Model (IMM)	p. 184
Shine Dalgarno SD Sites Finding	p. 185
Gene Annotation Methods	p. 187
Secondary Structures of Proteins	p. 191
Neural Networks	p. 193
PHD Architecture of Rost and Sander	p. 196
Ensemble Method of Riis and Krogh [23]	p. 198
Protein Secondary Structure Using HMMs	p. 199
DAG RNNs: Directed Acyclic Graphs and Recursive NN Architecture and 3D Protein Structure Prediction	p. 200
Annotate Subcellular Localization for Protein Structure	p. 201
Summary	p. 203
References	p. 204
Exercises	p. 206
Measurement Techniques
Biochips	p. 213
Objectives	p. 213
Introduction	p. 213
Microarrays, Biochips, and Disease	p. 214
Five Steps and Ten Tips	p. 218
Applications of Microarrays	p. 220
Microarray Detection	p. 223
Fluorescence Detection and Optical Requirements	p. 223
Confocal Scanning Microscope	p. 224
Microarray Surfaces	p. 227
Phosphoramadite Synthesis	p. 231
Microarray Manufacture	p. 233
Normalization for cDNA Microarray Data	p. 236
Summary	p. 240
References	p. 241
Exercises	p. 242
Electrophoretic Techniques and Finite Speed of Diffusion	p. 245
Objectives	p. 245
Role of Electrophoresis in the Measurement of Sequence Distribution	p. 245
Fick's Laws of Molecular Diffusion	p. 246
Generalized Fick's Law of Diffusion	p. 249
Derivation of a Generalized Fick's Law of Diffusion	p. 251
Taitel Paradox and Final Time Condition	p. 254
Relativistic Transformation of Coordinates	p. 259
Periodic Boundary Condition	p. 267
Electrophoresis Apparatus	p. 269
Electrophoretic Term, Ballistic Term, and Fick Term in the Governing Equation	p. 270
Summary	p. 274
References	p. 275
Exercises	p. 276
Internet Hotlinks to Public-Domain Databases	p. 287
PERL for Bioinformaticists	p. 299
Index	p. 303
Table of Contents provided by Ingram. All Rights Reserved.