Алгоритм Нусинова

Сорт	Прогнозирование структуры нуклеиновой кислоты
Худшая производительность	$O(n^{3})$
Наихудшая пространственная сложность	$O(n^{2})$

Алгоритм Нусинова — это алгоритм прогнозирования структуры нуклеиновой кислоты , используемый в вычислительной биологии для прогнозирования сворачивания молекулы РНК , который использует принципы динамического программирования . Алгоритм был разработан Рут Нусиновой в конце 1970-х годов.

Фон

РНК-оригами возникает, когда молекула РНК «складывается» и связывается сама с собой. Это сворачивание часто определяет функцию молекулы РНК. РНК складывается на разных уровнях, этот алгоритм предсказывает вторичную структуру РНК.

Алгоритм

Подсчет очков

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

Мотивация

Рассмотрим последовательность РНК $S$ элементы которого взяты из множества $\{A,U,C,G\}$. Представим, что у нас есть оптимальное решение подзадачи складывания $S_{i}$ к $S_{j-1}$, и оптимальное решение для складывания $S_{u}$ к $S_{v}$ $i\leq u\leq v\leq j-1$ . Теперь, чтобы выровнять $S_{i}$ к $S_{j}$, у нас есть два варианта:

1. Оставлять $S_{j}$ непарные и сохраняют структуру $S_{i}$ к $S_{j-1}$. Оценка за это выравнивание будет равна баллу за выравнивание $S_{i}$ к $S_{j-1}$, поскольку не было создано новых пар оснований.
2. Пара $S_{j}$ с $S_{k}$, где $i\leq k<j$. Оценка за это соответствие будет равна оценке пары оснований плюс оценка лучшего выравнивания $S_{i}$ к $S_{k-1}$ и $S_{k+1}$ к $S_{j-1}$.

Алгоритм

Рассмотрим последовательность РНК $S$ длины $n$ такой, что $S_{i}\in \{A,U,C,G\}$.

Построить $n\times n$ матрица $M$. Инициализировать $M$ такой, что

$M(i,i)=0$

$M(i,i-1)=0$

для $1\leq i\leq n$.

$M(i,j)$ будет содержать максимальный балл для подпоследовательности $S_{i}...S_{j}$. Теперь заполните записи $M$ вверх и вправо, так что

$M(i,j)=\max _{i\leq k<j}{\begin{cases}M(i,k-1)+M(k+1,j-1)+{\text{Score}}(S_{k},S_{j})\\M(i,j-1)\end{cases}}$

где ${\text{Score}}(S_{k},S_{j})={\begin{cases}1,&S_{k}{\text{ and }}S_{j}{\text{ complementary}}\\0,&{\text{otherwise.}}\end{cases}}$

После этого шага у нас есть матрица $M$ где $M(i,j)$ представляет собой оптимальную оценку сворачивания $S_{i}...S_{j}$.

Чтобы определить структуру свернутой РНК методом обратной трассировки, мы сначала создаем пустой список пар. $P$. Мы инициализируем с помощью $i=1,j=n$. Далее мы следуем одному из трех сценариев.

1. Если $j\leq i$, процедура останавливается.
2. Если $M(i,j)=M(i,j-1)$, затем установите $i=i,j=j-1$ и продолжить.
3. В противном случае для всех $k:i\leq k<j$, если $S_{k}$ и $S_{j}$ дополняют друг друга и $M(i,j)=M(i,k-1)+M(k+1,j-1)+1$, добавить $(k,j)$ к $P$, затем проследите оба с помощью $i=i,j=k-1$ и $i=k+1,j=j-1$.

Когда обратная трассировка завершится, $P$ содержит все парные основания.

Ограничения

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