Article View: bionet.software
Article #2561Looping inside Needleman-Wunsch algorithm & good values for the Similairity Matrix
From: almurph
Date: Thu, 09 Oct 2008 10:29
Date: Thu, 09 Oct 2008 10:29
43 lines
3405 bytes
3405 bytes
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)
{
blah;
}
else if(Score == Left + d)
{
blah;
}
else if(Score == Up + d)
{
blah;
}
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
structures...
Any hints/advice/user-experiences/websites/papers much appreciated.
Thanking you,
Al.
Technical Details
Message-ID:
<mailman.295.1223567502.29717.bio-soft@net.bio.net>Path:
arc1-ca.pugleaf.net!g2news2.google.com!news2.google.com!border1.nntp.dca.giganews.com!nntp.giganews.com!nx01.iad.newshosting.com!nx02.iad.newshosting.com!newshosting.com!news-out.superfeed.net!sp6iad.superfeed.net!news-in2.superfeed.net!news.purdue.edu!v30g2000hsa.googlegroups.com!not-for-mailShow Full Headers
Complete Article Headers
X-Google-Thread: fa6b6,35e4c88f45ad7cec,start X-Google-Attributes: gidfa6b6,domainid0,public,usenet X-Google-Language: ENGLISH,ASCII-7-bit Subject: Looping inside Needleman-Wunsch algorithm & good values for the Similairity Matrix From: "almurph@altavista.com" <almurph@altavista.com> Date: Thu, 9 Oct 2008 03:29:58 -0700 (PDT) Message-ID: <mailman.295.1223567502.29717.bio-soft@net.bio.net> Lines: 44 NNTP-Posting-Host: kalo.bio.indiana.edu Organization: http://groups.google.com Path: arc1-ca.pugleaf.net!g2news2.google.com!news2.google.com!border1.nntp.dca.giganews.com!nntp.giganews.com!nx01.iad.newshosting.com!nx02.iad.newshosting.com!newshosting.com!news-out.superfeed.net!sp6iad.superfeed.net!news-in2.superfeed.net!news.purdue.edu!v30g2000hsa.googlegroups.com!not-for-mail Approved: BIOSCI Approval Key <biosci-approval-key@net.bio.net> Newsgroups: bionet.software X-Trace: mailhub227.itcs.purdue.edu 1223567541 7838 129.79.224.26 (9 Oct 2008 15:52:21 GMT) Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit X-Complaints-To: news@purdue.edu NNTP-Posting-Date: Thu, 9 Oct 2008 15:52:21 +0000 (UTC) To: bionet-software@moderators.isc.org X-Envelope-From: news@google.com Complaints-To: groups-abuse@google.com Injection-Info: v30g2000hsa.googlegroups.com; posting-host=86.42.69.8; posting-account=Q4uDswgAAABewI7uG61B1W967GLr75JQ User-Agent: G2/1.0 X-HTTP-UserAgent: Mozilla/4.0 (compatible; MSIE 7.0; Windows NT 5.1; .NET CLR 1.1.4322; .NET CLR 2.0.50727; .NET CLR 3.0.04506.648; .NET CLR 3.5.21022),gzip(gfe),gzip(gfe) X-Mailman-Approved-At: Thu, 09 Oct 2008 10:51:40 -0500 X-BeenThere: bio-soft@net.bio.net X-Mailman-Version: 2.1.4 Precedence: list X-Auth: PGPMoose V1.1 PGP bionet.software iQCVAwUBSO4ojqCIqsWvyF5FAQF1WAP/ZTnDu1ZACsOKGyewk3kjmGOos/GjIWI6 DMQoxJvE3xo+RhthtNwB7YAmsQpSrMohgmLb3povPG31pYHvPYHTqn8iKg+3VicM 4ggd+1prDcAdP220XXHfpst47iHa1yOiCKCW1PmRM8cNkXTw/yMtpG5s3BsorXcc oYtVfPMdsSM= =GxYE X-Original-Bytes: 3069