Эволюционная теория графов

Эволюционная теория графов — область исследований, лежащая на стыке теории графов , теории вероятностей и математической биологии . Эволюционная теория графов — это подход к изучению того, как влияет на эволюцию популяции топология . То, что лежащая в основе топология может существенно повлиять на результаты эволюционного процесса, наиболее ясно видно в статье Эреза Либермана , Кристофа Хауэрта и Мартина Новака .

В эволюционной теории графов люди занимают вершины взвешенного ориентированного графа , а вес w _{i j} ребра i от вершины i до вершины j обозначает вероятность того, что заменит j . Вес соответствует биологическому понятию приспособленности , согласно которому более приспособленные типы размножаются легче. Одним из свойств, изучаемых на графах с двумя типами особей, является вероятность фиксации , которая определяется как вероятность того, что один случайно размещенный мутант типа A заменит популяцию типа B. Согласно изотермической теореме , граф имеет то же самое вероятность фиксации как соответствующий процесс Морана тогда и только тогда, когда она изотермична, поэтому сумма всех весов, ведущих в вершину, одинакова для всех вершин. Так, например, полный граф с равными весами описывает процесс Морана. Вероятность фиксации равна

${\begin{aligned}\rho _{M}={\frac {1-r^{-1}}{1-r^{-N}}}\end{aligned}}$

где r — относительная приспособленность вторгающегося типа.

Графы можно разделить на усилители отбора и подавители отбора. Если вероятность фиксации одной полезной мутации $\rho _{G}$ выше вероятности фиксации соответствующего процесса Морана $\rho _{M}$ тогда граф является усилителем, иначе – подавителем селекции. Одним из примеров подавителя выбора является линейный процесс, в котором только вершина i-1 может заменить вершину i (но не наоборот). В этом случае вероятность фиксации равна $\rho _{G}=1/N$ (где N — количество вершин), поскольку это вероятность того, что в первой вершине возникнет мутация, которая со временем заменит все остальные. С $\rho _{G}<\rho _{M}$ для всех r больше 1 этот граф по определению является подавителем выбора.

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

Также эволюционные игры можно изучать на графах, где ребро между i и j означает, что эти два человека будут играть в игру друг против друга.

Тесно связанные стохастические процессы включают модель избирателя , которая была предложена Клиффордом и Садбери (1973) и независимо Холли и Лиггеттом (1975) и которая широко изучалась.

Библиография

• Холли, РА; Лиггетт, ТМ (1975). «Эргодические теоремы для слабо взаимодействующих бесконечных систем и модели избирателя» . Анналы вероятности . 3 (4): 643–663. дои : 10.1214/aop/1176996306 .
• Лиггетт, Томас М. (1999). Стохастические взаимодействующие системы: процессы контакта, избирателя и исключения . Берлин: Шпрингер. ISBN  978-3-540-65995-2 .
• Клиффорд, П.; Садбери, А. (1973). «Модель пространственного конфликта». Биометрика . 60 (3): 581–588. дои : 10.1093/biomet/60.3.581 .
• Мартин А. Новак (2006). Эволюционная динамика: исследование уравнений жизни . Кембридж: Belknap Press издательства Гарвардского университета . ISBN  978-0-674-02338-3 .
• Монк, Т. (2018). «Мартингалы и вероятность фиксации многомерных эволюционных графов». Журнал теоретической биологии . 451 : 10–18. Бибкод : 2018JThBi.451...10M . дои : 10.1016/j.jtbi.2018.04.039 . ПМИД   29727631 . S2CID   13682722 .

Внешние ссылки

Виртуальная лаборатория для изучения эволюции на графах: [1]

Дальнейшее чтение

• Аллен, Бенджамин; Новак, Мартин А. (2014). «Игры на графах» . EMS-обзоры по математическим наукам . 1 (1): 113–151. дои : 10.4171/emss/3 .