# Why doesn't the Needleman-Wunsch algorithm find solutions that begin with a gap?

I have implemented in C++ the Needleman-Wunsch algorithm for pairwise sequence alignment using the following scores: +1 for match (regardless of base), -1 gap penalty and -1 for a mismatch. Given two sequences of length $m$ and $n$ the algorithm then generates the $mn$ search space row by row as per the algorithm's specifications and backtracks generating all solutions of maximum score. Given two sequences in which the first two letters overlap ie:

GCATGCU


and

GATTACA


the algorithm succesfully generates all the alignments of maximum score. Howeever, given two sequences of the kind:

ACTGCUGCTA


and

UGCTAATCGU


the algorithm fails to find any of the solutions that begin with a gap in sequence 1 or 2, thus failing to find the optimal solution as well:

ACTGCUGCTA-----
-----UGCTAATCGU


Once I add the letter A to the second sequence the algorithm once again has no problem finding the optimal solution (which in this case begins with a match and not a gap)

ACTGCUGCTA-----
A----UGCTAATCGU


Could someone explain to me why the algorithm doesn't find this subset of solutions and perhaps how I can modify it to find these solutions as well?

Your optimal alignment seems to be an optimal local alignment, the best substring match. Needleman-Wunsch is for global alignment. With the simple program by Eddy that you can find on the internet I have determined a global score of 0. This is better than the gobal score you get: -5 (for 10 gaps and 5 matches).

Sequence X: GCATGCU
Sequence Y: GATTACA
Scoring system: 1 for match; -1 for mismatch; -1 for gap

Dynamic programming matrix:
G    A    T    T    A    C    A
0   -1   -2   -3   -4   -5   -6   -7
G   -1    1    0   -1   -2   -3   -4   -5
C   -2    0    0   -1   -2   -3   -2   -3
A   -3   -1    1    0   -1   -1   -2   -1
T   -4   -2    0    2    1    0   -1   -2
G   -5   -3   -1    1    1    0   -1   -2
C   -6   -4   -2    0    0    0    1    0
U   -7   -5   -3   -1   -1   -1    0    0

Alignment:
X: GCA-TGCU
Y: G-ATTACA
Optimum alignment score: 0

• Is there anyway for Needleman-Wunsch to produce a global alignment optimum or is a different algorithm needed for that? Is the Needleman-Wunsch algorithm suitable for determining the order of several small fragments (with overlapping ends and less gaps) or is it better used to determine the compatibility between a small fragment and a large one? – andreas.vitikan Nov 27 '15 at 14:26
• Yes there is a bunch of variations, basically differing in where to start and where to end the scoring. Needleman-Wunsch counts every symbols so is global. Smith-Waterman counts the best overlap, and is local. There is indeed also a variant where you have partially overlapping alignments. See my answer to a related question. – Hendrik Jan Nov 27 '15 at 21:28
• Thank you! That was a very informative post and cleared everything up for me :D I think what I was really looking for was the Smith-Waterman algorithm – andreas.vitikan Nov 27 '15 at 21:40