Sequence Comparison (eBook)

Theory and Methods

Kun-Mao Chao, Louxin Zhang (Autoren)

eBook Download: PDF

2008 | 2009
XX, 209 Seiten
Springer London (Verlag)
978-1-84800-320-0 (ISBN)

Infos

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.

Inhalt

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

Produkt-Details

• Erscheint lt. Verlag: 27.11.2008
• Reihe/Serie: Computational Biology
• Zusatzinfo: XX, 209 p.
• Verlagsort: London
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik ► Programmiersprachen / -werkzeuge
• Themenwelt: Mathematik / Informatik ► Mathematik
• Themenwelt: Naturwissenschaften ► Biologie
• Themenwelt: Technik ► Elektrotechnik / Energietechnik
• Schlagworte: Algorithm analysis and problem complexity • algorithms • Alignment statistics • Bioinformatics • Computational Molecular Biology • Databases • Genome • Homology search • Molecular Biology • Scoring matrix • sequence alignment
• ISBN-10: 1-84800-320-X / 184800320X
• ISBN-13: 978-1-84800-320-0 / 9781848003200