Вторичная структура РНК: динамическое программирование по интервалам

В задаче о рюкзаке нам удалось сформулировать алгоритм динамического про- граммирования при добавлении новой переменной. Существует и другой очень распространенный сценарий, в котором в динамическую программу добавляется переменная.
Мы начинаем с рассмотрения множества подзадач {1, 2, ..., j} для всех возможных j, но найти естественное рекуррентное отношение не удается. Тогда мы рассматриваем большее множество подзадач из {/, / + 1, ..., j} для всех возможных / и j (где / < j) и находим естественное рекуррентное отношение для этих подзадач. Таким образом, в задачу добавляется вторая переменная /; в результате рассматри- вается подзадача для каждого непрерывного интервала в {1, 2, ..., n}.

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

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Вторичная структура РНК: динамическое программирование по интервалам:

  1. СТЕРЕОТИП ДИНАМИЧЕСКИЙ
  2. ПСИХОЛОГИЯ ДИНАМИЧЕСКАЯ
  3. Иванова Г.С. Основы программирования, 2002
  4. АНАЛИЗ КАУЗАЛЬНО-ДИНАМИЧЕСКИЙ
  5. Динамическая медитация
  6. В динамических методах
  7. ПСИХИКА: ПОНИМАНИЕ ДИНАМИЧЕСКОЕ
  8. Динамический смысл аспектов
  9. ПРОЦЕСС ПСИХИЧЕСКИЙ: ХАРАКТЕРИСТИКА ДИНАМИЧЕСКАЯ
  10. О. Л. Голицына, Т. Л. Партыка, И. И. Попов. ЯЗЫКИ ПРОГРАММИРОВАНИЯ, 2008
  11. Эстетика программирования
  12. Основной курс (Программирование)
  13. Г.С.Иванова, Т.Н.Ничушкина, Е.К.Пугачев. Объектно- ориентированное программирование, 2001
  14. Часть вторая Родительское программирование
  15. 46. Динамические процессы в малой группе
  16. СОЦИОЛОГИЧЕСКИЙ АНАЛИЗ СЕМЬИ В ЕДИНСТВЕ СТРУКТУРНЫХ И ДИНАМИЧЕСКИХ КООРДИНАТ
  17. Программирование телевизионного вещания