Theory and mathematical methods for bioinformatics

Bioinformatics is an interdisciplinary science which involves molecular bi- ogy, molecular chemistry, physics, mathematics, computational sciences, etc. Mostofthebooksonbiomathematicspublishedwithinthepasttenyearshave consistedofcollectionsofstandardbioinformaticsproblemsandinformational methods,andfocus mainly onthe logisticsofimplementing andmakinguse of various websites, databases, software packages and serving platforms. While these types of books do introduce some mathematical and computational methods alongside the software packages, they are lacking in a systematic and professional treatment of the mathematics behind these methods. It is signi?cant in the ?eld of bioinformatics that not only is the amount of data increasing exponentially, but collaboration is also both widening and deepening among biologists, chemists, physicists, mathematicians, and c- puter scientists. The sheer volume of problems and databases requires - searchers to continually develop software packages in order to process the huge amounts of data, utilizing the latest mathematical methods. The - tent of this book is to provide a professional and in-depth treatment of the mathematical topics necessary in the study of bioinformatics.

Author Notes

Shiyi Shen

Since 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 Tuszynski

Professor (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ÃYen, 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.

Outline	p. 1
Part I Mutations and Alignments
1 Introduction	p. 5
1.1 Mutation and Alignment	p. 5
1.1.1 Classification of Biological Sequences	p. 5
1.1.2 Definition of Mutations and Alignments	p. 6
1.1.3 Progress on Alignment Algorithms and Problems to Be Solved	p. 8
1.1.4 Mathematical Problems Driven by Alignment and Structural Analysis	p. 12
1.2 Basic Concepts in Alignment and Mathematical Models	p. 13
1.2.1 Mutation and Alignment	p. 13
1.3 Dynamic Programming-Based Algorithms for Pairwise Alignment	p. 17
1.3.1 Introduction to Dynamic Programming-Based Algorithms	p. 17
1.3.2 The Needleman-Wunsch Algorithm, the Global Alignment Algorithm	p. 18
1.3.3 The Smith-Waterman Algorithm	p. 21
1.4 Other Notations	p. 24
1.4.1 Correlation Functions of Local Sequences	p. 24
1.4.2 Pairwise Alignment Matrices Among Multiple Sequences	p. 25
1.5 Remarks	p. 26
1.6 Exercises, Analyses, and Computation	p. 27
2 Stochastic Models of Mutations and Structural Analysis	p. 29
2.1 Stochastic Sequences and Independent Sequence Pairs	p. 29
2.1.1 Definitions and Notations of Stochastic Sequences	p. 29
2.1.2 Independently and Identically Distributed Sequences	p. 31
2.1.3 Independent Stochastic Sequence Pairs	p. 33
2.1.4 Local Penalty Function and Limit Properties of 2-Dimensional Stochastic Sequences	p. 36
2.2 Stochastic Models of Flow Raised by Sequence Mutations	p. 37
2.2.1 Bernoulli Processes	p. 37
2.2.2 Poisson Flow	p. 40
2.2.3 Mutated Flows Resulting from the Four Mutation Types	p. 43
2.3 Stochastic Models of Type-I Mutated Sequences	p. 45
2.3.1 Description of Type-I Mutation	p. 45
2.3.2 Properties of Type-I Mutations	p. 47
2.4 Type-II Mutated Sequences	p. 50
2.4.1 Description of Type-II Mutated Sequences	p. 51
2.4.2 Stochastic Models of Type-II Mutated Sequences	p. 51
2.4.3 Error Analysis of Type-II Mutated Sequences	p. 54
2.4.4 The Mixed Stochastic Models Caused by Type-I and Type-II Mutations	p. 57
2.5 Mutated Sequences Resulting from Type-III and Type-IV Mutations	p. 58
2.5.1 Stochastic Models of Type-III and Type-IV Mutated Sequences	p. 58
2.5.2 Estimation of the Errors Caused by Type-III and Type-IV Mutations	p. 59
2.5.3 Stochastic Models of Mixed Mutations	p. 61
2.6 Exercises	p. 64
3 Modulus Structure Theory	p. 67
3.1 Modulus Structure of Expanded and Compressed Sequences	p. 67
3.1.1 The Modulus Structures of Expanded Sequences and Compressed Sequences	p. 67
3.1.2 The Order Relation and the Binary Operators on the Set of Expanded Modes	p. 71
3.1.3 Operators Induced by Modes	p. 73
3.2 Modulus Structure of Sequence Alignment	p. 76
3.2.1 Modulus Structures Resulting from Multiple Alignment	p. 76
3.2.2 Structure Analysis of Pairwise Alignment	p. 78
3.2.3 Properties of Pairwise Alignment	p. 81
3.2.4 The Order Relation and the Operator Induced by Modulus Structure	p. 84
3.3 Analysis of Modulus Structures Resulting from Sequence Mutations	p. 85
3.3.1 Mixed Sequence Mutations	p. 85
3.3.2 Structure Analysis of Purely Shifting Mutations	p. 87
3.3.3 Structural Representation of Mixed Mutation	p. 93
3.4 The Binary Operations of Sequence Mutations	p. 93
3.4.1 The Order Relationship Among the Modes of Shifting Mutations	p. 93
3.4.2 Operators Induced by Modes of Shifting Mutations	p. 96
3.5 Error Analysis for Pairwise Alignment	p. 100
3.5.1 Uniform Alignment of Mutation Sequences	p. 100
3.5.2 Optimal Alignment and Uniform Alignment	p. 102
3.5.3 Error Analysis of Uniform Alignment	p. 104
3.5.4 Local Modification of Sequence Alignment	p. 106
3.6 Exercises	p. 107
4 Super Pairwise Alignment	p. 109
4.1 Principle of Statistical Decision-Based Algorithms for Pairwise Sequences	p. 109
4.1.1 Uniform Alignment and Parameter Estimation for Pairwise Sequences	p. 109
4.1.2 The Locally Uniform Alignment Resulting from Local Mutation	p. 111
4.1.3 The Estimations of Mutation Position and Length	p. 113
4.2 Operation Steps of the SPA and Its Improvement	p. 115
4.2.1 Operation Steps of the SPA	p. 115
4.2.2 Some Unsolved Problems and Discussions of SPA	p. 118
4.2.3 Local Modifications for Sequence Alignment	p. 121
4.3 Index Analysis of SPA	p. 122
4.3.1 The Statistical Features of Estimations	p. 122
4.3.2 Improvement of the Algorithm to Estimate {{\hat s}}^\ast	p. 128
4.3.3 The Computational Complexity of the SPA	p. 131
4.3.4 Estimation for the Error of Uniform Alignment Induced by a Hybrid Stochastic Mutation Sequence	p. 132
4.4 Applications of Sequence Alignment and Examples	p. 135
4.4.1 Several Applications of Sequence Alignment	p. 135
4.4.2 Examples of Pairwise Alignment	p. 137
4.5 Exercises	p. 146
5 Multiple Sequence Alignment	p. 149
5.1 Pairwise Alignment Among Multiple Sequences	p. 149
5.1.1 Using Pairwise Alignment to Process Multiple Sequences	p. 149
5.1.2 Topological Space Induced by Pairwise Alignment of Multiple Sequences	p. 150
5.2 Optimization Criteria of MA	p. 156
5.2.1 The Definition of MA	p. 156
5.2.2 Uniform Alignment Criteria and SP-Optimization Criteria for Multiple Sequences	p. 156
5.2.3 Discussion of the Optimization Criterion of MA	p. 160
5.2.4 Optimization Problem Based on Shannon Entropy	p. 164
5.2.5 The Similarity Rate and the Rate of Virtual Symbols	p. 170
5.3 Super Multiple Alignment	p. 172
5.3.1 The Situation for MA	p. 172
5.3.2 Algorithm of SMA	p. 174
5.3.3 Comparison Among Several Algorithms	p. 179
5.4 Exercises, Analyses, and Computation	p. 180
6 Network Structures of Multiple Sequences Induced by Mutation	p. 183
6.1 General Method of Constructing the Phylogenetic Tree	p. 183
6.1.1 Summary	p. 183
6.1.2 Distance-Based Methods	p. 184
6.1.3 Feature-Based (Maximum Parsimony) Methods	p. 188
6.1.4 Maximum-Likelihood Method and the Bayes Method	p. 191
6.2 Network Structure Generated by MA	p. 197
6.2.1 Graph and Tree Generated by MA	p. 197
6.2.2 Network System Generated by Mutations of Multiple Sequences	p. 200
6.3 The Application of Mutation Network Analysis	p. 206
6.3.1 Selection of the Data Sample	p. 206
6.3.2 The Basic Steps to Analyze the Sequences	p. 208
6.3.3 Remarks on the Alignment and Output Analysis	p. 210
6.4 Exercises, Analyses, and Computation	p. 216
7 Alignment Space	p. 219
7.1 Construction of Alignment Space and Its Basic Theorems	p. 219
7.1.1 What Is Alignment Space?	p. 219
7.1.2 The Alignment Space Under General Metric	p. 221
7.2 The Analysis of Data Structures in Alignment Spaces	p. 224
7.2.1 Maximum Score Alignment and Minimum Penalty Alignment	p. 224
7.2.2 The Structure Mode of the Envelope of Pairwise Sequences	p. 226
7.2.3 Uniqueness of the Maximum Core and Minimum Envelope of Pairwise Sequences	p. 230
7.2.4 The Envelope and Core of Pairwise Sequences	p. 231
7.2.5 The Envelope of Pairwise Sequences and Its Alignment Sequences	p. 233
7.3 The Counting Theorem of the Optimal Alignment and Alignment Spheroid	p. 237
7.3.1 The Counting Theorem of the Optimal Alignment	p. 237
7.3.2 Alignment Spheroid	p. 238
7.4 The Virtual Symbol Operation in the Alignment Space	p. 241
7.4.1 The Definition of the Virtual Symbol Operator	p. 241
7.4.2 The Modulus Structure of the Virtual Symbol Operator	p. 243
7.4.3 The Isometric Operation and Micro-Adapted Operation of Virtual Symbols	p. 247
7.5 Exercises, Analyses, and Computation	p. 250
Part II Protein Configuration Analysis
8 Background Information Concerning the Properties of Proteins	p. 255
8.1 Amino Acids and Peptide Chains	p. 255
8.1.1 Amino Acids	p. 255
8.1.2 Basic Structure of Peptide Chains	p. 257
8.2 Brief Introduction of Protein Configuration Analysis	p. 259
8.2.1 Protein Structure Database	p. 259
8.2.2 Brief Introduction to Protein Structure Analysis	p. 260
8.3 Analysis and Exploration	p. 263
9 Informational and Statistical Iterative Analysis of Protein Secondary Structure Prediction	p. 265
9.1 Protein Secondary Structure Prediction and Informational and Statistical Iterative Analysis	p. 265
9.1.1 Protein Secondary Structure Prediction	p. 265
9.1.2 Data Source and Informational Statistical Model of PSSP	p. 267
9.1.3 Informational and Statistical Characteristic Analysis on Protein Secondary Structure	p. 269
9.2 Informational and Statistical Calculation Algorithms for PSSP	p. 271
9.2.1 Informational and Statistical Calculation for PSSP	p. 271
9.2.2 Informational and Statistical Calculation Algorithm for PSSP	p. 273
9.2.3 Discussion of the Results	p. 275
9.3 Exercises, Analyses, and Computation	p. 277
10 Three-Dimensional Structure Analysis of the Protein Backbone and Side Chains	p. 279
10.1 Space Conformation Theory of Four-Atom Points	p. 279
10.1.1 Conformation Parameter System of Four-Atom Space Points	p. 279
10.1.2 Phase Analysis on Four-Atom Space Points	p. 283
10.1.3 Four-Atom Construction of Protein 3D Structure	p. 286
10.2 Triangle Splicing Structure of Protein Backbones	p. 288
10.2.1 Triangle Splicing Belts of Protein Backbones	p. 288
10.2.2 Characteristic Analysis of the Protein Backbone Triangle Splicing Belts	p. 291
10.3 Structure Analysis of Protein Side Chains	p. 292
10.3.1 The Setting of Oxygen Atom O and Atom C B on the Backbones	p. 293
10.3.2 Statistical Analysis of the Structures of Tetrahedrons V O , V B	p. 295
10.4 Exercises, Analyses, and Computation	p. 297
11 Alignment of Primary and Three-Dimensional Structures of Proteins	p. 299
11.1 Structure Analysis for Protein Sequences	p. 299
11.1.1 Alignment of Protein Sequences	p. 299
11.1.2 Differences and Similarities Between the Alignment of Protein Sequences and of DNA Sequences	p. 301
11.1.3 The Penalty Functions for the Alignment of Protein Sequences	p. 302
11.1.4 Key Points of the Alignment Algorithms of Protein Sequences	p. 306
11.2 Alignment of Protein Three-Dimensional Structures	p. 307
11.2.1 Basic Idea and Method of the Alignment of Three-Dimensional Structures	p. 307
11.2.2 Example of Computation in the Discrete Case	p. 310
11.2.3 Example of Computation in Consecutive Case	p. 314
11.3 Exercises, Analyses, and Computation	p. 323
12 Depth Analysis of Protein Spatial Structure	p. 325
12.1 Depth Analysis of Amino Acids in Proteins	p. 325
12.1.1 Introduction to the Concept of Depth	p. 325
12.1.2 Definition and Calculation of Depth	p. 327
12.1.3 Proof of Theorem 40	p. 329
12.1.4 Proof of Theorem 41	p. 334
12.2 Statistical Depth Analysis of Protein Spatial Particles	p. 335
12.2.1 Calculation for Depth Tendency Factor of Amino Acid	p. 335
12.2.2 Analysis of Depth Tendency Factor of Amino Acid	p. 338
12.2.3 Prediction for Depth of Multiple Peptide Chains in Protein Spatial Structure	p. 342
12.2.4 The Level Function in Spatial Particle System	p. 347
12.2.5 An Example	p. 347
12.3 Exercises	p. 353
13 Analysis of the Morphological Features of Protein Spatial Structure	p. 355
13.1 Introduction	p. 355
13.1.1 Morphological Features of Protein Spatial Structure	p. 355
13.1.2 Several Basic Definitions and Symbols	p. 357
13.1.3 Preliminary Analysis of the Morphology of Spatial Particle System	p. 360
13.1.4 Example	p. 362
13.2 Structural Analysis of Cavities and Channels in a Particle System	p. 366
13.2.1 Definition, Classification and Calculation of Cavity	p. 366
13.2.2 Relationship Between Cavities	p. 368
13.2.3 Example	p. 371
13.3 Analysis of ¿-Accessible Radius in Spatial Particle System	p. 371
13.3.1 Structural Analysis of a Directed Polyhedron	p. 371
13.3.2 Definition and Basic Properties of ¿-Accessible Radius	p. 377
13.3.3 Basic Principles and Methods of ¿-Accessible Radius	p. 378
13.4 Recursive Algorithm of ¿-Function	p. 382
13.4.1 Calculation of the ¿-Function Generated by 0-Level Convex Hull	p. 382
13.4.2 Recursive Calculation of ¿-Function	p. 384
13.4.3 Example	p. 387
13.5 Proof of Relative Theorems and Reasoning of Computational Formulas	p. 387
13.5.1 Proofs of Several Theorems	p. 387
13.5.2 Reasoning of Several Formulas	p. 390
13.6 Exercises	p. 394
14 Semantic Analysis for Protein Primary Structure	p. 395
14.1 Semantic Analysis for Protein Primary Structure	p. 395
14.1.1 The Definition of Semantic Analysis for Protein Primary Structure	p. 395
14.1.2 Information-Based Stochastic Models in Semantic Analysis	p. 397
14.1.3 Determination of Local Words Using Informational and Statistical Means and the Relative Entropy Density Function for the Second and Third Ranked Words	p. 400
14.1.4 Semantic Analysis for Protein Primary Structure	p. 402
14.2 Permutation and Combination Methods for Semantic Structures	p. 412
14.2.1 Notation Used in Combinatorial Graph Theory	p. 416
14.2.2 The Complexity of Databases	p. 420
14.2.3 Key Words and Core Words in a Database	p. 421
14.2.4 Applications of Combinatorial Analysis	p. 425
14.3 Exercises, Analyses, and Computation	p. 429
Epilogue	p. 431
References	p. 433
Index	p. 441

Available:*

On Order

Summary

Summary

Author Notes

Table of Contents