Genome annotation relies on comparing new sequences with established databases. Initial solutions included the Needleman-Wunsch algorithm for global alignment and Smith-Waterman for local alignment, using experimentally derived mutation matrices like BLOSUM62. For multiple sequence alignment (MSA), progressive heuristics like the Clustal algorithm simplify the computationally heavy process. These methods involve pairwise alignment, clustering to form a guide tree, and refining consensus sequences with tools like T-Coffee or MUSCLE. Visual summaries, such as sequence logos and position weight matrices, help identify specific motifs in protein and DNA sequences, revealing functionally significant amino acid patterns.
The development of genetic sequencing started with insulin in 1952, eventually progressing to the first protein structure in 1958. Early database efforts in 1965 by Margaret Dayhoff introduced the single-letter code for amino acids, optimizing computer analysis. By the 1970s, researchers developed dot plots to visualize sequence similarity and established the foundations of bioinformatics. Major advancements continued with the creation of the PAM matrix, the GenBank repository, and faster search heuristics like FASTA. The explosion of genomic data mandated moving beyond slow dynamic programming, setting the stage for the highly cited 1990 release of the Basic Local Alignment Search Tool (BLAST).
BLAST operates through several key stages, starting with database indexing where sequences are divided into short words called k-mers. These k-mers are converted into numerical keys and stored in a searchable binary tree, allowing for rapid retrieval. When a query is initiated, it is also broken into k-mers and compared against the indexed database using a scoring scheme that considers similar amino acids. Potential matches, or seeds, are identified based on a configurable threshold. These matches are then extended in both directions until the alignment score drops below a specific limit, ensuring high performance while maintaining sensitivity across massive datasets.
Results are evaluated using the E-value, which represents the probability that a found alignment occurred by random chance. Lower E-values, such as those below 10^-50, typically indicate nearly identical sequences, while values closer to 1 suggest random matches. Users can choose between various specialized versions, including Nucleotide BLAST and Protein BLAST. Advanced iterations like PSI-BLAST use iterative profile mapping to find very distant homologs, following an evolutionary trail. Translatable versions like BLASTx allow researchers to search nucleotide queries against protein databases across all six possible reading frames, which is essential for identifying protein-coding regions in newly sequenced genomes.