Search 12:15 PM * 31%. Homework3.pdf Figure 1: A Markov Model with transition pr

Question

Search 12:15 PM * 31%. Homework3.pdf Figure 1: A Markov Model with transition probabilities and probabilities of each state. Red square, match state; green diamond, insert state; blue circle, delete state. Arrows indicate probability of going from one state to the next transitions froen each state; e, the backgroand probability will be one of 1/2-05, 1/3-0.33, or 1/1). Now caleulate the probability in part I as a log odds soore. Real DNA sequences are inbomogeneoas and can be described by a hidden Markox model with hidden states representing different types of nuclootide composition. Consider an HMMM that includes two hidden states and L for high and lower C +G content, respectively. Initial probabilities for both H and L are equal to 0.5, while transition probabialities are as from states H and L with probabilities 0.2,0.3,0.2,0.3, and 0.3,0.2,0.3, 0.2, respectively Use the Viterbi algorithm to define the most likely sequence of hidden states for the sequence - GGCACTGAA Use the i o initialization gtates, VO(0) = 0, Vy(O--inf. ½(0)--inf and for 1: L. use Vii) log(ex))+mar(log-1))+log(au)).For each i, compate each hidden state, , parameter: V() and Vli). Remember, k is each hidden state as well that should be computed for each of these (to get the max). The traceback pointer to the hidden state value is the greater of the two. (The Viterbi algorithm is found on p 56 in Durbin et al.) 3 For the hidden Markow model defined above, find the probability of the sequence oc- curring, P), by both the forward algorithm and the backward algorithm (found on pages 57 and 58 in Durbin et al.). The last líklen state transitions to the end state must occur with 4m= 1 and «to = 1, For the forward algorithm, give the Prfw(i) +feli) for each i. e transitions are equiprobable with a-0.5, -0.5. The For the hidden Markov model defined above, find the posterior probabilities of states H and L at the last position of z -GGCA and GGCACTGAA Use the formula: Open With Print

Explanation / Answer

Answer)

The Viterbi algorithm calculations are performed here in logarithmic mode (base 2), which is recommended in general to avoid an underflow error. We use a tilde to designate new values of parameters, so a˜kl = log2 akl, etc. As the recursion equations we have

Vl(i + 1) = ˜el(xi+1) + max k (Vk(i) + ˜akl),

where V is the logarithm of v. The Viterbi algorithm is initialized at the begin state designated as 0, and scores VH (i), VL(i) are calculated in turn

i = 0, V0(0) = 0, VH (0) = , VL(0) = ;

i = 1, VH (1) = ˜eH (G) + ˜a0H = 2.736966,

VL(1) = ˜eL(G) + ˜a0L = 3.321981;

i = 2, VH (2) = ˜eH (G) + VH (1) + ˜aHH = 5.473931,

VL(2) = ˜eL(G) + VH (1) + ˜aHL = 6.058893;

i = 3, VH (3) = ˜eH (C) + VH (2) + ˜aHH = 8.210897,

VL(3) = ˜eL(C) + VH (2) + ˜aHL = 8.795859;

i = 4, VH (4) = ˜eH (A) + VH (3) + ˜aHH = 11.532825,

VL(4) = ˜eL(A) + VH (3) + ˜aHL = 10.947862;

i = 5, VH (5) = ˜eH (C) + VL(4) + ˜aLH = 14.006756,

VL(5) = ˜eL(C) + VL(4) + ˜aLL = 14.006756;

i = 6, VH (6) = ˜eH (T) + VH (5) + ˜aHH = 17.328684,

VL(6) = ˜eL(T) + VL(5) + ˜aLL = 16.480673;

i = 7, VH (7) = ˜eH (G) + VL(6) + ˜aHH = 19.539581,

VL(7) = ˜eL(G) + VL(6) + ˜aLL = 19.539581;

i = 8, VH (8) = ˜eH (A) + VH (7) + ˜aHH = 22.861509,

VL(8) = ˜eL(A) + VL(7) + ˜aLL = 22.013512;

i = 9, VH (9) = ˜eH (A) + VL(8) + ˜aLH = 25.657368,

VL(9) = ˜eL(A) + VL(8) + ˜aLL = 24.487443.

The most probable path is determined by the traceback procedure: = HHHLLLLLL,

while P(x, ) = 2VL(9) = 4.251528 × 108.

For sequence x the Viterbi path is unique, because at each step i of the algorithm the maximum score V•(i) was derived unambiguously from only one of the two previous values V•(i 1).

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.