Find a middle edge in the global alignment graph in linear space.

Assignment

Write a function middle_edge that takes the location of a FASTA file containing two amino acid sequences $$v$$ and $$w$$. The function must return a middle edge in the global alignment graph of $$v$$ and $$w$$, where the optimal path is defined by the BLOSUM62 scoring matrix and a linear indel penalty equal to 5. The middle edge must be returned as a tuple $$((i, j), (k, l))$$, where $$(i, j)$$ connects to $$(k, l)$$. If there exist multiple middle edges, 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.

>>> middle_edge('data01.faa')
((4, 2), (5, 3))

Resources

• Hirschberg DS (1975). A linear space algorithm for computing maximal common subsequences. Communications of the ACM 18(6), 341-343. ²

• Powell DR, Allison L, Dix TI (1999). A versatile divide and conquer technique for optimal string alignment. Information Processing Letters 70(3), 127-139. ³