2
$\begingroup$

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?

|cite|improve this question
$\endgroup$
4
$\begingroup$

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
|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – andreas.vitikan Nov 27 '15 at 14:26
  • $\begingroup$ 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. $\endgroup$ – Hendrik Jan Nov 27 '15 at 21:28
  • $\begingroup$ 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 $\endgroup$ – andreas.vitikan Nov 27 '15 at 21:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.