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

Assignment

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

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

• Write a function global_alignment that takes the location of a FASTA file containing two amino acid sequences $$v$$ and $$w$$. The function must return a global alignment of $$v$$ and $$w$$, represented as a tuple of two strings with indels represented by hyphens (-). If multiple global 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.

>>> global_alignment_score('data01.faa')
8

>>> global_alignment('data01.faa')
('PLEASANTLY', '-MEA--N-LY')

Resources

• Needleman SB, Wunsch CD (1970). A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of molecular biology 48(3), 443-453. ²