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

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

	Базовый уровень статей Выделить только проверенную информацию
	Создать черновик

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

(статья опубликована в журнале «Автоматика и вычислительная техника» в первом номере за 2011 год, полная версия на русском, полная версия на английском, платный вариант)

С.С. Яковлев*, магистр инженерных наук, исследователь

А.Н. Борисов*, доктор технических наук, профессор

*Рижский Технический университет, Латвия

Аннотация

Ключевые слова: теория игр, сворачивание белка, NP-полная задача, третичная структура РНК

Краткое содержание

Сформулировано представление задачи в терминах теории игр

Один из способов формализовать задачу сворачивания РНК - это сформулировать её в терминах задачи принятия оптимальных решений теории игр. Эта задача может быть определена как игра с природой — игра, в которой имеется только один игрок, причем исход ее зависит не только от его решений, но и от состояния “природы”, то есть не от сознательно противодействующего противника, но от объективной, невраждебной действительности. Чтобы определить данную игру нужно задать:

Начальное и конечное состояние игры.
Функцию переходов, в виде пар (move, state), каждая из которых указывает допустимое действие и результирующее состояние.
Функцию полезности $f(x)$ , числовые значения, которые указывают на приближение к конечному состоянию. Например, в игре шахматы или крестики-нолики результатом является победа, поражение или ничья, со значениями +1, -1 или 0. Может использоваться также более широкий диапазон значений функции полезности.

Зададим необходимые параметры, описанные выше:

Начальное состояние игры ( $S_{0}$ ) – грубое приближение третичной структуры цепи РНК, полученное методом «Быстрое охлаждение» (см. следующий раздел).
Конечное состояние игры ( $S_{n}$ ) – третичная структура цепи РНК, обладающая водородными связями согласно её вторичной структуре.
Функция переходов – разработано специальное программное обеспечение RNAFoldingAI, которое позволяет для конкретного поворота RotID определенного нуклеотида NucNumber в цепи РНК рассчитать третичную структуру РНК. А именно $S_{t+1}=f(S_{t},RotID,NucNumber)$ .
Функция полезности $f(x)$ – основывается на близости нуклеотидов, которые должны образовать водородную связь. А именно $f(r,a)$ , где r – расстояние между нуклеотидами, а a – угол между донором и акцептором предполагаемой водородной связи.

Предложены два метода

Показано, что метод „X-тюнинг“ может быть альтернативой методу „МиниМакс“ в играх с противником (таких как, шахматах, крестики - нолики и т.п.)

В методе Мини-Макс необходимо построить полное дерево возможных исходов игры. Число узлов при построении дерева в игре крестики-нолики равно 2106288. Сравнительно для метода X-тюнинг за всю игру нужно просчитать 1000-2000 состояний игры в зависимости от ходов игроков. При этом первый ход не имеет предпочтений и делается случайно, а за второй ход оценивается около 1000 позиций, и соответственно, все последующие ходы занимают менее 500-1000 оценок состояний. Таким образом, метод X-тюнинг перебирает сравнительно незначительное число состояний, и на несколько порядков быстрее вычисляет ход, который должен сделать игрок. При этом, несмотря на то что варианты ходов по сравнению с методом Мини-Макс разные, метод X-тюнинг также в наихудшем случае всегда сводит игру к ничьей.

Показано, что метод „Q-обучение“ в отличии от метода „X-тюнинг“, не пригоден для использования в играх с противником

Такие игры как «крестики-нолики» также решают с помощью метода Q-обучения, в котором агент изучает энергетическую поверхность и пытается обучиться стратегии игры. Но для применения этого и многих других методов ИИ, использующих стохастический поиск, необходима стадия обучения. Во время этой стадии агент пытается изучить поверхность поиска, построить её модель в том или ином виде и распространить свои знания на неизвестную еще область – осуществляя затем прогноз. Но энергетическая поверхность в игре сильно изменяется с каждым новым ходом и является практически неповторяемой. Поэтому даже в игре «крестики-нолики» невозможно сделать обобщение и построить модель поверхности. Точнее, обобщённая модель будет почти эквивалентна полному дереву возможных состояний, которое и строится методом Мини-Макс. Таким образом, в задачах, где энергетическая поверхность меняется в зависимости от действий игроков (агентов), затраты на построение модели будут эквивалентны полному перебору или еще больше.

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

