[Computational-biology] Looping inside Needleman-Wunsch algorithm & good values for the Similairity Matrix

almurph from altavista.com via comp-bio%40net.bio.net (by almurph from altavista.com)
Thu Oct 9 05:35:28 EST 2008

Hi everyone,

	Concerning the Needleman-Wunsch algorithm (cf.
http://en.wikipedia.org/wiki/Needleman-Wunsch_algorithm) I have
noticed a possible loop.

	Inside the algorithm there is an important decision making mechanism.
Its a "if, else if, else if" structure like:

if(ScoreValue == DiagonalValue + SimilarityValue(i, j)
else if(Score == Left + d)
else if(Score == Up + d)

	I've been playing with value of the similarity matrix and for certain
values I can get the algorithms to stick as there is no else clause to
offer an out if none of the above conditions are met. Now I know that
I could introuduce an else statement and avoid the loop but it does
not address the fundamental probalm of constructing a useful
Similarity matrix.

	It's on this point issue that I want to ask for help. The similaity
Matrix that I built for my task is ultimately causing this problem. So
i need to make it better. My question is: what properties should a
good Similarity matrix have to avoid this loop? How does one go about
constructing an effective Similarity matrix? What properties should it
have? I'm not referring to the simple structure that score 1 for a
match and 0 for a mismatch. i'm referring to more complex
	Any hints/advice/user-experiences/websites/papers much appreciated.

Thanking you,

More information about the Comp-bio mailing list