Theory And Mathematical Methods In Bioinformatics

by Shen, Shiyi; Tuszynski, Jack A.

• ISBN13: 9783540748908
• ISBN10: 3540748903
• Edition: 1st
• Format: Hardcover
• Copyright: 2008-04-20
• Publisher: Springer Nature

Summary

This monograph addresses, in a systematic and pedagogical manner, the mathematical methods and the algorithms required to deal with the molecularly based problems of bioinformatics. The book will be useful to students, research scientists and practitioners of bioinformatics and related fields, especially those who are interested in the underlying mathematical methods and theory. Among the methods presented in the book, prominent attention is given to pair-wise and multiple sequence alignment algorithms, stochastic models of mutations, modulus structure theory and protein configuration analysis. Strong links to the molecular structures of proteins, DNA and other biomolecules and their analyses are developed. In particular, for proteins an in-depth exposition of secondary structure prediction methods should be a valuable tool in both molecular biology and in applications to rational drug design. The book can also be used as a textbook and for this reason most of the chapters include exercises and problems at the level of a graduate program in bioinformatics.

Author Biography

Shiyi ShenSince 1985, professor of mathematics, 1987-1998: chair of the department of mathematics, and the dean of the college of mathematical sciences; a standing committee of China Mathematical Society, the director of the Tianjin Mathematical Society. 1984-1986: visiting scholar of Cornell University; visiting scholar of Stanford University, and visiting researcher at the Hong Kong Chinese University. Shiyi Shen's fields of scientific interest are informatics and bioinformatics. His publications include about 60 journal papers and 6 books (Chinese). Jack TuszynskiProfessor (from 07/1993 until present). Department of Physics, University of Alberta Research Manager of the Neurons Group, (May 1, 2000- June 1, 2001) Starlab NV, Brussels, Belgium Visiting Professor, Department of Physics, Ecole Normale Superieure, Lyon, France (December 2000, June-September 2001) Senior Visiting Fellow, Laboratory of Biomolecular Dynamics, Catholic University of Leuven, Belgium (November-December 2000 and February-March 2001) Adjunct Professor (from March 1, 2000). Department of Oncology, Division of Medical Physics, University of Alberta. Visiting Professor (07/1995 - 09/1995). Institut f+â-+r Theoretische Physik, J. Liebig-Universit+â-ñt Gie+â++en, Germany. Visiting Professor (07/1993 - 08/1994). Institut f+â-+r Theoretische Physik, H.Heine-Universit+â-ñt D+â-+sseldorf, Germany. McCalla Professor (07/1992 - 07/1993). Department of Physics, University of Alberta. Guest Professor (summer 1992), Visting Scientist (summer 1994, spring 1996). Institute of Mathematical Modelling, Danish Technical University, Lyngby. Associate Professor (07/1990 - 07/1993). Department of Physics, University of Alberta, Edmonton. Tenure granted effective July 1, 1991. Assistant Professor (01/1988 - 06/1990). Department of Physics, University of Alberta, Edmonton. Field: theoretical condensed matter physics. Honorary Assistant Professor (01/1988 - 01/1991). Department of Physics, Memorial University of Newfoundland, St. John's, Newfoundland. Assistant Professor (09/1983 - 01/1988). Department of Physics, Memorial University of Newfoundland, St. John's. Field: theoretical condensed matter physics. Tenure granted as of September 1, 1987. Post-doctoral Fellow (04/1983 - 09/1983). Chemistry Department, The University of Calgary. Supervisor: Professor R. Paul. Field: Molecular biophysics.

Table of Contents

