Skip to main content
8 of 9
deleted 23 characters in body

Smith-Waterman (and Needleman-Wunsch)

This may be too far fetched so please comment.

Smith-Waterman: The Sequence Alignment Algorithm

I think one of such examples is the Smith-Waterman and Needleman-Wunsch algorithms and their approximations. All of them are essentially doing the same thing. They align two or more strings (sequences). There is a significance in Biology. When DNA or Protein sequences are aligned - regions of structural, functional and evolutionary similarity are revealed.

BLAST as a descendant of Smith-Waterman

A heuristic that approximates Smith-Waterman is BLAST. It allows searching sequences of large databases for Biological similarity. The popularity of BLAST is really great - it's very likely the most widely used algorithm in Biology. The newer areas in Bioinformatics and Genomics have newer and better approximations of Smith-Waterman/Needleman-Wunsch algorithms that are more accurate than BLAST.

Genome Assembly as a descendant of Smith-Waterman

High-throughput approximations of Smith-Waterman and Needleman-Wunsch that are faster than BLAST are used to assemble Genomes from shotgun sequencing - where the product of the sequencer machine is a huge amount DNA reads (billions) from arbitrary parts of the Genome that are very short (50 to 100 nucleotides). The approach was used to complete the Human Genome Project. All modern sequencing is done this way.

Multiple Sequence Alignment an extension of Smith-Waterman

Numerous Multiple Sequence Alignment algorithms exist - they are approximating a multi-sequence version of the Smith-Waterman/Needleman-Wunsch. Multiple sequences are aligned as a group simultaneously to each other. It's a much harder problem than it's pairwise counterpart, but the solutions provide much more insight into Biological function, structure, and evolutionary history of related sequences.