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?