Description
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.
