Find a longest common subsequence of multiple strings.

Assignment

In this assignment we will construct an alignment for the longest common subsequence of three strings. To score alignments, we use a scoring function in which the score of a multiple alignment column is 1 if all three symbols are identical and 0 otherwise. Your task:

• Write a function multiple_lcs_length that takes the location of a FASTA file containing three DNA strings. The function must return the length of a longest common subsequence of the three given strings.

• Write a function multiple_lcs that takes the location of a FASTA file containing three DNA strings. The function must return a multiple alignment of the three given strings achieving the maximum score. If more than one multiple alignment achieves the maximum score, the function may return any one.

Example

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

>>> multiple_lcs_length('data01.fna')
3

>>> multiple_lcs('data01.fna')
('A-TAT---CC--G-', '--T-----C-C-GA', '-AT--GTAC--TG-')