Smith-Waterman Algorithm

• A dynamic programming algorithm for sequence alignment
• Widely used in bioinformatics ()

An Example (1/2)

• Sequence 1 = ACACACTA
• Sequence 2 = AGCACACA
• match: +2, mismatch/gap: -1

An Example (2/2)

• Alignment result:
• Score = 12
• Sequence 1 => A-CACACTA
• Sequence 2 => AGCACAC-A

Homework

• Implement Smith-Waterman algorithm on Qtspim with following requirements
• Lengths of two input sequences can be changed or unequal
• Scores: match: +3 , mismatch: -1 , gap: -2
• Traceback: Starting at the highest score in the scoring matrix and ending at a matrix cell that has a score of 0

Homework

• Output should include:
• The highest score in the scoring matrix
• The traceback direction from the highest score to the 0 score
• (direction: (3) , (2) , (1) )
• Recommended priority: 3 > 2 > 1 seq 1 Example:

Homework