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

Материал из Викиверситета
Перейти к навигации Перейти к поиску
Fairytale down blue.png
Здесь должна быть только подтвержденная информация

Перейти на базовый уровень

  • Целенаправленный поиск в задаче сворачивания третичной структуры РНК
(статья опубликована в журнале «Автоматика и вычислительная техника» в первом номере за 2011 год, полная версия на русском, полная версия на английском, платный вариант)
С.С. Яковлев*, магистр инженерных наук, исследователь
А.Н. Борисов*, доктор технических наук, профессор
*Рижский Технический университет, Латвия
Аннотация

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

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

Краткое содержание[править]

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

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

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

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

  1. Начальное состояние игры () – грубое приближение третичной структуры цепи РНК, полученное методом «Быстрое охлаждение» (см. следующий раздел).
  2. Конечное состояние игры () – третичная структура цепи РНК, обладающая водородными связями согласно её вторичной структуре.
  3. Функция переходов – разработано специальное программное обеспечение RNAFoldingAI, которое позволяет для конкретного поворота RotID определенного нуклеотида NucNumber в цепи РНК рассчитать третичную структуру РНК. А именно .
  4. Функция полезности – основывается на близости нуклеотидов, которые должны образовать водородную связь. А именно , где 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. Приемлемость решения оценивается заданным конечным состоянием игры, а именно образованием всех необходимых водородных связей. При сложных энергетических поверхностях автоматически гарантировать получение приемлемых решений нельзя, так как узким место является образование петли РНК, участка, где нет водородных связей. Но для небольших фрагментов РНК экспериментальная проверка показала, что удовлетворяющие решения находятся, и последующие образование спирали РНК с водородными связями позволяет получить большое число конечных структур молекулы (для последующих пар получается все большое число удовлетворительных состояний).

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

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