How does PatternHunters algorithm compare with the Smith-Waterman and Needleman-Wunsch algorithms?
Answer.The Needleman-Wunsch algorithm finds the best global alignment between two sequences, whereas Smith-Waterman and PatternHunter find the best local alignments. Smith-Waterman assigns a negative score/weight to mismatches (e.g. it requires a gap penalty); this has the effect of maximizing locally optimal alignments at the expense of the global alignment. Needleman-Wunsch usually loses subsequence matches. Both Smith-Waterman and Needleman-Wunsch compare all bases in one sequence against all bases in another sequence, a time consuming method which doesn’t lend itself well to large DNA sequences. PatternHunter indexes one sequence and uses this to quickly find short exact “seed” matches (hits), which are then extended into longer alignments. With the optimal multiple spaced seed technology, PatternHunter achieves Smith-Waterman sensitivity at a speed 3000 times faster. See the PatternHunter II paper for further details – this can be found in the PatternHunter papers section of the B
