Exact numerical calculation of fixation probability and time on graphs
Exact numerical calculation of fixation probability and time on graphs
复制标题
DOI：
10.1016/j.biosystems.2016.08.010
复制
发表时间：
2016-12-01
期刊：
影响因子：
1.6
通讯作者：
Bauer, Benedikt
中科院分区：
文献类型：
--
作者：
Hindersin, Laura;Moeller, Marius;Bauer, Benedikt
图上的Moran过程是研究空间结构种群进化动力学的一种流行模型。迄今为止，只对少数几类图找到了新突变体的固定概率和时间的精确解析解。由于固定时间的变化很大，模拟是费时的，并且需要许多实现。我们提出了一种基于转移矩阵的方法对任意小图的这些量进行数值计算的算法。与模拟相比，它的优点是计算只需要执行一次。我们的算法自动构建转移矩阵。这使得不同的图形结构及其对固定概率和时间的影响的快速和交互式研究成为可能。我们提供了一个C语言的快速实现（Hindersin et al., 2016）。我们的代码非常灵活，因为它可以处理两种不同的更新机制（Birth-death或death-Birth），以及任意有向图或无向图。2016爱思唯尔爱尔兰有限公司版权所有。
The Moran process on graphs is a popular model to study the dynamics of evolution in a spatially structured population. Exact analytical solutions for the fixation probability and time of a new mutant have been found for only a few classes of graphs so far. Simulations are time-expensive and many realizations are necessary, as the variance of the fixation times is high. We present an algorithm that numerically computes these quantities for arbitrary small graphs by an approach based on the transition matrix. The advantage over simulations is that the calculation has to be executed only once. Building the transition matrix is automated by our algorithm. This enables a fast and interactive study of different graph structures and their effect on fixation probability and time. We provide a fast implementation in C with this note (Hindersin et al., 2016). Our code is very flexible, as it can handle two different update mechanisms (Birth-death or death-Birth), as well as arbitrary directed or undirected graphs. (C) 2016 Elsevier Ireland Ltd. All rights reserved.