FASTA

Although the Smith-Waterman algorithm published in 1981 was elegant, it was too slow for aligning large number of sequences. Biologists needed speed, and FASTA, a heuristic algorithm developed in 1985 by David J. Lipman and William R. Pearson, served their purpose.

FASTA and most other later alignment algorithms used seeding and extension method to speed up the search process. In this approach, the algorithms heuristically look for multiple consecutive letters conserved between two sequences (seed) and then perform Smith-Waterman alignment only in the neighborhoods of those seeds. That way the effective search space of Smith-Waterman is reduced substantially, thus speeding up the whole alignment process.