Outline	p. 1
Mutations and Alignments
Introduction	p. 5
Mutation and Alignment	p. 5
Classification of Biological Sequences	p. 5
Definition of Mutations and Alignments	p. 6
Progress on Alignment Algorithms and Problems to Be Solved	p. 8
Mathematical Problems Driven by Alignment and Structural Analysis	p. 12
Basic Concepts in Alignment and Mathematical Models	p. 13
Mutation and Alignment	p. 13
Dynamic Programming-Based Algorithms for Pairwise Alignment	p. 17
Introduction to Dynamic Programming-Based Algorithms	p. 17
The Needleman-Wunsch Algorithm, the Global Alignment Algorithm	p. 18
The Smith-Waterman Algorithm	p. 21
Other Notations	p. 24
Correlation Functions of Local Sequences	p. 24
Pairwise Alignment Matrices Among Multiple Sequences	p. 25
Remarks	p. 26
Exercises, Analyses, and Computation	p. 27
Stochastic Models of Mutations and Structural Analysis	p. 29
Stochastic Sequences and Independent Sequence Pairs	p. 29
Definitions and Notations of Stochastic Sequences	p. 29
Independently and Identically Distributed Sequences	p. 31
Independent Stochastic Sequence Pairs	p. 33
Local Penalty Function and Limit Properties of 2-Dimensional Stochastic Sequences	p. 36
Stochastic Models of Flow Raised by Sequence Mutations	p. 37
Bernoulli Processes	p. 37
Poisson Flow	p. 40
Mutated Flows Resulting from the Four Mutation Types	p. 43
Stochastic Models of Type-I Mutated Sequences	p. 45
Description of Type-I Mutation	p. 45
Properties of Type-I Mutations	p. 47
Type-II Mutated Sequences	p. 50
Description of Type-II Mutated Sequences	p. 51
Stochastic Models of Type-II Mutated Sequences	p. 51
Error Analysis of Type-II Mutated Sequences	p. 54
The Mixed Stochastic Models Caused by Type-I and Type-II Mutations	p. 57
Mutated Sequences Resulting from Type-III and Type-IV Mutations	p. 58
Stochastic Models of Type-III and Type-IV Mutated Sequences	p. 58
Estimation of the Errors Caused by Type-III and Type-IV Mutations	p. 59
Stochastic Models of Mixed Mutations	p. 61
Exercises	p. 64
Modulus Structure Theory	p. 67
Modulus Structure of Expanded and Compressed Sequences	p. 67
The Modulus Structures of Expanded Sequences and Compressed Sequences	p. 67
The Order Relation and the Binary Operators on the Set of Expanded Modes	p. 71
Operators Induced by Modes	p. 73
Modulus Structure of Sequence Alignment	p. 76
Modulus Structures Resulting from Multiple Alignment	p. 76
Structure Analysis of Pairwise Alignment	p. 78
Properties of Pairwise Alignment	p. 81
The Order Relation and the Operator Induced by Modulus Structure	p. 84
Analysis of Modulus Structures Resulting from Sequence Mutations	p. 85
Mixed Sequence Mutations	p. 85
Structure Analysis of Purely Shifting Mutations	p. 87
Structural Representation of Mixed Mutation	p. 93
The Binary Operations of Sequence Mutations	p. 93
The Order Relationship Among the Modes of Shifting Mutations	p. 93
Operators Induced by Modes of Shifting Mutations	p. 96
Error Analysis for Pairwise Alignment	p. 100
Uniform Alignment of Mutation Sequences	p. 100
Optimal Alignment and Uniform Alignment	p. 102
Error Analysis of Uniform Alignment	p. 104
Local Modification of Sequence Alignment	p. 106
Exercises	p. 107
Super Pairwise Alignment	p. 109
Principle of Statistical Decision-Based Algorithms for Pairwise Sequences	p. 109
Uniform Alignment and Parameter Estimation for Pairwise Sequences	p. 109
The Locally Uniform Alignment Resulting from Local Mutation	p. 111
The Estimations of Mutation Position and Length	p. 113
Operation Steps of the SPA and Its Improvement	p. 115
Operation Steps of the SPA	p. 115
Some Unsolved Problems and Discussions of SPA	p. 118
Local Modifications for Sequence Alignment	p. 121
Index Analysis of SPA	p. 122
The Statistical Features of Estimations	p. 122
Improvement of the Algorithm to Estimate <$>{\hat s}^\ast<$>	p. 128
The Computational Complexity of the SPA	p. 131
Estimation for the Error of Uniform Alignment Induced by a Hybrid Stochastic Mutation Sequence	p. 132
Applications of Sequence Alignment and Examples	p. 135
Several Applications of Sequence Alignment	p. 135
Examples of Pairwise Alignment	p. 137
Exercises	p. 146
Multiple Sequence Alignment	p. 149
Pairwise Alignment Among Multiple Sequences	p. 149
Using Pairwise Alignment to Process Multiple Sequences	p. 149
Topological Space Induced by Pairwise Alignment of Multiple Sequences	p. 150
Optimization Criteria of MA	p. 156
The Definition of MA	p. 156
Uniform Alignment Criteria and SP-Optimization Criteria for Multiple Sequences	p. 156
Discussion of the Optimization Criterion of MA	p. 160
Optimization Problem Based on Shannon Entropy	p. 164
The Similarity Rate and the Rate of Virtual Symbols	p. 170
Super Multiple Alignment	p. 172
The Situation for MA	p. 172
Algorithm of SMA	p. 174
Comparison Among Several Algorithms	p. 179
Exercises, Analyses, and Computation	p. 180
Network Structures of Multiple Sequences Induced by Mutation	p. 183
General Method of Constructing the Phylogenetic Tree	p. 183
Summary	p. 183
Distance-Based Methods	p. 184
Feature-Based (Maximum Parsimony) Methods	p. 188
Maximum-Likelihood Method and the Bayes Method	p. 191
Network Structure Generated by MA	p. 197
Graph and Tree Generated by MA	p. 197
Network System Generated by Mutations of Multiple Sequences	p. 200
The Application of Mutation Network Analysis	p. 206
Selection of the Data Sample	p. 206
The Basic Steps to Analyze the Sequences	p. 208
Remarks on the Alignment and Output Analysis	p. 210
Exercises, Analyses, and Computation	p. 216
Alignment Space	p. 219
Construction of Alignment Space and Its Basic Theorems	p. 219
What Is Alignment Space?	p. 219
The Alignment Space Under General Metric	p. 221
The Analysis of Data Structures in Alignment Spaces	p. 224
Maximum Score Alignment and Minimum Penalty Alignment	p. 224
The Structure Mode of the Envelope of Pairwise Sequences	p. 226
Uniqueness of the Maximum Core and Minimum Envelope of Pairwise Sequences	p. 230
The Envelope and Core of Pairwise Sequences	p. 231
The Envelope of Pairwise Sequences and Its Alignment Sequences	p. 233
The Counting Theorem of the Optimal Alignment and Alignment Spheroid	p. 237
The Counting Theorem of the Optimal Alignment	p. 237
Alignment Spheroid	p. 238
The Virtual Symbol Operation in the Alignment Space	p. 241
The Definition of the Virtual Symbol Operator	p. 241
The Modulus Structure of the Virtual Symbol Operator	p. 243
The Isometric Operation and Micro-Adapted Operation of Virtual Symbols	p. 247
Exercises, Analyses, and Computation	p. 250
Protein Configuration Analysis
Background Information Concerning the Properties of Proteins	p. 255
Amino Acids and Peptide Chains	p. 255
Amino Acids	p. 255
Basic Structure of Peptide Chains	p. 257
Brief Introduction of Protein Configuration Analysis	p. 259
Protein Structure Database	p. 259
Brief Introduction to Protein Structure Analysis	p. 260
Analysis and Exploration	p. 263
Informational and Statistical Iterative Analysis of Protein Secondary Structure Prediction	p. 265
Protein Secondary Structure Prediction and Informational and Statistical Iterative Analysis	p. 265
Protein Secondary Structure Prediction	p. 265
Data Source and Informational Statistical Model of PSSP	p. 267
Informational and Statistical Characteristic Analysis on Protein Secondary Structure	p. 269
Informational and Statistical Calculation Algorithms for PSSP	p. 271
Informational and Statistical Calculation for PSSP	p. 271
Informational and Statistical Calculation Algorithm for PSSP	p. 273
Discussion of the Results	p. 275
Exercises, Analyses, and Computation	p. 277
Three-Dimensional Structure Analysis of the Protein Backbone and Side Chains	p. 279
Space Conformation Theory of Four-Atom Points	p. 279
Conformation Parameter System of Four-Atom Space Points	p. 279
Phase Analysis on Four-Atom Space Points	p. 283
Four-Atom Construction of Protein 3D Structure	p. 286
Triangle Splicing Structure of Protein Backbones	p. 288
Triangle Splicing Belts of Protein Backbones	p. 288
Characteristic Analysis of the Protein Backbone Triangle Splicing Belts	p. 291
Structure Analysis of Protein Side Chains	p. 292
The Setting of Oxygen Atom O and Atom CB on the Backbones	p. 293
Statistical Analysis of the Structures of Tetrahedrons VO, VB	p. 295
Exercises, Analyses, and Computation	p. 297
Alignment of Primary and Three-Dimensional Structures of Proteins	p. 299
Structure Analysis for Protein Sequences	p. 299
Alignment of Protein Sequences	p. 299
Differences and Similarities Between the Alignment of Protein Sequences and of DNA Sequences	p. 301
The Penalty Functions for the Alignment of Protein Sequences	p. 302
Key Points of the Alignment Algorithms of Protein Sequences	p. 306
Alignment of Protein Three-Dimensional Structures	p. 307
Basic Idea and Method of the Alignment of Three-Dimensional Structures	p. 307
Example of Computation in the Discrete Case	p. 310
Example of Computation in Consecutive Case	p. 314
Exercises, Analyses, and Computation	p. 323
Depth Analysis of Protein Spatial Structure	p. 325
Depth Analysis of Amino Acids in Proteins	p. 325
Introduction to the Concept of Depth	p. 325
Definition and Calculation of Depth	p. 327
Proof of Theorem 40	p. 329
Proof of Theorem 41	p. 334
Statistical Depth Analysis of Protein Spatial Particles	p. 335
Calculation for Depth Tendency Factor of Amino Acid	p. 335
Analysis of Depth Tendency Factor of Amino Acid	p. 338
Prediction for Depth of Multiple Peptide Chains in Protein Spatial Structure	p. 342
The Level Function in Spatial Particle System	p. 347
An Example	p. 347
Exercises	p. 353
Analysis of the Morphological Features of Protein Spatial Structure	p. 355
Introduction	p. 355
Morphological Features of Protein Spatial Structure	p. 355
Several Basic Definitions and Symbols	p. 357
Preliminary Analysis of the Morphology of Spatial Particle System	p. 360
Example	p. 362
Structural Analysis of Cavities and Channels in a Particle System	p. 366
Definition, Classification and Calculation of Cavity	p. 366
Relationship Between Cavities	p. 368
Example	p. 371
Analysis of ¿-Accessible Radius in Spatial Particle System	p. 371
Structural Analysis of a Directed Polyhedron	p. 371
Definition and Basic Properties of ¿-Accessible Radius	p. 377
Basic Principles and Methods of ¿-Accessible Radius	p. 378
Recursive Algorithm of ¿-Function	p. 382
Calculation of the ¿-Function Generated by 0-Level Convex Hull	p. 382
Recursive Calculation of ¿-Function	p. 384
Example	p. 387
Proof of Relative Theorems and Reasoning of Computational Formulas	p. 387
Proofs of Several Theorems	p. 387
Reasoning of Several Formulas	p. 390
Exercises	p. 394
Semantic Analysis for Protein Primary Structure	p. 395
Semantic Analysis for Protein Primary Structure	p. 395
The Definition of Semantic Analysis for Protein Primary Structure	p. 395
Information-Based Stochastic Models in Semantic Analysis	p. 397
Determination of Local Words Using Informational and Statistical Means and the Relative Entropy Density Function for the Second and Third Ranked Words	p. 400
Semantic Analysis for Protein Primary Structure	p. 402
Permutation and Combination Methods for Semantic Structures	p. 412
Notation Used in Combinatorial Graph Theory	p. 416
The Complexity of Databases	p. 420
Key Words and Core Words in a Database	p. 421
Applications of Combinatorial Analysis	p. 425
Exercises, Analyses, and Computation	p. 429
Epilogue	p. 431
References	p. 433
Index	p. 441
Table of Contents provided by Publisher. All Rights Reserved.