RNAFoldingAI/Общие описание корреляционно-иерархического поиска

## Параллельный ход сворачивания


Гипотеза выше направляет сворачивание в правильную сторону, но только оно приводит к скатыванию с локальному минимуму, дальше которого сворачивание не происходит. Необходимо учесть, что идет параллельное сворачивание нуклеотидов, которое вынужденно моделируется последовательно (см. Дискуссия: Биологические аспекты сворачивания РНК ).

Вычислительные мощности позволят учесть (построить энергетическую поверхность) одновременно согласованные повороты только 2-х нуклеотидов.

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

Проводилось изучение энергетической поверхности самых коротких РНК-цепей. Например, отобрав те повороты которые наиболее выгодны для достижения минимума цепи **ga**, эти же повороты не будут способствовать достижению минимума в цепи **gaa**.

## Методы приближения к глобальному минимуму на сложной энергетической поверхности

Файл:Logo arte.jpg | Будем исходить из предположения, что глобальный минимум лежит в рамках специально отобранных локальных решений.
|


Чтобы пояснить проблематику/сложность нахождения глобального энергетического минимума, создающей цепочкой РНК рассмотрим один вырожденный пример. Возьмем последовательность из трех нуклеотидов **gaa**. Для каждого нуклеотида возможны 1526 различных поворотов. Поэтому уже для такой короткой цепочки, чтобы полностью перебрать все варианты требуется порядка 2 недель 6-процессорной машины. Полный перебор не был сделан, но частичный (были отобраны 316, 196, 116 вариантов поворотов для соответствующего нуклеотида) позволил найти энергетический минимум -13.87 (1 - №496; 2 - №939; 3 - №50).

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

### Метод „Быстрое охлаждение“

- Для каждого нуклеотида проверяем какой из поворотов дает наибольшее понижение энергии
- Выбираем тот нуклеотид и тот поворот, который максимально понизил энергию
- Фиксируем цепочку РНК, осуществляя поворот полученный в п.2.
- Повторяем процесс с п.1. пока понижение энергии не остановится

Таким образом, в рассматриваемом примере были получены следующие повороты нуклеотидов:

2 - №1541 3 - №723 1 - №2151

Это положение соответствует энергии -9.41. Как видим, оно далеко до полученного ранее энергетического минимум (-13.87). Причина этого состоит в том, что данный метод не учитывает возможные корреляции положений двух или более нуклеотидов, попав в которые только одновременно происходит понижение энергии.

### Метод „Попарная корреляция“

В отличии от метода „Быстрого охлаждения“, данный метод пытается учесть корреляции положений. Но так как уже для трех положений это требует значительных вычислительных затрат, данный метод перебирает только положения для 2 нуклеотидов (1526*1526 ≈ 2.3 млн.).

- Начинает попарный перебор с тех нуклеотидов, которые в методе „Быстрого охлаждения“ были зафиксированы первыми (в рассматриваемом примере 2-ой и 3-ий нуклеотид)
- Во время перебора находим наилучшие повороты двух нуклеотидов и их фиксируем
- Последовательно проверяем все возможные пары (в нашем случае: 1-2, 1-3 и 2-3, остальные в силу симметрии дадут тоже самое)
- Если после последней фиксации, которая дала понижение энергии, проверили все возможные пары и понижения нет, то закончить

Этот метод позволил найти локальный минимум в -10.91. Как видим он ближе к нашему глобальному, но тем не менее не достаточен.

### Метод „Иерархичная корреляция“

Итак, в методе „Попарная корреляция“ мы можем учесть только попарные корреляции. Корреляции же всех, в данном случае 3 нуклеотидов перебрать технически не можем (слишком долго). Искать случайным образом (Монте-Карло) также бесперспективно, так как вероятность попасть именно в глобальный минимум сразу делая три поворота - крайне мала. А последовательно, что показали два выше описанных метода это сделать не возможно.

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

Поэтому предлагается метод последовательной иерархической корреляции.

- Возьмем первых два нуклеотида
**ga**из последовательности**gaa**. - Для неё применим метод „Попарная корреляция“, отобрав по 100 вариантов поворотов для каждого нуклеотида, которые дают наибольшее понижение энергии
- Проведем полный перебор для последовательности
**gaa**, но с уменьшенным множеством поворотов для первых двух нуклеотидов

Таким образом, будет перебор среди вариантов 100х100х1526, что осуществляется за несколько часов.

Такой подход, позволяет найти минимум в -12.99. Такой минимум уже очень близок к глобальному. При этом оказывается, что глобальный минимум в -13.87 менее биологически правдоподобен, чем -12.99. Это следствие того, что сама функция оценки энергии достаточно приблизительна и неточна.