Align Two Strings Using Linear Space solved by 325

The pseudocode below for LinearSpaceAlignment describes how to recursively find a longest path in the alignment graph constructed for a substring v_top+1 ... v_bottom of v and a substring w_left+1 ... w_right 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 v_top+1 ... v_bottom and w_left+1 ... w_right. 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 v_top+1 ... v_bottom, which is trivially computed as the score of a gap formed by bottom − top vertical edges.

Global Alignment in Linear Space Problem

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.

Sample Dataset

PLEASANTLY
MEANLY

Sample Output

8
PLEASANTLY
-MEA--N-LY

Extra Dataset

Click for an extra dataset