Dynamic Programming Example: Solution is given. I\'m looking for an explanantion

Question

Dynamic Programming Example: Solution is given. I'm looking for an explanantion that will help me understand the process in getting the answer! Thanks!

17) Dynamic programming, popular for sequence alignment, can also be used for spell checking Assuming that a match is worth 10, a mismatch is worth 5, and a gap "costs" -5, which of these four words is closest to the word "graffe" typed by a user? Write the score of the optimal alignment next to each word (gaps at the start or at the end do not count). A) gaff B) graft C) grail D) giraffe best score: 40-5 35 best score: 40+5 45 best score: 30+5+5 = 40 best score: 60-5-55

Explanation / Answer

Match - same letters

Mismatch - different letters

Gap - we need space in between to align other letters correctly.

Word is "graffe"

A) gaff

lets align this word with graffe

So we found that 4 letters are matching and we need one gap, indicated by #.

So total score is 40 - 5 = 35

B) graft

So we found that 4 letters are matching and we have one mismatch 't'.

So total score is 40 + 5 = 45

C) grail

So we found that 3 letters are matching and we have two mismatches 'i' and 'l'.

So total score is 30 + 5 + 5 = 40

4) giraffe

So we found that 6 letters are matching and we need one gap, indicated by #.

So total score is 60 - 5 = 55

g r a f f e g # a f f

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

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