Algorithmic Aspects of Bioinformatics (eBook)

Preface 6
Contents 8
1 Introduction 12
Part I Introduction and Basic Algorithms 17
2 Basics of Molecular Biology 18
2.1 Proteins 18
2.2 Nucleic Acids 20
2.3 Hereditary Information and Protein Biosynthesis 23
2.4 Experimental Techniques 26
2.5 Bibliographic Notes 31
3 Basic Concepts: Strings, Graphs, and Algorithms 34
3.1 Strings 34
3.2 Graphs 36
3.3 Algorithms and Complexit y 39
3.4 Bibliographic Notes 46
4 String Algorithms 48
4.1 The String Matc hing Problem 48
4.2 String Matc hing Automata 50
4.3 The Boyer-Moore Algorithm 55
4.4 Suffix Trees 61
4.5 Further Applications of Suffix Trees 69
4.6 Suffix Arrays 79
4.7 Summary 88
4.8 Bibliographic Notes 89
5 Alignment Methods 92
5.1 Alignment of Two Strings 93
5.2 Heuristic Metho ds for Database Search 108
5.3 Multiple Alignments 112
5.4 Summary 125
5.5 Bibliographic Notes 125
Part II DNA Sequencing 128
6 Introduction and Overview 130
7 Physical Mapping 134
7.1 Restriction Site Mapping 134
7.2 Fingerprin ting and Mapping b y Hybridization 154
7.3 Summary 177
7.4 Bibliographic Notes 179
8 DNA Sequencing 182
8.1 Shotgun Sequencing 182
8.2 Sequencing by Hybridization 212
8.3 Summary 218
8.4 Bibliographic Notes 219
Part III Analyzing Biological Data 222
9 Finding Signals in DNA Sequences 224
9.1 Iden tical and Similar Substrings 224
9.2 T andem Rep eats 228
9.3 F requen t and Infrequen t Substrings 234
9.4 Hidden Mark o v Mo dels 239
9.5 Summary 246
9.6 Bibliographic Notes 246
10 Genome Rearrangements 248
10.1 Modeling 248
10.2 Sorting Undirected Permutations 250
10.3 Sorting Directed Permutations 258
10.4 Computing the Syntenic Distance 260
10.5 Summary 266
10.6 Bibliographic Notes 266
11 Phylogenetic Trees 268
11.1 Ultrametric Distances 269
11.2 Additive Trees 276
11.3 Characters with Binary States 279
11.4 The Parsimon y Principle and the Quartet Method 286
11.5 Summary 294
11.6 Bibliographic Notes 296
12 Haplotyping 298
12.1 Inferring Haplotypes from a Population 299
12.2 Haplotyping a Single Individual 316
12.3 Summary 327
12.4 Bibliographic Notes 327
13 Higher-Dimensional Structures of Biomolecules 330
13.1 RNA Secondary Structure Prediction 331
13.2 Structure-Based Comparison of Biomolecules 348
13.3 Protein Structure Prediction 360
13.4 Summary 380
13.5 Bibliographic Notes 383
References 388
Index 400

2 Basics of Molecular Biology (p. 7-8)

If one wants to consider questions in the area of molecular biology, as we do in this book, it is an obligatory prerequisite for the development and the evaluation of abstract models and techniques to have at least a basic knowledge about the fundamental principles of molecular biology. We therefore devote this chapter to fundamentals concerning the topics of subsequent chapters, and especially to the classes of biologically most relevant molecules, namely proteins and nucleic acids. The description will be an abstraction and recapitulation of biological knowledge only, and does not claim to be comprehensive or fully detailed. It instead provides an overview of the basic relations in molecular biology serving as a solid background for the problems we are going to consider later in this book. We will thus omit all details that are not necessary for understanding the text.

We start this chapter by the description of proteins in Section 2.1 and nucleic acids in Section 2.2, and their interaction for protein biosynthesis in Section 2.3. Afterwards, we will present some standard techniques used for the analysis of nucleic acids in Section 2.4, and we complete the chapter with some bibliographic notes in Section 2.5.

2.1 Proteins

Proteins represent one of the most important of the molecule classes in living organisms. Their functions include the catalysis of metabolic processes in the form of enzymes, they play an important role in signal transmission, defense mechanisms, and molecule transportation, and they are used as building material, for example in hair.

Proteins are chains of smaller molecular entities, so-called amino acids, which consist of a central carbon atom, denoted as C , connected to an amino group (NH2), a carboxyl group (COOH), and a side chain (R), which is specific for the particular amino acid. The fourth free binding site of C is saturated by a single hydrogen (H) atom. In Figure 2.1, this general structure is shown. According to this, the particular amino acids only di er with respect to their side chains, which also determine their chemical characteristics. We will, however, not consider the detailed chemical structure of the side chains any further.

In nature, there are several known amino acids, but only twenty of them serve as standard building blocks of proteins, these are given in Table 2.1. Next to the names of the amino acid, the corresponding abbreviation and the so-called one letter code is shown. Furthermore, we refer to the polarity of the amino acids, i.e., to their affinity to water, which will play an important role in Section 13.3.