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

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

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

Backgound [ править ]

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

Алгоритм [ править ]

Подсчет очков [ править ]

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

Мотивация [ править ]

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

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

Алгоритм [ править ]

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

Постройте матрицу . Инициализировать так , чтобы${\displaystyle n\times n}$${\displaystyle M}$${\displaystyle M}$

${\displaystyle M(i,i)=0}$

${\displaystyle M(i,i-1)=0}$

для . ${\displaystyle 1\leq i\leq n}$

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

${\displaystyle 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}}}$

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

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

Чтобы определить структуру по трассировке, мы сначала создаем пустой список пар . Инициализируем с помощью . Затем мы следуем одному из трех сценариев.${\displaystyle P}$${\displaystyle i=0,j=n}$

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

По окончании трассировки содержит все парные базы.${\displaystyle P}$

Ограничения [ править ]

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

Ссылки [ править ]