CS 369: HMM applications
David Welch 2 May 2019
Pairwise alignment: Finite State Automata
2/15
Pairwise alignment: Pair HMM
3/15
Relationship with scores used in standard method
\[ \begin{align*} s(a,b) &= \log \frac{p_{ab}}{q_aq_b} + \log{1 – 2\delta – \tau}{(1- \eta)^2} \\ d &= -\log \frac{\delta(1-\epsilon – \tau)}{(1-\eta)(1 – 2\delta – \tau)} \\ e &= -\log \frac{\epsilon}{1-\eta}. \end{align*} \]
4/15
Probability that \(x_i\) and \(y_j\) are aligned
\[ \Pr(\langle x_i,y_j \rangle | x,y) = P(\pi(i,j) = M|x,y) = \frac{ P(\pi(i,j) = M,x,y)} {P(x,y)} = \frac{f_M(i,j)b_M(i,j)}{P(x,y)}. \]
5/15
Profile HMMs: Characterising protein families
6/15
Profile HMMs: model structure
In a Match state when less than half column is gaps
7/15
Profile HMMs: Insert and Delete states
8/15
Profile HMMs: Fitting parameters from MSA
9/15
Pseudo-counts: Fitting parameters from MSA
As discussed previously, add pseudo-counts to allow for unseen transitions or emissions.
Simplest is to add pseudo-count of 1 to all counts.
10/15
Profile HMMs: finding family members
11/15
Profile HMMs: finding family members
12/15
Profile HMMs: finding family members
13/15
Gene finding: structure of gene
14/15
Gene finding: structure of HMM
–>
15/15