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.
Submission:
Submit your Python3 source code (two programs, one for alignment with and one for
alignment without affine gap penalty; make sure to include instructions of how to run your
programs) via Blackboard by Friday April 9th, 2021 11:59PM.
