In 1966, Vladimir Levenshtein introduced the notion of the edit distance between two strings as the minimum number of edit operations needed to transform one string into another. Here, an edit operation is the insertion, deletion, or substitution of a single symbol. For example, TGCATAT can be transformed into ATCCGAT with five edit operations, implying that the edit distance between these strings is at most 5.

Assignment

Write a function edit_distance that takes the location of a FASTA file containing two amino acid sequences $$v$$ and $$w$$. The function must return the edit distance between $$v$$ and $$w$$.

Example

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

>>> edit_distance('data01.faa')
5

Resources

• Levenshtein VI (1966). Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics Doklady 10(8), 707-710. ²

• Navarro G (2001). A guided tour to approximate string matching. ACM computing surveys 33(1), 31-88. ³