Экология и эволюция через алгоритмический объектив

27

Изучение экологии и эволюции становится все более математическим, но большинство теоретических инструментов, похоже, исходит от физики. Однако во многих случаях проблемы носят весьма дискретный характер (см., Например, SLBS00 ) и могут быть полезны с точки зрения информатики . Тем не менее, я знаю только несколько серьезных результатов от TCS, которые пытаются коснуться конкретных вопросов в области экологии и эволюции. На ум приходят два направления:

  1. Ливнат А., Пападимитриу С., Душо Дж. И Фельдман М.В. [2008] «Теория смешиваемости роли секса в эволюции» PNAS 105 (50): 19803-19808. [ pdf ]

  2. Valiant, LG [2009] "Evolvability" Журнал ACM 56 (1): 3.

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

Есть ли еще результаты в этих венах? Являются ли их другие глубокие / нетривиальные приложения теоретической информатики для понимания экологии и эволюции, как ее изучают биологи?


Заметки

  • Меня не интересуют результаты общих генетических или эволюционных алгоритмов. Хотя это очень интересная и захватывающая часть информатики, ее связь с эволюцией, изучаемой биологами, часто поверхностна. Иногда (как в LPDF08) устанавливаются конкретные соединения, но большинство стандартных результатов не представляют биологического интереса, и поэтому я не заинтересован в них в этом посте.

  • Биоинформатика - это близлежащая область, но это также не то, что я ищу. Хотя его можно использовать для реконструкции таких вещей, как филогенетические деревья и, таким образом, для содействия эволюции / экологии, теоретические аспекты КС не занимают центральное место. Здесь результаты КС, по-видимому, в основном совершенствуют инструмент, который можно использовать в основном в качестве черного ящика в рамках существующих устоявшихся теорий, а не для создания или расширения новых биологических теорий.

  • Я предпочитаю результаты, которые используют современные и нетривиальные аспекты информатики, чтобы влиять на биологию на теоретическом (но все же актуальном для биологов) уровне. Таким образом, меня не так интересуют такие вещи, как метабиология Чейтина .

Смежные вопросы

Артем Казнатчеев
источник
4
Исследование Тани Бергер-Вольф по вычислительной биологии популяций может быть актуальным здесь.
Джефф
2
@vzn, как это связано с теоретической информатикой? Любая из этих идей использует TCS нетривиальным способом? Я не прошу вводный курс по биологии, но о влиянии теоретического мышления на экологию и эволюцию.
Артем Казнатчеев
1
Возможно, несколько уместно: связь между клетками в многоклеточном организме с точки зрения теории распределенных вычислений - см., Например, этот доклад Ювала Эмека .
Юкка Суомела

Ответы:

4

Хммм. Что касается эволюционной теории динамики / игры, то, по моему личному мнению, упомянутая вами статья Livnat et al., Хотя и очень хорошая работа, похоже, не выходит за пределы стандартного математического подхода к теории эволюционных игр (см., Например, работу Группа Мартина Новака , например, статья 05 года «Эволюционная динамика на графах» ).

Итак, две претензии, которые я хотел бы сделать: во-первых, хотя это и есть какая-то отличная работа в Evolutionary Dynamics, которая, как оказалось, выполняется компьютерными учеными, я бы не стал помещать ее в теоретическую информатику или как все, что тесно связано с TCS, кроме для существовавших ранее отношений между эволюционной и алгоритмической теорией игр. Во-вторых, если вы склонны не соглашаться, то вы можете быть удивлены, насколько область философии Evolutionary Dynamics уже разделяет / разделяет с TCS (но я все еще не уверен, что методы схожи).

В целом, я хотел бы сказать, что нет никакой работы в этом направлении, включая упомянутое вами упоминание, которое бы соответствовало тому, что вы, похоже, ищете, что, я думаю, является глубокой связью между некоторой основной концепцией / техникой в ​​TCS. и изучение эволюции. (Конечно, если у кого-то другое мнение, скажите, пожалуйста!)

Я действительно думаю, что эволюционная теория игр или эволюционная динамика могли бы выиграть от более алгоритмических подходов (таких как Livnat et al). Для конкретного примера я вижу возможные хорошие расширения для рассмотрения развивающихся агентов с (ограниченными) вычислительными способностями, смоделированными, например, конечными автоматами. Это позволило бы нам изучить эволюцию дискретных агентов с более сложными условными стратегиями, такими как «синица за зубом». Я немного разбирался в этом и слышал о некоторых предварительных работах в этом направлении, но у меня нет ссылок на ссылки.

