This sounds quite similar to a banded Smith-Waterman, which cuts off the corners of the matrix using the assumption that the most significant score will likely be close to the main diagonal. A banded alignment is used in things like crossmatch, SSAHA, and some other programs. 
<br><br>Marty<br><br><div><span class="gmail_quote">On 6/15/06, <b class="gmail_sendername">Theodore H. Smith</b> <<a href="mailto:delete@elfdata.com">delete@elfdata.com</a>> wrote:</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<br>Hi people,<br><br>Do you know of any technique to end a Smith-Waterman operation early,<br>by saying that if the operation cannot find a match of a certain<br>desired minimum strength, then we won't do anymore? We'll end the
<br>operation early? We would at every row, check the "Best score we can<br>possibly get based upon the current best score". If the "Best score<br>we could possibly get" is below our desired score, we end the SW
<br>operation.<br><br>Or do you know of any papers on this subject? Or even can you think<br>of good keywords for me to search with? Perhaps the way I'm<br>describing it isn't the best way.<br><br>So, let's say you have a standard SW operation. You have a square
<br>Matrix, and you run from left to right across the matrix, line by<br>line down the matrix. Let's say, the matrix has 90 rows, as we are<br>trying to match a protein sequence of 90 letters.<br><br>Now, is there anyway, some way, by logical analysis or guesswork, to
<br>tell perhaps by the time we get to row 70, we know that we'll not be<br>able to get any better score matches than the one we got, and thus<br>cull the SW operation? So that we don't search through rows 71 to 90?<br>The numbers 70 or 90 don't matter, as long as we can check at every
<br>row, whether the "best match score" gets better or not.<br><br>I have something like this for a global alignment producer, and it<br>slices the time down to a small fraction!! Even though it only kills<br>the last third or so, of the alignment, it still cuts down the time
<br>required down to less than 66%, perhaps even down to 20%.<br><br>Basically, I've spent a few months, as a hobby, putting my inventive<br>capacity into making a SmithWaterman-based, BLAST-like searcher. I do<br>things like this because I can, although I think this is probably the
<br>most complex thing I'll ever work on in my entire life.<br><br>My BLAST-like searcher, stores all of it's data in a tree (a "trie"<br>actually). Protein sequences that are shared across many proteins,<br>are stored in the root or earlier branches of the tree. So any work
<br>done on the early parts of the tree is reused across many many<br>proteins. This is good, it saves CPU-time. Most of the work then, is<br>done processing the leaves of the tree.<br><br>This is why the last few rows of the SW Matrix are so important,
<br>because most of the work is done there to process them! This is why I<br>want to shave the last few rows off, when possible. But of course,<br>the idea is to process the entire leaf, if the "best score match" is
<br>going to get better. For that reason some kind of quick hueristic<br>predictive trick would be desired, so that we don't cull good leaves.<br><br>Any ideas anyone? This would mean so much to me if I can find a<br>paper, or if anyone even knows what I am talking about and can give
<br>me some help.<br><br>If anyone doesn't know what I am talking about but feels like helping<br>should you understand me, please let me know that I need to explain<br>this in a different better way?<br><br>I've spent many months on this algorithm. I have a nearly identical
<br>algorithm that already works to do global alignmnents, it just<br>doesn't do local alignments, and the global aligner is pretty quick<br>actually. It's just the CPU-saving tricks I've done with global<br>alignment, don't seem to cross over to local alignment, and I'm
<br>scratching my brain wondering if these past few months were a waste<br>or not.<br><br>Because of this "loss of tricks" (that worked with global alignment)<br>situation, I am asking for new tricks, here!<br><br>
Thankfully, I was smart enough to do this work part-time, as a<br>hobby :) I also have a proper normal job that doesn't rely on the<br>success of proposed inventions to make me money. I decided it wasn't<br>a good idea to starve myself just for an idea that might never
<br>produce anything worthwhile.<br><br>Help anyone! Thanks a lot :)<br><br>--<br><a href="http://elfdata.com/plugin/">http://elfdata.com/plugin/</a><br><br><br><br>_______________________________________________<br>Bioinformatics.Org
 general forum  -  <a href="mailto:BiO_Bulletin_Board@bioinformatics.org">BiO_Bulletin_Board@bioinformatics.org</a><br><a href="https://bioinformatics.org/mailman/listinfo/bio_bulletin_board">https://bioinformatics.org/mailman/listinfo/bio_bulletin_board
</a><br></blockquote></div><br><br clear="all"><br>-- <br>-- <br>Martin Gollery<br>Associate Director<br>Center For Bioinformatics<br>University of Nevada at Reno<br>Dept. of Biochemistry / MS330<br>775-784-7042<br>-----------