Description
Construct a profile HMM from a multiple alignment.
Input: A multiple alignment Alignment and a threshold θ.
Output: HMM(Alignment, θ), in the form of transition and emission matrices.
Input Format.
The 1st line of the input contains the threshold θ.
The 2nd line of the input is “--------” (a delimiter).
The 3rd line of the input is the list of symbols in the alphabet Σ (space-separated).
The 4th line of the input is “--------” (a delimiter).
The remaining lines are the multiple alignment Alignment, with one sequence (containing gaps) on each line.
Output Format.
Let States denote the set of all states in the resulting profile HMM, where we have one Match state for each column of Alignment with fewer than θ gaps (M1, M2, …), one Insertion state for every Match state as well as before the first Match state (I0, I1, I2, …), one Deletion state for every Match state (D1, D2, …), a Start state (S), and an End state (E).
The 1st |States|+1 lines should contain the transition matrix of HMM(Alignment, θ)
The next line should be “--------” (a delimiter)
The remaining |States|+1 lines should contain the emission matrix of HMM(Alignment, θ), with both matrices drawn in the format as shown in the sample output.
Constraints.
0.2 ≤ θ ≤ 0.4
|Σ| = 5
5 ≤ |Alignment| ≤ 10
80 ≤ |Alignment[i]| ≤ 100