# Align Two Strings Using Linear Space solved by 160

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 bottomtop vertical edges.

LinearSpaceAlignment(top, bottom, left, right)
if left = right
return alignment formed by bottomtop vertical edges
if top = bottom
return alignment formed by rightleft horizontal edges
middle ← $\lfloor$ (left + right)/2$\rfloor$
midNodeMiddleNode(top, bottom, left, right)
midEdgeMiddleEdge(top, bottom, left, right)
LinearSpaceAlignment(top, midNode, left, middle)
output midEdge
if midEdge = "→" or midEdge = "↘"
middlemiddle + 1
if midEdge = "↓" or midEdge ="↘"
midNodemidNode + 1
LinearSpaceAlignment(midNode, bottom, middle, right)

## 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