Shakarian Paulo, Roos Patrick, Moores Geoffrey
Network Science Center and Department of Electrical Engineering and Computer Science, United States Military Academy, West Point, NY 10996, United States.
Biosystems. 2013 Feb;111(2):136-44. doi: 10.1016/j.biosystems.2013.01.006. Epub 2013 Jan 23.
Evolutionary graph theory studies the evolutionary dynamics of populations structured on graphs. A central problem is determining the probability that a small number of mutants overtake a population. Currently, Monte Carlo simulations are used for estimating such fixation probabilities on general directed graphs, since no good analytical methods exist. In this paper, we introduce a novel deterministic framework for computing fixation probabilities for strongly connected, directed, weighted evolutionary graphs under neutral drift. We show how this framework can also be used to calculate the expected number of mutants at a given time step (even if we relax the assumption that the graph is strongly connected), how it can extend to other related models (e.g. voter model), how our framework can provide non-trivial bounds for fixation probability in the case of an advantageous mutant, and how it can be used to find a non-trivial lower bound on the mean time to fixation. We provide various experimental results determining fixation probabilities and expected number of mutants on different graphs. Among these, we show that our method consistently outperforms Monte Carlo simulations in speed by several orders of magnitude. Finally we show how our approach can provide insight into synaptic competition in neurology.
进化图论研究在图结构上构建的种群的进化动态。一个核心问题是确定少量突变体取代种群的概率。目前，由于不存在好的解析方法，蒙特卡罗模拟被用于估计一般有向图上的这种固定概率。在本文中，我们引入了一个新颖的确定性框架，用于计算在中性漂移下强连通、有向、加权进化图的固定概率。我们展示了这个框架如何还能用于计算给定时间步的突变体预期数量（即使我们放宽图是强连通的假设），它如何能扩展到其他相关模型（例如选民模型），在有利突变体的情况下我们的框架如何能为固定概率提供非平凡的界，以及它如何能用于找到固定平均时间的非平凡下界。我们提供了各种实验结果，确定不同图上的固定概率和突变体预期数量。其中，我们表明我们的方法在速度上始终比蒙特卡罗模拟高出几个数量级。最后，我们展示了我们的方法如何能为神经学中的突触竞争提供见解。
