Как работает алгоритм BLAST для поиска биологических последовательностей?

Алгоритм BLAST для поиска биологических последовательностей работает следующим образом: en.wikipedia.org iitp.ru

1. Для каждого слова длины W в искомой последовательности составляется список схожих слов, вес выравнивания которых выше определённого порога T. iitp.ru
2. Для каждого слова обрабатывается составленный для него список схожих слов — по заранее построенной хэш-таблице ищутся последовательности в базе данных, имеющие точное вхождение данных слов. iitp.ru
3. Выравнивание расширяется вправо и влево от найденных «затравок» с помощью алгоритма динамического программирования. iitp.ru
4. Расширение выравнивания прекращается, если падение суммарного веса выравнивания от точки последнего максимума достигнет заранее установленного порога X. iitp.ru Длина выравнивания устанавливается в позиции последнего максимума. iitp.ru

BLAST ориентирован на локальное выравнивание, то есть на поиск подобия только в пределах некоторой части последовательности. static.igem.org Результатом локального выравнивания является выбор участка в каждой из последовательностей и выравнивание между этими участками. static.igem.org