Но даже этот пример является довольно простым приложением, поэтому результаты такого рода, вероятно, все еще не ответят на ваш вопрос.

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

(Изменить) Одна потенциальная связь, которую следует упомянуть, - это известная взаимосвязь обучения (например, «проблема эксперта») и сближения с равновесием в повторяющихся играх. В частности, например (подробности см. В комментарии Аарона Рота), если в повторяющейся игре все игроки играют в стратегии без сожаления, то распределение действий в прошлом сходится к грубому коррелированному равновесию игры в один раунд. Может быть что-то интересное и новое, что можно сказать об этом, если смотреть сквозь призму теории эволюционной игры; Я не уверен.

усул
источник
2
Спасибо за ваши мысли, но это не ответ. Я полностью осведомлен (как я упоминаю во втором предложении) о таких группах, как Новак, которые полагаются главным образом на инструменты, вдохновленные физикой. Вопрос не в том, могут ли быть какие-либо связи (как я уже знаю), или в том, преследует ли их большинство (как я уже знаю, нет), а в том, что касается ранних шагов, предпринятых людьми с точки зрения TCS. ,
Артем Казнатчеев
Хорошо, ну, я пытался ответить отрицательно (насколько эволюционная динамика идет) как можно лучше.
usul
Также меня сейчас немного смущает вопрос, считаете ли вы, что Ливнат и др. Является положительным ответом на ваш собственный вопрос, или нет? (Кроме того, это удивительный / интересный вопрос, и я надеюсь, что вы получите намного больше / лучшие ответы!)
usul
1
LPDF08 и более поздняя последующая работа являются положительными примерами, как и работа Valiant и последующие действия. Однако я исключаю их из ответов просто потому, что уже знаком с ними.
Артем Казнатчеев
3
Быстрый выбор гниды: согласно стандартному представлению о сожалении, эмпирическая история игры без сожалений сходится только к набору «грубых» коррелированных равновесий в общих играх. Более сильное понятие «внутреннего» или «обменного» сожаления необходимо, чтобы сходиться к набору коррелированных равновесий. Обычная игра без сожалений сходится к равновесию Нэша в играх с нулевой суммой. Это может быть более уместным для эволюционных представлений - коррелированные равновесия нуждаются в коррелирующем устройстве для реализации, и неясно, что это будет в контексте эволюции.
Аарон Рот
3

Одно (недавнее) направление работы, касающееся бесполой эволюции, с приложениями к дизайну наркотиков и с использованием интересных методов цепей Маркова: Эволюция без секса

анонимный
источник
2

Вот новая заметная статья, связывающая эволюцию / генетику с алгоритмом Multiplicative Weight Update, также только что профилированная фондом Simons, и включает в себя соавтора, процитированного в вопросе (Papadimitriou):

  • Алгоритмы, игры и эволюция Эрик Честейн, Ади Ливнат, Христос Пападимитриу и Умеш Вазирани

    Даже самые опытные ученики эволюции, начиная с самого Дарвина, иногда выражали удивление, что механизм естественного отбора произвел всю Жизнь, какой мы ее видим вокруг себя. Существует вычислительный способ сформулировать то же изумление: «Какой алгоритм мог бы достичь всего этого всего за три с половиной миллиарда лет?». В этой статье мы предлагаем ответ: мы демонстрируем, что в режиме слабого отбора стандарт Уравнения популяционной генетики, описывающие естественный отбор в присутствии пола, становятся идентичными уравнениям повторяющейся игры между генами, в которую играют согласно мультипликативным обновлениям веса (MWUA), алгоритм, известный в информатике как удивительно мощный и универсальный. MWUA максимизирует компромисс между совокупной производительностью и энтропией,

ВЗН
источник
0

Недавний широкомасштабный опрос Миши Громова « Кристаллы, белки, стабильность и изопериметрия» (Bull. Amer. Math. Soc. 48 (2011), 229-257) представляет собой богатую тему математических тем, связанных с биологией (включая множество тем, связанных с TCS). методы).

Вопрос задан для перечисления

Результаты, которые используют современные и нетривиальные аспекты информатики […] очень дискретного характера [...] через алгоритмический объектив

