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

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

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

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