Wat is BLAST?

Een zoekvraag van $300$ residuen tegen een databank van $10^{11}$ uitlijnen met volledig dynamisch programmeren zou $3\times 10^{13}$ celbewerkingen per zoekactie kosten. BLAST (Altschul en collega’s, 1990) ruilt een beetje gevoeligheid in voor duizendvoudige snelheid met drie stappen: (1) maak een lijst van de woorden van de zoekvraag (drie residuen voor eiwitten, elf basen voor DNA) en van hun hoogscorende buren; (2) doorzoek de databank op exacte woordtreffers — de seeds; (3) verleng elke seed in beide richtingen zonder hiaten tot de score een vastgestelde hoeveelheid onder haar beste waarde zakt, en houd de hoogscorende segmentparen (HSP’s) over, en verbind daarna nabije HSP’s met gehiaat dynamisch programmeren in een smalle band. Een echte homoloog bevat vrijwel altijd minstens één exact woord van drie residuen; een toevallige gelijkenis zelden, en die wordt nooit verlengd.