Опрос Громова больше ориентирован на общие математические вопросы, чем на конкретные исследовательские программы. Таким образом, опрос может быть прочитан как выбор Громова

Вопросы, которые (потенциально) используют современные и нетривиальные аспекты компьютерной науки […] (многие из которых) носят весьма дискретный характер [...] через (что часто) алгоритмический объектив.

В качестве списка вопросов без ответа, а не списка известных результатов, статья Громова предъявляет значительные творческие требования к читателю.

Возможно, главное достоинство статьи в том, что автором является ... Миша Громов !

Джон Сидлес
источник
1
Это классная статья, но я не понимаю, как она связана с эволюцией и экологией. Есть несколько преходящих ссылок на эволюцию (наиболее заметно в разделах 4 и 6, где утверждается, что эволюция должна способствовать симметрии). Там нет абсолютно никакого упоминания об экологии. Кроме того, хотя это хорошая математическая обработка, я не вижу алгоритмического или вычислительного внимания. Можете ли вы расширить свой ответ, чтобы объяснить актуальность этой статьи для рассмотрения эволюции и экологии через алгоритмический объектив? В противном случае это лучше подходит для комментариев, а не для ответа.
Артем Казнатчеев
@Artem, ответ был расширен по запросу. Спасибо Артём.
Джон Сидлес
-2

увы, здесь, кажется, существует огромный разрыв в научном интересе / значении по сравнению с реальным научным исследованием, что также подтверждается высоким голосом по этому вопросу и низким голосами за ответы (и не ожидаем, что это будет игнорироваться). Похоже, что это очень важная учебная / исследовательская программа, лежащая в основе научной теории в ее раннем детстве. Теперь у нас есть инструменты для проведения вычислительных экспериментов, которые могут подвергнуть теорию эволюции ограничениям фальсифицируемости, по крайней мере, в том смысле, что, если эволюционная теория точна, то должна быть возможность моделировать / моделировать ее хотя бы приблизительно на компьютере; но, похоже, очень мало попыток проекта (что, безусловно, чрезвычайно амбициозно, если не сказать больше).

например, существует ли какое-либо моделирование, которое соответствует известным эволюционным изменениям в филогенетическом дереве за миллиарды лет? проблема междисциплинарная и сквозная, и она, кажется, не вписывается точно / точно в существующие научные области / границы. Примечательно, что, похоже, нет даже крупных ученых или биологов, явно предлагающих такую ​​исследовательскую программу.

Вот несколько других ссылок, которые, конечно, не будут вписываться строго в узкие критерии, изложенные в вопросе, но могут быть примерно такими:

  • в области «искусственной жизни» есть некоторый интерес к попыткам смоделировать условия, которые привели к самоорганизации «химического супа» в некие квази-жизненные формы, которые показывают основные аспекты репликации и так далее. Например: EVOGRID: подход к вычислительным истокам жизни. Damer

    Стремление понять механизмы происхождения жизни на Земле может быть усилено компьютерным моделированием вероятных стадий возникновения жизни из неживой на молекулярном уровне. Этот класс моделирования может затем поддерживать тестирование и валидацию посредством параллельных лабораторных химических экспериментов. Эту комбинацию вычислительного или «кибер» компонента и исследования параллельных усилий в химическом абиогенезе можно назвать подходом кибербиогенеза. Основная технологическая задача в области кибербиогенеза заключается в разработке компьютерных имитационных моделей, позволяющих de novo создавать пребиотические и биологические виртуальные молекулярные структуры и процессы через множество порогов сложности. Этот тезис берет на себя задачу разработки, реализации и анализа одной из таких имитационных моделей.

  • МОДЕЛЬ ОТБОРА ГРУПП ТЕРРИТОРИАЛЬНОЙ ВОЙНЫ, КСЕНОФОБИИ И АЛЬТРУИЗМА У ЧЕЛОВЕКА И ДРУГИХ ПРАМАТОВ Агнер Фог

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

  • Примечательно, что вопрос кажется очень похожим на: компьютерное моделирование процесса эволюции на Земле, датирующееся 2008 годом, по переполнению стека с некоторыми ошибками.

ВЗН
источник
обратите внимание, что проект «происхождение жизни» на самом деле пытается симулировать «эволюцию» с очень исконным происхождением, то есть до стадии ДНК , поэтому в некоторых отношениях можно утверждать, что он на самом деле является «
предбиологией