Алгоритм Нуссинова — один из классических динамических программных методов для предсказания вторичной структуры одноцепочечной РНК путём максимизации числа непересекающихся пар основанных на комплементарности оснований. Метод впервые описан в работах конца 1970-х годов и предназначен для получения оптимальной пары первичной последовательности при упрощённых допущениях: учитывается только количество спариваний и запрещаются псевдоузлы (пересечения нитей), что даёт детерминированную и вычислительно эффективную модель. В исходной формулировке рассматриваются стандартные комплементарные пары (A–U, G–C и иногда G–U) и минимальная разрешённая длина петли между спаренными основаниями.

Алгоритм строит матрицу динамического программирования, в которой каждая ячейка соответствует оптимальному числу пар для подотрезка последовательности между позициями i и j. Решение вычисляется рекурсивно с использованием четырёх типов переходов: пропуск левого или правого конца, объединение двух подотрезков и образование пары между концами i и j при допустимой комплементарности. После заполнения матрицы производится восстановление структуры (backtracking), формирующее множество непересекающихся дуг, соответствующих парным основаниям. Несмотря на простоту, метод служит базовой иллюстрацией подхода динамического программирования и часто используется в педагогических и исследовательских целях как исходная модель для более сложных методов.

• Цель: максимизация числа непересекающихся пар оснований в РНК-последовательности.
• Подход: динамическое программирование с матрицей размеров n×n для последовательности длины n.
• Ограничения: запрещены псевдоузлы; учитывается минимальная длина петли между спаренными основаниями.
• Комплементарность: пары формируются по заданному набору допустимых сочетаний оснований (обычно A–U, G–C, возможно G–U).
• Рекуррентные случаи: пропуски концов, разбиение на два подотрезка, спаривание концов i и j.
• Сложность по времени: в базовой реализации O(n^3) из-за проверки всех разбиений подотрезков.
• Сложность по памяти: O(n^2) для хранения матрицы DP.
• Восстановление структуры: backtracking по матрице для получения конкретного набора пар.
• Применение: учебные примеры, базовая оценка вторичной структуры и стартовая точка для расширений с энергийными моделями и учётом псевдоузлов.