Алгоритм BLAST. 
BLAST, парное выравнивание последовательностей

• 1. Составление списка пар слов выше порога T. По умолчанию для белков слово — это участок последовательностей, из трёх аминокислот. Для blastn, размер слов обычно 7, 11, или 15 (выявляется меньше совпадений, но реализуется быстрее чем при 11 или 7). Для megablast размер слова 28 (может быть задан до 64) — очень быстрый поиск для близкородственных ДНК-последовательностей.
• 2. Сканирование базы данных по записям, совпадающим с созданным списком.
• 3. Когда найден хит (то есть совпадение между словом и записью базы данных), слово расширяется в оба направления (сначала без гэпов (пробелов), а затем с их использованием). В исходном (1990) исполнении BLAST, попадания расширялись в каждом направлении. В модификации BLAST от 1997 г., требуются 2 независимых попадания близко друг к другу. Остановка расширения происходит, когда оценка ниже порогового уровня Т. Далее определяются выравнивания с максимальным количеством совпадений между запросом и последовательностью базы данных.

Интерпретация BLAST: оценка сходства выравниваний осуществляется по величинам E-value и S (Score), в большинстве случаев (за исключением blastn и megablast) для этого используется матрица BLOSUM62 (блоковая матрица замен с 62% идентичности).

E-value: имеет низкие значения, когда последовательности гомологичны (при этом высокие значения не означают отсутствия гомологии); возрастает с увеличением длины участка выравнивания и с размером базы данных. Для баз данных нуклеотидных последовательностей результаты BLAST рассматривают при E-value < 10−6 и идентичности от 70%; для баз данных аминокислотных последовательностей — при E-value < 10−3 и идентичности от 25%.E — число выравниваний с оценкой больше или равной оценке S, которая ожидаема как случайное событие в поиске по базе данных.

Значение p — другой путь представления значимости выравнивания: p = 1 — e^-E. Очень маленькое значение E очень схоже со значением p. Значение E от 1 до 10 намного проще интерпретировать, чем соответствующее значение p.

E p.

• 10 0.99 995 460
• 5 0.99 326 205
• 2 0.86 466 472
• 1 0.63 212 056
• 0.1 0.9 516 258 (примерно 0.1)
• 0.05 0.4 877 058 (примерно 0.05)
• 0.001 0.99 950 (примерно 0.001)
• 0.0001 0.1 000
• S (Score) — вычисляется в битах, что позволяет сравнить результаты между поисками в различных базах данных, даже при использовании различных матриц замен.

Проблемы BLAST:

не находит последовательности с низкой степенью родства (решаемо с PSI-BLAST в NCBI, также как скрытыми моделями Маркова);

поиск по запросу 10 000 (или 1 000 000 000) пар оснований (решаемо с большинством BLAST-подобных инструментов, доступных для геномной ДНК: PatternHunter, Megablast, BLAT, и BLASTZ).