Table of contents for Algorithmic aspects of bioinformatics / Hans-Joachim Bo╠łckenhauer, Dirk Bongartz.


Bibliographic record and links to related information available from the Library of Congress catalog
Note: Electronic data is machine generated. May be incomplete or contain other coding.


Counter
Part I Introduction and Basic Algorithms
2   Basics of M olecular Biology ..........  ..............        7
2    Proteins  .,.  ..........    ..   ....  ... ....          7
2._  Nucleic  Acids  ...... ..  .. ......                      9
2.3  Hereditary information and Protein Biosynthesis .... .... .12
2.4  Experimental Techniques ......................  .......  15
2.4.1 Basic Terms and Methods ........    ..... .   ...  15
2.4.2 Duplication of DNA ..     .........                15
2.4.3  Gel Electrophoresis and Direct Sequencing ... .......  16
2.4   DNA  Chip  ...    ...... ..........     ........   19
2.5  Bibliographic  Notes ....   . .. .....  .......  .. . .. .  20
3   Basic Concepts: Strings, Graphs, and Algorithms. .. . ...     23
3.1  St ings .. ......................                        23
3.2  G rap hs .. .. ... .... .. ....... . ...........  .... ... .  25
3.3  Algorithms and  Complexity .. . . . . . . .  ...........  28
3.4  Bib  iographic  Notes.. . .......   ... .  . .. ...... ...  35
4   String Algorithms ..... 37
4-.1  The String  Matching Problem  ..   .......   . ............  37
4.2  String Matching Automata  . .  .... ......   ... .. ... .  39
43   The Boyer-Moore Algorithm. 4.....  .......     ........ 44
.4   Suffix  Třees.     .  ..                 .... ......     50
4.5 Further Applications of Suffix Trees .. . . . . . . . . . .  .  58
4.5,1 Generalized Suffix Trees and the Substring Problem .. . 58
4.5.2  Longest Con non  Substrings  .  . . . .  . ... .. . . . . .   61
4.5.3 Effcient Compuitation of Overlaps . . , . . . . . ..  63
4.5.4  Repeats in  Strings .. ...  . .. . ... . .  . .... ..   ...  66
4.6  Suffix  A rrays  . .... ..... .. . . ............... . .... ...  68
4.7 Summary.....
48   Bibliographic Notes......  ...........          .  ...   78
5   Alignm ent  M ethods  .  ...... ............................  81
5.1  Alignment of  wo  trings        ............... ... ....  82
5.1.1  Basic  Definitions  ............ .. .. . ..... .. . ....  82
5.1,2  Global Alignment  ..................              84
5.1.3 Local and Semiglobal Alignment .. ...... .  ....  . . 89
5.1.4  Generalized Scoring Functions            ...   . 94
5.2 Hleuristic Methods for Database Sear.h .. ........ . . . . . ...  97
5.2.1 The ASTA Heuristic    ............    .......      98
5.2.2 The BLAST Heuristic ......99
5.3  M ultiple  Alignments  ....... ........... .... . ........ ..   101
5.3.1 Definition and Scoring of Multiple Alignments ........ 101
0,3.2 Exact Computation of Multiple Alignments . . ....... 104
"53.3  Conibining Pairwise Alignments ... .  .. .. . . . .. . 109
5.A  Sum m ary  .......   ...... ..  ... ........ .... ..    114
5.5  Bibliographic  Notes  .. .                 ..............................114
Part II DNA Sequencing
6   Introduction and Overview ....       ..... ......       ......119
7   Physical M apping   .. . .. ........... ..     ......... ... .. 123
7.1 Restriction Site Mapping .........                  ... 123
7.1.1  The Double Digest Approach  ............... ....  .124
7.1.2 The Partial Digest Approach ................... 131
7.1.3  Comparison of Methods for Restriction Site Mapping .. 141
7.2 Hybridization Mapping    ............................. 143
7.2.1 Mapping with Unique Probes .........46
7.2.2 Miapping with Unique Probes and Errors ...... ... 157
7.2.3 Mapping with Non-unique Probes .....    . .. .. 165
8   D N A  Sequencing  ....    ... ............  ...   .. .....  171
8.1  Shotgun  Sequencing     .... ... ...  .....  ............171
8.1.1  Crucial Points to Be Considered in a Suitable Model. . 174
"8.1.2 The Shortest Common Superstring Problem ......... 176
8.1.3 Refined Models for Fragmrent Asspembly ... 196
8.2 Sequencing by Hybridization ................. 201
8.3   unm ar  y. .           .   . .  .  . .. .. .  .. . . .... . .. 207
's   ..      . . . .. . . . . . . . . . . . .^             Ci
8.4 :ibiiographic Notes .. .........    ......  . .     . .. .208
Part III Analyzing Biological Data
9   Finding Signals in DNA Sequences .... 213
9.  ld.M,en  d anad SmiBar Substrings .....              . 213
9.2  Tandem  Repeats                .. ...... ....... ..... . .. ..  217
9.3 Frequent and Infrequent Substrings ....  ..... 223
SHicidden Ma, rkov Models .... . . .. . . . .       . . . . .. . 228
"9. 5  St iar  y......                   ...... ...         235
9.6  Bibliographic Notes .. .   . .   . .. 235
10 Geno me Rearrangements . .          . . . . . ............... .237
10.  M odeing..     ...... .  ..           ........      ..  237
10.2  Sarting Undirected  Permutations ... . .....  .  . . . . . . . .  . . . .  .  239
10.3  Sorting Directee  Permur tations  .   .  ... . . .  . .......... .  .  247
10.4 Computling the Synenic Distnce  . . . .  .   . . .  . . D  . 249
10.,5  Summary  ....... .. . .  ......                ....255
10.6  Bibliographic  Notes  .. .....  ....... .  ..............  255
11  Phylogenetic  Trees  .......................257
11.1  11lt rametric  Distances .. . ....    .  .. .......  . 258
Si.2  Add:ive  Trees  ... .......  .. ... .          . .  .  . . 265
11.3 Charcters with Inar Sta es .. . . . . .......... 268
11.4, The Parsimony Principle and the Quartet Method ... ...... 275
11.5  Su mim ary  . .. .... ....      ........ . ...  ......  283
11.  Bibliographic Notes                 .  . . . . .  .  .  . . . . . . . . 285
12  H aplotyping  .  .... ..             .......   ....  ... .... 287
12.1 Inferring Haplotypes from a Population .  ..  . . . . . . . .. 288
12.2  I [plotvping a Single lndividual.  . ...       . . . . 305
12.3  Sumirnary  . .....         . ...    .....              316
12.4  Bibliographic Notes .   ......... 316
13 Molecular Structures .......        .......... ...319
13.1  ,N A  Secondar  Structure Prediction  .. . ... ........  ... .  320
1.3.1.1 Minmizing the Free Energy . . .. .......322
1.3.12 Stochastic Co ntet-sr,e Tramnmars ....... . . . .... 3129
1.12 St rue nre-Based Conmparison o" Biomoeules. ...  ..    337
13.3 IProtem S tricture Prediction .. ............       ..... 349
1..3.1 DIe Nov Srnicture Prediction -- The HP Model ... .52
i3,2  Protein  Threading  . . . . . . .  .   . .  .  .  .  .  .   .  63
1 .41  Sui mrrngy  ........                         ... .  . .36
1 .4 R1NA Secondary Structure Predict ion .... . . . . . . . . . ..30
13.4.2 Structure-Based Comparison of Biomolecules        371
13.4.3 Protein Structure Prediction .  .....        ..   371
13.5  Bibliographic Notes ......  .. .... ..          ..  .  . .372
13.5.1 RNA Secondary Structure Prediction . ...     ... 372
13.5.2 Structure-Based Comparison of Biomolecules  .  ... 373
13.5 3 Protein Structure Prediction  . ..........        374



Library of Congress subject headings for this publication: Bioinformatics Mathematics, Algorithms