BI - The Needleman-Wunsch Algorithm

Questions

---

IMPORTANTE

IMPORTANTE The Needleman-Wunsch Algorithm NOTE: This is a dynamic algorithm that return the optimal alignment of two sequences.

Rules for constructing the matrix:

• Initialize the first row to $0,-1,-2,\dots$
• Initialize the first column to $0,-1,-2,\dots$
• The element $i,j$ is the maximum of the following three rules.
  • A diagonal step, is not a malus
  • An orizontal or vertical step is a malus of $-1$
  • If the row $i$ is equal to the column $j$ it’s a bonus of $+1$, else: $+0$

Once constructed the matrix, we take the last element, and reconstruct the allignment. Watch the example, they are more clear.

~Ex.: Rules

~Ex.: Algorithm

~Ex.: Algorithm II

---

Slides with Notes

IMPORTANTE The Needleman-Wunsch Algorithm NOTE: This is a dynamic algorithm that return the optimal alignment of two sequences.

Rules for constructing the matrix:

• A diagonal step, is not a malus
• An orizontal or vertical step is a malus of $-1$
• If the row $i$ is equal to the column $j$ it’s a bonus of $+1$, else: $+0$
• The element $i,j$ is the maximum of this three rules.

Once constructed the matrix, we take the last element, and reconstruct the allignment. Watch the example, they are more clear.

~Ex.: Rules

~Ex.: Algorithm

~Ex.: Algorithm II