Filtration efficiency in rapid homology search statistical algorithms
Pavel A. Pevzner · Biopolymers and Cell · 1990
П. А. Певзнер ЭФФЕКТИВНОСТЬЮ ФИЛЬТРАЦИИ В СТАТИСТИЧЕСКИХ АЛГОРИТМАХ БЫСТРОГО ПОИСКА ГОМОЛОГИИ При поиске локальных гомологии, (поиск гомологий в генетических банках, выбор оптимальных олигонуклеотидных зондов и т. п.) возникает проблема их «быстрого» поиска.Квадратичная трудоемкость алгоритмов динамического программирования заставляет прибегать к методам фильтрации, позволяющим быстро b 0 отбрасываются.Конечно, для выявления окон с b > Ь 0 можно ki-k 2 раз применить какой-нибудь из алгоритмов глобального поиска гомологий (например, алгоритм Нидельмана-Вунша) с трудоемкостью п 2 (k u k 2 -длины анализируемых последовательностей, η -длина окна) и получить для каждой пары окон, начинающихся в позициях і и /, точные значения расстояния b(i, j).Если при этом нас интересуют только позиции (i, j) с уровнем расстояния b(i, j) b 0 не нужна.Методы фильтрации позволяют отказаться от трудоемкого определения расстояния b(i, j) между всеми окнами путем введения легко вычисляемого фильтра /(г, /), принимающего два значения 0 и 1, при этом из f(i, /) = 1 следует, что b (i, j) > b 0 .С введением фильтра f процедура поиска гомологий становится двухступенчатой: на первом этапе (фильтрация) вычисляется функция f(i,j) (при этом пары окон, для