Feb. 16, 2014, 8:44 p.m. by Rosalind Team
The pseudocode below for LinearSpaceAlignment describes how to recursively find a longest path in the alignment graph constructed for a substring vtop+1 ... vbottom of v and a substring wleft+1 ... wright of w. LinearSpaceAlignment calls the function MiddleNode(top, bottom, left, right), which returns the coordinate i of the middle node (i, j) defined by the sequences vtop+1 ... vbottom and wleft+1 ... wright. LinearSpaceAlignment also calls MiddleEdge(top, bottom, left, right), which returns → , ↓, or ↘ depending on whether the middle edge is horizontal, vertical, or diagonal. The linear-space alignment of strings v and w is constructed by calling LinearSpaceAlignment(0, n, 0, m). The case left = right describes the alignment of an empty string against the string vtop+1 ... vbottom, which is trivially computed as the score of a gap formed by bottom − top vertical edges.
Find the highest-scoring alignment between two strings using a scoring matrix in linear space.
Given: Two long amino acid strings (of length approximately 10,000).
Return: The maximum alignment score of these strings, followed by an alignment achieving this maximum score. Use the BLOSUM62 scoring matrix and indel penalty σ = 5.
8 PLEASANTLY -MEA--N-LY