Интернет-журнал "Домашняя лаборатория", 2008 №5
Шрифт:
Решением является то, что мы до применения методов динамического программирования сначала выбираем правильных кандидатов для сравнения. Есть такая программа BLAST (basic local alignment search tool), которую все биологи очень любят, она почти правильная. То есть она почти всегда работает так, как требует "золотой стандарт".
Основная идея ее работы заключается в хешировании. В самом начале мы один раз проходим по всему банку и для каждого короткого слова с заранее зафиксированной длиной мы запишем список позиций, где оно встречается в банках.
Здесь
Дальше мы идем вдоль последовательности "Query" (та последовательность, которую мы хотим прогнать по банку) и выбираем очередные слова. Смотрим в таблице, где встречается это слово, вытягиваем найденные последовательности из банка и строим выравнивание их с нашей исходной последовательности. Это делается быстро, так как мы сравниваем нашу последовательность не со всеми последовательностями из банка, а только те, которые соответствуют нашему "слову" (tttgc в показанном случае). И выравнивание строим тоже не так аккуратно, как это делает алгоритм динамического программирования, а используем упрощенную схему.
Затем мы оцениваем статистическую значимость этого выравнивания — так называемую e-value. Вообще, есть два понятия, которые очень часто встречаются в биоинформатике: e-value и p-value. Е-value — это сколько мы ожидаем увидеть совпадений с таким весом (то есть такого качества), если бы у нас наши последовательность и банк были случайными. Если они случайные, то мы ожидали бы увидеть е– 2 совпадений.
e-value — это ожидаемое число событий, может быть больше единицы. Если е-value маленькое, то, значит, совпадение значимое, и оно несет большую биологическую информацию. P-value — это вероятность встречи такого соответствия (не может быть больше единицы). При оценке e-value, да и вообще при любых статистических оценках, важно, какая модель лежит в основе всего этого дела. Модель, которая лежит в основе e-value, конечно же, неправильная, потому что мы не знаем правильность статистических характеристик биологических последовательностей. Е-value просто дает нам ориентир, и реально, если мы имеем е-value порядка 10– 2, то это, как правило, мусор, незначимое соответствие. Правда, есть некоторые специалисты с такой интуицией о структуре белков, которые могут работать с выравниваниями с e-value даже порядка 1. А обычно если исследователи видят e-value > 10– 3, они с этим не работают.
Есть разные модификации BLAST: BLASTp (выравнивание аминокислотных последовательностей), BLASTn (выравнивание нуклеотидных последовательностей), BLASTx (выравнивание всех возможных транслятов нашей нуклеотидной последовательности против банка аминокислотных последовательностей), TBLASTx (выравнивание всех возможных транслятов нашей нуклеотидной последовательности против всех транслятов банка нуклеотидных последовательностей). Еще нужно знать, что Nr Data Base — (non redundant) — это база, против которой обычно прогоняют BLAST, в которой нет повторяющихся последовательностей, из которой убраны дубли для того, чтобы не гонять BLAST по одним и тем же последовательностям. И score — это вес выравнивания.
А если на нашу последовательность при поиске налипло, например, не одна, а двадцать последовательностей. При этом возникает задача написать все эти последовательности друг под другом, чтобы увидеть, в какой мере они совпадают, что консервативно (устойчиво повторяется), а что нет, и как устроена наша аминокислотная последовательность. Эта задача называется
Множественное
Множественное выравнивание — это такой способ написания нескольких последовательностей друг под другом (может быть, с пропусками в каких-то позициях в разных последовательностях), чтобы в каждом столбце стояли гомологичные позиции.
Для этой задачи тоже есть «золотой стандарт». Это выравнивание, которое бы получилось, если бы мы выровняли друг под другом последовательности, которые имеют одинаковую пространственную структуру. То есть две экспериментально установленные пространственные структуры белка сопоставляем и отмечаем, какие аминокислотные остатки друг под другом встали (эти остатки соответствуют гомологичным позициям). Это — биологически обоснованное выравнивание. Возникает задача — найти способ (построить алгоритм и определить параметры), который выравнивает последовательности "золотого стандарта" (то есть последовательности, для которых пространственная структура известно) правильно. Если такой алгоритм построен, то есть надежда, что он выровняет последовательности с неизвестной пространственной структурой тоже правильно.
Для решения задачи множественного выравнивания можно попробовать написать многомерную матрицу и построить методом динамического программирования с просмотром многомерной матрицы. Тогда количество вершин будет порядка Ln, где L — длина, а n — количество последовательностей. Так как типичное количество последовательностей в семействе белков сотни, то 300 аминокислот дадут 300100 — это очень много, этот алгоритм для множественного выравнивания не подходит.
Тогда придумали метод прогрессивного выравнивания. Зная расстояния между любой парой последовательностей, мы можем построить выравнивание, определить вес выравнивания, и построить какое-то бинарное дерево. Затем мы обходим это дерево, последовательно проводя парные выравнивания наиболее близких последовательностей. Объединяем, получаем выравнивание. Соединяем суперпоследовательности, получаем следующее выравнивание. В конце концов, получаем выравнивание в корне.
Такое постепенное построение выравнивание решает задачу, которую мы не можем сформулировать математически. В биоинформатике очень часто нельзя построить математическую формулировку задачи, которую мы решаем. Поэтому формулировка задачи, которую решает алгоритм BLAST, выглядит так: мы находим то, что находит программа BLAST. Также мы не можем сказать, что мы оптимизируем при множественном выравнивании.
Одна и та же биологическая задача может приводить к разным математическим постановкам одной и той же задачи. Есть примеры, когда одна и та же задача может быть построена так, что она будет математически решаемой или математически не решаемой. Есть класс задач, для которых не существует хороших алгоритмов. Но при построении множественных выравниваний мы решаем с помощью данного алгоритма, без формулировки математической задачи.
Дальше идет задача
предсказания вторичной структуры РНК
Вторичная структура РНК — структура, образуемая спаренными основаниями на однонитевой молекуле РНК. Биологическая роль вторичной структуры: структурная (РНК — рибосомная, тРНК), регуляция (рибопереключатели, аттенюация, микроРНК), рибозимы, стабильность РНК.
На рисунке показана типичная вторичная структура РНК и разные формы представления вторичной структуры РНК: