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:
References
Smith, Temple F. & Waterman, Michael S. (1981). "Identification of Common Molecular Subsequences". Journal of Molecular Biology. 147: 195–197.
