Catálogo de publicaciones - libros

In computational biology one often needs to look up the occurrence of some pattern P in a text T . Since the texts of computational biology include genome sequences, which tend to be large, it is important to apply efficient methods of string matching. Traditional string matching methods are guaranteed to take time O(n) , where n is the length of the text. By preprocessing a set of patterns into a keyword tree, this time requirement can be extended to set matching. Instead of preprocessing one or more patterns, it is also possible to preprocess the text. A suffix tree is a data structure that can be constructed for a given text in O(n) . However, once it is constructed, it can be used to search any P in T in time O(m) , where is the length of the pattern. In addition to making string searching extremely efficient, a suffix tree reveals in one fell-swoop the entire repeat structure of T without the need for carrying out any string comparisons. This has important biological applications where unique and repeat sequences play a central role in many fundamental as well as biotechnological problems. Finally, suffix trees can also be used for rapid inexact string matching, where ≤ k mismatches between P and its occurrence in T are allowed.

Multiple sequence alignments are often computed for known members of a protein family. The aim is to discover sequence motifs that are conserved across the mem bers of the protein family in order to infer the functionally important protein domains. Like pairwise sequence alignments, multiple sequence alignments can be computed using optimal or heuristic methods. In practice most multiple sequence alignments are computed using heuristic methods. These proceed by reducing the multiple alignment problem to a series of pairwise alignments. The order in which these pairwise alignments are fused into the multiple alignment is crucial for the success of the algorithm. The pairwise alignments of the input sequences are used to calculate pairwise distances. This in turn serves as input data for the construction of a guide tree, which determines the order in which sequences are added to the multiple alignment.

Profiles are position-specific score matrices derived from multiple sequence alignments. They are typically used for protein classification, where an unknown amino acid sequence is compared to a set of profiles characterizing known protein families. Such comparisons between profiles and anonymous sequences are often more sensitive than pairwise comparisons. Profiles can be rewritten as profile hidden Markov models. Hidden Markov models are based on Markov chains. These consist of a number of states and the probabilities of switching between them. The first order Markov chains considered in this chapter have the property that the chain’s state at some point in time depends only on its direct predecessor state. In hidden Markov models (HMMs), the states of the Markov chain are said to be hidden and to emit observation states, for example a DNA sequence. Given such data and a HMM, there are three classical problems that need to be solved for HMMs to be useful in biological sequence analysis: the scoring, the detection, and the training problem. Efficient solution of these problems leads to many applications of HMMs in biology, including homology detection, for which profiles were originally designed, but also extremely rapid multiple sequence alignment.