Что компьютеры не расскажут об экологической и эволюционной динамике

В статье, опубликованной на этой неделе в Proceedings of the National Academy of Sciences, Расмус Ибсен-Йенсен, постдок в Институте науки и технологий Австрии (IST Austria), вместе с профессором IST Austria Кришненду Чаттерджи и профессором Мартином А. Новаком из Гарвардского университета обнаружили неожиданные связи между информатикой и биологией.

Авторы применили хорошо определённые классы сложности из теории сложности вычислений к фундаментальным вопросам биологии: экологической и эволюционной динамике в структурированных популяциях. Эти вопросы изучают, как структура популяции влияет на исход эволюционного процесса.

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

Исследователи неожиданно доказали, что эти фундаментальные вопросы в экологии и эволюции могут быть точно охарактеризованы специфическими классами сложности, как если бы эти эволюционные процессы имитировали аспекты вычислений. Определив точный класс сложности, они формально доказали, что эти вопросы не могут быть решены с помощью простой формулы.

Однако авторы также продемонстрировали, что две классические проблемы действительно эффективно разрешимы:

1. Молекулярные часы — скорость, с которой нейтральные мутации накапливаются со временем.
2. Точная вероятность фиксации генетического варианта в случае хорошо смешанной структуры популяции.

Авторы использовали установленные методы теории вычислительной сложности, применив их к определённым эволюционным сценариям в эволюционной теории игр и эволюционной теории графов. В результате они смогли вывести точный класс сложности для каждого из этих исследовательских вопросов. Конкретный класс сложности, в свою очередь, может сказать нам, существует ли эффективный алгоритм.

• Класс P содержит задачи, которые можно решить за полиномиальное время (например, с помощью простой формулы).
• Класс NP содержит задачи, для которых решение можно проверить за полиномиальное время.
• Вопрос, равны ли классы P и NP, является одной из нерешённых проблем тысячелетия. Широко распространено мнение, что P ≠ NP, а значит, самые сложные задачи в NP не могут быть решены простой формулой.

Результаты исследования — первый шаг к установлению связи между информатикой и биологией. Они также предполагают, что исследования по определённым вопросам экологической и эволюционной динамики должны сосредоточиться на тех аспектах, которые могут быть решены с помощью простой формулы.