Find the highest-scoring local alignment between two strings using a scoring matrix.

Assignment

In this assignment we will construct a highest-scoring local alignment (with linear gap penalties) between two strings. To score alignments, we use the PAM250 scoring matrix and an indel penalty $$\sigma = 5$$. Your task:

• Write a function local_alignment_score that takes the location of a FASTA file containing two amino acid sequences $$v$$ and $$w$$. The function must return the local alignment score of $$v$$ and $$w$$.

• Write a function local_alignment that takes the location of a FASTA file containing two amino acid sequences $$v$$ and $$w$$. The function must return a local alignment of $$v$$ and $$w$$, represented as a tuple of two strings with indels represented by hyphens (-). If multiple local alignments achieving the maximum score exist, the function may return any one.

Example

In the following interactive session, we assume the FASTA file data01.faa¹ to be located in the current directory.

>>> local_alignment_score('data01.faa')
15

>>> local_alignment('data01.faa')
('EANL-Y', 'ENALTY')

Resources

• Altschul SF, Erickson BW (1986). Optimal sequence alignment using affine gap costs. Bulletin of mathematical biology 48(5-6), 603-616. ²

• Gotoh O (1982). An improved algorithm for matching biological sequences. Journal of molecular biology 162(3), 705-708. ³