FASTA

FASTA is a heuristic algorithm and software package for biological sequence alignment developed by David Lipman and William Pearson in 1985. It was the first widely used tool for searching protein and DNA databases, predating BLAST by five years and establishing the heuristic paradigm that would dominate bioinformatics for decades.

FASTA operates by finding short exact matches (k-tuples, typically of length 1-2 for proteins and 4-6 for DNA) between a query sequence and database sequences. It ranks these initial matches by density, identifies diagonals in the alignment matrix where multiple k-tuples cluster, and then rescores the best diagonals using a substitution matrix such as the PAM matrix or BLOSUM matrix. The highest-scoring diagonals are joined and refined using a banded dynamic programming step that restricts the search space.

The algorithm was revolutionary not for its biological insight but for its empirical pragmatism. Lipman and Pearson recognized that exact algorithms like the Needleman-Wunsch algorithm would never scale to database search, and that biological sequences contain enough local structure — conserved regions, motifs, repeated domains — that heuristic methods would find true homologies with acceptable sensitivity. FASTA's success proved this bet correct and paved the way for the faster but less sensitive BLAST heuristic.

FASTA occupies a curious position in the history of bioinformatics: it was the pioneer, yet it is now the slower, more sensitive alternative to BLAST. For distantly related sequences where BLAST's speed-optimized heuristics miss weak similarities, FASTA remains the tool of choice. The lesson is that algorithmic progress in biology is not linear — trade-offs between speed and sensitivity persist, and the 'older' tool sometimes remains the better tool for specific questions.