Computational Biology Lecture 11: Pairwise alignment using HMMs

We looked at various alignment algorithms with different scoring schemes. We argued that the score of an alignment is related to the relative likelihood that the two sequences are related compared to being unreleated, and we used the log-odds ratio to express this relative likelihood while maintaining an additive scoring scheme. Therefore, maximizing the score of an alignment was in some sense equivalent to maximizing the log-odds ratio, with the exception that gaps are scored separately and are not related to the log-odds ratio. Recall that we have considered only ungapped alignments in deriving the scores that relate to the log-odds ratio, and assumed a separate model for scoring gaps; for instance, an affine gap penalty function. Now we will unify both models into a single probabilistic model and see how the score of a gapped alignment of the Needleman-Wunsch algorithm can be viewed as a maximum log-odds ratio obtained by a Viterbi algorithm for an HMM that generates two sequences simultaneously. Needleman-Wunsch as a Finite State Machine Recall the Needleman-Wunsch algorithm with an affine gap penalty function. A(i, j) = s(i, j) + max A(i − 1, j − 1)B(i − 1, j − 1) C(i − 1, j − 1) B(i, j) = max A(i − 1, j) − e B(i − 1, j) − d C(i, j) = max A(i, j − 1) −