Chao / Zhang Sequence Comparison

Theory and Methods
1. Auflage 2008
ISBN: 978-1-84800-320-0
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, Band 7, 209 Seiten

Reihe: Computational Biology

Biomolecular sequence comparison is the origin of bioinformatics. This book gives a complete in-depth treatment of the study of sequence comparison. A comprehensive introduction is followed by a focus on alignment algorithms and techniques, proceeded by a discussion of the theory. The book examines alignment methods and techniques, features a new issue of sequence comparison - the spaced seed technique, addresses several new flexible strategies for coping with various scoring schemes, and covers the theory on the significance of high-scoring segment pairs between two unalignment sequences. Useful appendices on basic concepts in molecular biology, primer in statistics and software for sequence alignment are included in this reader-friendly text, as well as chapter-ending exercise and research questions A state-of-the-art study of sequence alignment and homology search, this is an ideal reference for advanced students studying bioinformatics and will appeal to biologists who wish to know how to use homology search tools.

Autoren/Hrsg.

Chao, Kun-Mao

Zhang, Louxin

Inhaltsverzeichnis

1;Foreword;7
2;Preface;9
3;Acknowledgments;12
4;About the Authors;13
5;Contents;14
6;Introduction;18
6.1;1.1 Biological Motivations;18
6.2;1.2 Alignment: A Model for Sequence Comparison ;19
6.3;1.3 Scoring Alignment;24
6.4;1.4 Computing Sequence Alignment;25
6.5;1.5 Multiple Alignment;28
6.6;1.6 What Alignments Are Meaningful?;29
6.7;1.7 Overview of the Book;29
6.8;1.8 Bibliographic Notes and Further Reading;30
7;PART I. ALGORITHMS AND TECHNIQUES;32
7.1;Basic Algorithmic Techniques;33
7.1.1;2.1 Algorithms and Their Complexity;34
7.1.2;2.2 Greedy Algorithms;34
7.1.3;2.3 Divide-and-Conquer Strategies;37
7.1.4;2.4 Dynamic Programming;39
7.1.5;2.5 Bibliographic Notes and Further Reading;48
7.2;Pairwise Sequence Alignment;50
7.2.1;3.1 Introduction;51
7.2.2;3.2 Dot Matrix;52
7.2.3;3.3 Global Alignment;52
7.2.4;3.4 Local Alignment;57
7.2.5;3.5 Various Scoring Schemes;61
7.2.6;3.6 Space-Saving Strategies;64
7.2.7;3.7 Other Advanced Topics;69
7.2.8;3.8 Bibliographic Notes and Further Reading;75
7.3;Homology Search Tools;78
7.3.1;4.1 Finding Exact Word Matches;79
7.3.2;4.2 FASTA;83
7.3.3;4.3 BLAST;84
7.3.4;4.4 BLAT;89
7.3.5;4.5 PatternHunter;90
7.3.6;4.6 Bibliographic Notes and Further Reading;93
7.4;Multiple Sequence Alignment;95
7.4.1;5.1 Aligning Multiple Sequences;95
7.4.2;5.2 Scoring Multiple Sequence Alignment;96
7.4.3;5.3 An Exact Method for Aligning Three Sequences;98
7.4.4;5.4 Progressive Alignment;99
7.4.5;5.5 Bibliographic Notes and Further Reading;100
8;PART II. THEORY;103
8.1;Anatomy of Spaced Seeds;104
8.1.1;6.1 Filtration Technique in Homology Search;105
8.1.2;6.2 Basic Formulas on Hit Probability;106
8.1.3;6.3 Distance between Non-Overlapping Hits;112
8.1.4;6.4 Asymptotic Analysis of Hit Probability;117
8.1.5;6.5 Spaced Seed Selection ;123
8.1.6;6.6 Generalizations of Spaced Seeds;125
8.1.7;6.7 Bibliographic Notes and Further Reading;128
8.2;Local Alignment Statistics;131
8.2.1;7.1 Introduction;132
8.2.2;7.2 Ungapped Local Alignment Scores;134
8.2.3;7.3 Gapped Local Alignment Scores;146
8.2.4;7.4 BLAST Database Search;151
8.2.5;7.5 Bibliographic Notes and Further Reading;158
8.3;Scoring Matrices;160
8.3.1;8.1 The PAM Scoring Matrices;161
8.3.2;8.2 The BLOSUM Scoring Matrices;164
8.3.3;8.3 General Form of the Scoring Matrices;166
8.3.4;8.4 How to Select a Scoring Matrix?;168
8.3.5;8.5 Compositional Adjustment of Scoring Matrices;169
8.3.6;8.6 DNA Scoring Matrices;172
8.3.7;8.7 Gap Cost in Gapped Alignments;174
8.3.8;8.8 Bibliographic Notes and Further Reading;175
8.4;Basic Concepts in Molecular Biology;184
8.4.1;A.1 The Nucleic Acids: DNA and RNA;184
8.4.2;A.2 Proteins;185
8.4.3;A.3 Genes;186
8.4.4;A.4 The Genomes;186
8.5;Elementary Probability Theory;188
8.5.1;B.1 Events and Probabilities;188
8.5.2;B.2 Random Variables;189
8.5.3;B.3 Major Discrete Distributions;190
8.5.4;B.4 Major Continuous Distributions;193
8.5.5;B.5 Mean, Variance, and Moments ;194
8.5.6;B.6 Relative Entropy of Probability Distributions;198
8.5.7;B.7 Discrete-time Finite Markov Chains ;199
8.5.8;B.8 Recurrent Events and the Renewal Theorem;202
8.6;Software Packages for Sequence Alignment;205
9;References;207
10;Index;216