BLAST কী?

Alinhar uma consulta de $300$ resíduos contra um banco de $10^{11}$ por programação dinâmica completa custaria $3\times 10^{13}$ atualizações de célula por busca. O BLAST (Altschul e colaboradores, 1990) troca um pouco de sensibilidade por mil vezes mais velocidade em três etapas: (1) lista as palavras da consulta (três resíduos para proteínas, onze bases para DNA) e suas vizinhas de alto escore; (2) varre o banco em busca de correspondências exatas de palavra — as sementes; (3) estende cada semente nos dois sentidos sem lacunas até que o escore caia uma quantidade fixada abaixo de seu melhor valor, guardando os pares de segmentos de alto escore (HSPs) e unindo depois os HSPs próximos por programação dinâmica com lacunas numa faixa estreita. Uma homóloga verdadeira quase sempre contém ao menos uma palavra exata de três resíduos em comum; uma semelhança de acaso raramente contém, e nunca é estendida.