Интернет-журнал "Домашняя лаборатория", 2008 №5

Для этой задачи тоже есть «золотой стандарт». Это выравнивание, которое бы получилось, если бы мы выровняли друг под другом последовательности, которые имеют одинаковую пространственную структуру. То есть две экспериментально установленные пространственные структуры белка сопоставляем и отмечаем, какие аминокислотные остатки друг под другом встали (эти остатки соответствуют гомологичным позициям). Это — биологически обоснованное выравнивание. Возникает задача — найти способ (построить алгоритм и определить параметры), который выравнивает последовательности "золотого стандарта" (то есть последовательности, для которых пространственная структура известно) правильно. Если такой алгоритм построен, то есть надежда, что он выровняет последовательности с неизвестной пространственной структурой тоже правильно.

Для решения задачи множественного выравнивания можно попробовать написать многомерную матрицу и построить методом динамического программирования с просмотром многомерной матрицы. Тогда количество вершин будет порядка Lⁿ, где L — длина, а n — количество последовательностей. Так как типичное количество последовательностей в семействе белков сотни, то 300 аминокислот дадут 300¹⁰⁰ — это очень много, этот алгоритм для множественного выравнивания не подходит.

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

Такое постепенное построение выравнивание решает задачу, которую мы не можем сформулировать математически. В биоинформатике очень часто нельзя построить математическую формулировку задачи, которую мы решаем. Поэтому формулировка задачи, которую решает алгоритм BLAST, выглядит так: мы находим то, что находит программа BLAST. Также мы не можем сказать, что мы оптимизируем при множественном выравнивании.

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

Дальше идет задача

предсказания вторичной структуры РНК

Вторичная структура РНК — структура, образуемая спаренными основаниями на однонитевой молекуле РНК. Биологическая роль вторичной структуры: структурная (РНК — рибосомная, тРНК), регуляция (рибопереключатели, аттенюация, микроРНК), рибозимы, стабильность РНК.

На рисунке показана типичная вторичная структура РНК и разные формы представления вторичной структуры РНК:

Вся РНК состоит из петель и спиралей (указано на рисунке). Петли бывают следующих типов: шпилька, внутренняя, выпячивание, множественная, псевдоузел. Так вот, возникает задача установить, кто с кем спарен. Биологическая формулировка этой задачи звучит так: дана последовательность РНК, определить ее правильную вторичную структуру. «Золотой стандарт» — тРНК и рРНК. Количество возможных вторичных структур очень велико. Задачу можно сформулировать таким образом (законным с точки зрения физики): надо минимизировать энергию, по скольку правильная вторичная структура наиболее стабильная. На самом деле, с точки зрения биологии это не совсем верно, но формулировка очень удобная с точки зрения физики и математики. Далее вопрос, что оптимизировать и как оптимизировать.

Предположим, что мы не будем минимизировать усилия по поиску, а все переберем. Построим такой граф, в котором вершины — потенциальные спирали, а ребра проводятся, если две потенциальные спирали в вершинах совместимы (то есть, если две спирали могут одновременно существовать в данной молекуле РНК).

Тогда вторичной структурой будет любой полный подграф, то есть такой граф, в котором все вершины между собой соединены — называется "клика". Тогда задача такова: в таком графе найти клику. Клика будет соответствовать хорошей структуре.

Но, к сожалению, задача поиска клики в графе является математически плохой — для нее, скорее всего, не существует эффективного алгоритма ее решения (кроме полного перебора всех вариантов).

Если мы fgh уберем, то получим клику, некую вторичную структуру. Можем получить и другую клику.