Fundamentals of Bioinformatics - Ogurtsov A.N. 2013

Methods of Bioinformatic Analysis
Multiple Sequence Alignment
Hidden Markov Models

A Hidden Markov model (HMM) is a statistical model that simulates The behavior of a process resembling a Markov process with unknown parameters, where the task is to decipher (reconstruct) these unknown parameters based on observable data. The resulting parameters can be used in further analysis, such as pattern recognition. The first notes on hidden Markov models were published by Baum in the 1960s, and they were first applied to speech recognition as early as the 1970s. Since the mid-1980s, HMMs have been used in the analysis of Biological Sequences, particularly DNA.

A Markov process is a random process whose evolution after any given time parameter value $t$ does not depend on the evolution preceding $t$, provided that the value of the process at that moment is fixed ("future" of the process does not depend on the "past" given the "present"; or, in other words: the "future" of the process depends on the "past" only through the "present").

The property defining a Markov process is conventionally called the Markov property; it was first formulated by Andrey Andreyevich Markov (1856–1922), an outstanding Russian mathematician who made a major contribution to probability theory, mathematical analysis, and number theory. In his works of 1907, A. A. Markov initiated The Study of sequences of dependent trials and associated sums of random variables. This research direction is known as The Theory of Markov chains. Besides bioinformatics, hidden Markov models are used in cryptanalysis and machine Translation.

In bioinformatics, hidden Markov models serve to describe subtle differences existing between families of homologous sequences. The Hidden Markov Model (HMM) method is efficient both in comparing distant relatives and in predicting protein Folding Pathways. Only this method, relying entirely on sequence analysis (i.e., without using structural information), can rival the PSI-BLAST program in identifying distant homologs.

Although the hidden Markov model method works with Structure/59.html">Multiple Sequence Alignments, it is also frequently used for sequence generation.

Generally speaking, a standard multiple sequence alignment table can also be used to generate these sequences by sampling Amino Acids at successive positions. Each amino acid is chosen from a position-specific probability distribution derived from the profile.

HMM models are more general Methods than profiles because they include the probability of deletions or insertions occurring in the generated sequence with position-dependent penalties.

While profile application requires the prior Construction of a multiple sequence alignment—with query statistics determined after the alignment is built—an HMM simultaneously performs both the alignment and the probability estimation.

Figure 62 schematically illustrates the sequence generation mechanism. The figure shows three positions and a set of states (m), (i), (d).

Class="center">

Figure 62 - Structure of a Hidden Markov Model

Starting from "Start", the HMM moves along the arrows until reaching "Stop". Each arrow leads to a specific system state. In each of these states, (1) a specific action is undertaken (e.g., an amino acid is specified), and then (2) an arrow is chosen that transitions the system to the next state. Both the action and the choice of the next state are governed by specific sets of probabilities.

At each position where an amino acid residue is introduced, one set of probabilities governs The process of choosing one of the 20 standard amino acids, while a second set of probabilities governs the transition path to the next stage of the process. Both sets of probabilities are tuned to provide an adequate description of a specific sequence family. Using this approach and varying only the position-specific probability tables, the same algorithm can be applied to different sequence families. In Figure 62, each of the three positions in the multiple alignment corresponds to a match (m) and a deletion (d) in the HMM. Insertions (i) can occur either between residue positions or at the very beginning and end of the alignment.

If a given position corresponds to a match (m), the corresponding amino acid residue is inserted into the alignment.

In this context, the word "match" simply means that Certain amino acids are present in both the HMM sequence and the final sequence, rather than implying that they must necessarily be identical amino acids.

The probability of selecting one of the 20 amino acids at a given match position is determined by the parameters of the model being used, that is, the position-specific probabilities of amino acid insertion at that position.

In the case of a deletion (d), the corresponding Column of the multiple alignment is skipped. The Introduction of the first deletion represents a gap-open, and the probability of this introduction determines the gap-opening penalty, which is also position-specific. Introducing a second deletion immediately following the first represents a gap-extension, for which a penalty may also be assigned (see section 7.2).

Insertions (i) are placed between two consecutive positions in the alignment. If the program introduces an insertion, a residue is inserted into the generated sequence that does not match (at the given position) the residues in the sequences used for the multiple alignment. The first insertion may be followed by a second, and so on, forming an insertion of more than one residue in length.

The sequence of residues, resulting matches, and insertions constitutes the desired (generated) sequence.

After performing the corresponding action (m, d, or i), the transition to the next graph node is determined by a new set of probabilities.

In every possible position sequence, each column of the constructed alignment must be either a match or a deletion—there is no way to traverse the graph without passing through either an (m)-node or a (d)-node, and this holds for every position in the sequence.

The dynamics of the described system are such that only the current position determines which of the available arrows will be chosen for the next transition; in other words, the system has no "memory" of its history. This is precisely the characteristic feature of Markov processes.

Note that a distinction should be made between the sequence of positions (or stages) in the program's operation and the sequence of amino acids generated As a result of the algorithm's execution.

It may turn out that different paths through the system can produce identical sequences.

Ultimately, we obtain the output of the algorithm, while all the "details" of navigating the graph within the system and selecting a specific "route" between "Start" and "Stop" remain hidden. Hence the name—Hidden Markov Model (HMM).

The Specificity of the algorithm's operation for a given set of sequences is determined precisely by the sets of probabilities (residue choice and transition choice) that are assigned individually for each position.

Programs implementing HMMs for biological sequence analysis can perform the following tasks.

1. Training. Given a set of unaligned homologous sequences, one can (1) align them and (2) adjust transition and residue emission probabilities to define an HMM that accurately describes the target set of sequences.

2. Searching for distant homologs. Given an HMM and a sequence of interest, one can calculate the probability that the HMM could have generated that sequence. If an HMM built for a known protein family can do this with a sufficiently high probability, it strongly suggests that the query sequence also belongs to that family.

3. Aligning additional sequences. The probability of traversing any path within a given HMM—that is, the probability of obtaining a specific set of states—can be calculated from the individual state-by-state transition probabilities. Finding the most probable sequence of states that the HMM would use to generate one or more test sequences reveals their optimal alignment with the given sequence family.

METABOLISM/35.html">Selection/41.html">Review Questions and exercises

1. What is meant by multiple sequence alignment?

2. What type of multiple alignment annotation does the ClustalW program use?

3. What is an alignment profile?

4. What is the advantage of the PSI-BLAST program over alignment profiles?

5. What process is referred to as Markovian?

6. What is the main advantage of the hidden Markov model method?

7. What two choices, utilizing position-specific probability tables, are made at each state of the system within the framework of a hidden Markov model?

8. What Three types of tasks can be solved by programs implementing hidden Markov models?