Write a function lcs that takes two arguments: i) the location of a FASTA file containing two DNA strings $$v$$ and $$w$$ and ii) another file location. The function must write a longest common subsequence of $$v$$ and $$w$$ in FASTA format to the file whose location is passed as the second argument.

Example

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

        >>> lcs('data01.fna', 'output01.fna')
>>> print(open('output01.fna').read().rstrip())
>seq01
AACTTG

Resources

Bergroth L, Hakonen H, Raita T (2000). A survey of longest common subsequence algorithms. In: Proceedings of the Seventh International Symposium on String Processing and Information Retrieval, 39-48. ²
Chvatal V, Sankoff D (1975). Longest common subsequences of two random sequences. Journal of Applied Probability 12(2), 306-315. ³
Masek WJ, Paterson MS (1980). A faster algorithm computing string edit distances. Journal of Computer and System sciences 20(1), 18-31. ⁴