Решение методом „X-тюнинг“ задачи сворачивания РНК на примере одного рибозима

Вторичная структура фрагмента RZ+ рибозима NC_003540.

Применяя метод «Быстрое охлаждение», были получены грубые структуры фрагментов L1 и L2. Применяя метод X-тюнинг для поиска структуры фрагмента, при котором будет образована водородная связь между 14 и 22 нуклеотидом, было получено 82 удовлетворительных варианта, где водородная связь присутствует. Далее эти 82 варианта используются при получении водородной связи в следующей паре нуклеотидов. При этом получено 18 вариантов, на основании только одной из 82 вариантов, т.е. 81 вариант непригоден для одновременного наличия водородных связей между 14 и 22 нуклеотидами, и 13 и 23 нуклеотидами.

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

Для РНК основными взаимодействиями, которые определяю третичную структуру – являются наличие водородных связей. Поэтому достоверность полученных фрагментов определяется заданием условий при которых образуется водородная связь, конечно с погрешностью на то, что положение каждого отдельного нуклеотида может отличаться от данных ЯМР из-за динамичности самой молекулы. Но общая форма молекулы будет максимально соответствовать реальной, в противном бы случае невозможно было бы получить структуру, в которой промоделированы все водородные связи.

Дальнейшие исследования в этой области должны решить вопрос с построением цепей РНК из нескольких фрагментов.

Анализ

В работе содержится такая фраза:

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

Рецензентом был задан следующий интересный вопрос: „Но как здесь определить детерминированность ? Случайность используется из-за незнания состояний природы.“

Данный вопрос действительно является ключевым для данной статьи. Но в тоже время выходит далеко за рамки самой статьи, и касается скорее методологических вопросов моделирования. Кратко и обще ответить на него не представляется возможным, поэтому можно дать лишь неформальный ответ. Если отвечать в двух словах, то можно было бы сказать: „так как и было сделано в данной статье, для данной частной задачи“. Но понятно, что это не до конца проясняет вопрос. „За деревьями леса не видно“. И далее будет дан более развернутый ответ.

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

Как мы идеализировали данную задачу ? Мы определили, что если мы получим все водородные связи, которые в реальности имеет РНК - этого будет достаточно чтобы короткий фрагмент РНК приобрел свою третичную структуру. И этой идеализации нам в данном случае оказалось достаточно - визуализировав фрагмент мы увидели образованную спираль, что и имеет место быть в реальности - короткие фрагменты приобретают структуру спирали. Мы это условие ни каким образом не задавали, а ориентировались только на образование водородных связей. Получается, что РНК устроенно таким образом, что просто геометрически нет других возможностей образовать другую форму, если задаться целью образовать требуемые водородные связи. Именно поэтому мы в заключении пишем:

А теперь мы можем ответить на вопрос: что заставляет фрагмент РНК приобретать именно спиральную структуру? Из результатов эксперимента получается, что только образованная РНК-петля и последующие нуклеотиды (первичная структура) полностью предопределяют то, что данный фрагмент РНК имеет спиральную структуру.

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

Теперь как же мы формально задали детерминированность. Через определение функции полезности

f(x)

, где

x

определяет собственно выбранную идеализацию - образование водородных связей. А далее уже дело техники, создать функцию приближения:

Для формирования водородных связей имеет значение расстояние r и угол a между определёнными атомами. В зависимости от этого, для использования метода X-тюнинг мы определим 100 групп. 0-группа при r < 3.0 и a<20°, 1-группа при r < 3.1 и a<21° … 100 группа при r < 13.0 и a<120°. Большее число групп не нужно, так как при расстоянии r > 13 и a>120° вероятность образования водородной связи минимальна.

и затем применить описанные методы для поиска нужного состояния.

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

В целом от случайности нужно отказаться взамен, хоть и не имеющейся в природе, идеализации, но тем самым в ходе экспериментов узнавая (через моделирование) „движущие силы“ природы. Далее важно еще так определить функцию переходов, чтобы она была по возможности „гладкой“, т.е. чтобы можно было параллельные процессы в природе заменить моделированием последовательных переходов на компьютере.

См. также