Основы биоинформатики - Огурцов А.Н. 2013

Методы биоинформационного анализа
Алгоритмы выравнивания последовательностей
Приближённые методы быстрого поиска в базах данных

По общепринятой практике гены из нового генома сравниваются со всеми последовательностями из базы данных.

Сначала обычно используют приближённые методы, которые могут работать хорошо и быстро для поиска похожих последовательностей, однако при поиске очень отдалённых связей они могут работать хуже, чем точные методы.

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

Типичный приближённый подход выбирает некое малое целое значение к и находит все подстроки длиной к символов в последовательности запроса, которые появляются также в какой-либо последовательности в базе данных.

Такая короткая идентичная последовательность называется "слово" или "k-кортеж" ("k-tuple").

В математике кортежем называют последовательность конечного числа элементов. В некоторых языках программирования кортеж является особым типом структуры данных. В языке Python кортеж (англ. tuple) отличается от списка тем, что кортеж нельзя изменять.

Само слово "tuple" - это своеобразный обобщающий "суффикс" в перечислении слов всё большей длины: single, double, triple, quadruple, quintuple, sextuple, septuple, octuple, ..., n-tuple,...

Последовательность-кандидат - это последовательность в базе данных, содержащая большое число подходящих k-кортежей.

Затем для отобранного набора последовательностей-кандидатов производятся вычисления приближённого оптимального выравнивания с временным и пространственным ограничением, которое предусматривали проходы по матрице в пределах диагоналей, содержащих многочисленные совпадающие наборы k-кортежей.

Методы слов, или k-кортежей, которые реализованы в алгоритмах таких программ, как FASTA и BLAST, являются достаточно быстрыми и позволяют просматривать полную базу данных при поиске последовательности-кандидата, которая даёт наилучшее выравнивание с последовательностью запроса.

Алгоритмы программ FASTA и BLAST являются эвристическими, то есть основанными на эмпирических методах машинного программирования, в которых решение находится по установленным опытным путём правилам и используется обратная связь для уточнения результата.

Основная операция при поиске в базе данных - выравнивание последовательности запроса с каждой последовательностью-кандидатом базы данных; и если эвристические методы позволяют выполнить эту операцию значительно быстрее, то лучше применять именно их, а не алгоритмические методы динамического программирования.

Программа FASTA обеспечивает как высокий уровень чувствительности, так и большую скорость поиска подобия. Чувствительность достигается за счёт реализованных в программе FASTA алгоритмов оптимизированного локального выравнивания и анализа матрицы замен.

Сначала FASTA подготавливает список слов-кортежей, выбранных из пары сравниваемых последовательностей. Слово представляет собой строку из 3-6 нуклеотидов или 2-3 аминокислот. При этом слова-кортежи не должны перекрываться. Затем программа сопоставляет слова-кортежи и ведёт подсчёт совпадений.

Подобно построению диаграммы и вычислению счёта точечной матрицы, FASTA отбирает варианты с максимальным числом слов на диагонали, находит совпадение с возможно высоким счётом и помечает результат (совпадение слов) как элемент № 1. Если максимальный счёт оказывается достаточно большим, программа переходит ко второму уровню.

На втором уровне для каждого лучшего совпадения слов производится поиск соседних приблизительных совпадений, и если значение счёта удовлетворительно, то программа объединяет короткие сегменты элемента № 1, строит из них более длинную диагональ точечной матрицы и вычисляет счёт после включения пропусков и оценки штрафа.

Наилучший счёт из счетов второго уровня называют начальным числом. FASTA сохраняет счёта начальных чисел, вычисленные для всех сравнений последовательности запроса с предметной последовательностью. После того как все последовательности базы данных проверены, те последовательности, которые дают максимальные счёта начальных чисел, используются для построения (с помощью алгоритма Смита-Уотермена) локального выравнивания с возможно большим оптимальным счётом.

Формат FASTA принят во многих программах множественного выравнивания последовательностей.