Find a Middle Edge in an Alignment Graph in Linear Space solved by 371

Feb. 16, 2014, 8:43 p.m. by Rosalind Team

Middle Edge in Linear Space Problem

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

Given: Two amino acid strings.

Return: A middle edge in the alignment graph of these strings, where the optimal path is defined by the BLOSUM62 scoring matrix and a linear indel penalty equal to 5. Return the middle edge in the form “(i, j) (k, l)”, where (i, j) connects to (k, l).

Sample Dataset

PLEASANTLY
MEASNLY

Sample Output

(4, 3) (5, 4)

Extra Dataset

Please login to solve this problem.