Project 3: Sequence Alignment with Affine Gap Penalty
Tasks:
1. Implement the sequence alignment algorithm without affine gap penalty (the algorithm that does not distinguish gap configuration)
2. Implement the sequence alignment algorithm with affine gap penalty (the algorithm that distinguish between contiguous gaps and scattered gaps, and uses three dynamic programming matrices instead of just one)
Scoring Function:
• Match of identical nucleotides: +1
• Match of non-identical nucleotides: -2
• Gap open: -5
• Gap extension: -1
Hits:
We expect to see that gaps are aggregated together when affine gap penalty is applied.
For example, with affine gap we expect an alignment of:
AGCGAGGC
| *|||| A--CAGGC
And without affine gap we expect an alignment of:
AGCGAGGC
| | ||||
A-C-AGGC
You can always check the alignment score by adding up column-wise matching/gap scores, and compare it with the score produced by the dynamic programming, to ensure the correctness of your program.
