Martingales and the fixation probability of high-dimensional evolutionary graphs

被引:15
作者
Monk, Travis [1 ]
机构
[1] Western Sydney Univ, MARCS Inst, Biomed Engn & Neurosci, Locked Bag 1797, Penrith, NSW 2751, Australia
关键词
Birth-death; Moran; Stochastic process; Megastar; Random walk; DYNAMICS;
D O I
10.1016/j.jtbi.2018.04.039
中图分类号
Q [生物科学];
学科分类号
07 ; 0710 ; 09 ;
摘要
A principal problem of evolutionary graph theory is to find the probability that an initial mutant population will fix on a graph, i.e. that the mutants will eventually replace the indigenous population. This problem is particularly difficult when the dimensionality of a graph is high. Martingales can yield compact and exact expressions for the fixation probability of an evolutionary graph. Crucially, the tractability of martingales does not necessarily depend on the dimensionality of a graph. We will use martingales to obtain the exact fixation probability of graphs with high dimensionality, specifically k-partite graphs (or 'circular flows') and megastars (or 'superstars'). To do so, we require that the edges of the graph permit mutants to reproduce in one direction and indigenous in the other. The resultant expressions for fixation probabilities explicitly show their dependence on the parameters that describe the graph structure, and on the starting position(s) of the initial mutant population. In particular, we will investigate the effect of funneling on the fixation probability of k-partite graphs, as well as the effect of placing an initial mutant in different partitions. These are the first exact and explicit results reported for the fixation probability of evolutionary graphs with dimensionality greater than 2, that are valid over all parameter space. It might be possible to extend these results to obtain fixation probabilities of high-dimensional evolutionary graphs with undirected or directed connections. Martingales are a formidable theoretical tool that can solve fundamental problems in evolutionary graph theory, often within a few lines of straightforward mathematics. (C) 2018 Elsevier Ltd. All rights reserved.
引用
收藏
页码:10 / 18
页数:9
相关论文
共 50 条
[41]   Housing price spillovers in China: A high-dimensional generalized VAR approach [J].
Yang, Jian ;
Yu, Ziliang ;
Deng, Yongheng .
REGIONAL SCIENCE AND URBAN ECONOMICS, 2018, 68 :98-114
[42]   High-dimensional encoding of movement by single neurons in basal ganglia output [J].
Zur, Gil ;
Larry, Noga ;
Cain, Matan ;
Lixenberg, Adi ;
Yarkoni, Merav ;
Behling, Stuart ;
Joshua, Mati .
ISCIENCE, 2024, 27 (09)
[43]   The Role of High-Dimensional Diffusive Search, Stabilization, and Frustration in Protein Folding [J].
Rimratchada, Supreecha ;
McLeish, Tom C. B. ;
Radford, Sheena E. ;
Paci, Emanuele .
BIOPHYSICAL JOURNAL, 2014, 106 (08) :1729-1740
[44]   A scalable approach to the computation of invariant measures for high-dimensional Markovian systems [J].
Gerber, Susanne ;
Olsson, Simon ;
Noe, Frank ;
Horenko, Illia .
SCIENTIFIC REPORTS, 2018, 8
[45]   Edge manifold as a Lagrangian coherent structure in a high-dimensional state space [J].
Beneitez, Miguel ;
Duguet, Yohann ;
Schlatter, Philipp ;
Henningson, Dan S. .
PHYSICAL REVIEW RESEARCH, 2020, 2 (03)
[46]   DataHigh: graphical user interface for visualizing and interacting with high-dimensional neural activity [J].
Cowley, Benjamin R. ;
Kaufman, Matthew T. ;
Butler, Zachary S. ;
Churchland, Mark M. ;
Ryu, Stephen I. ;
Shenoy, Krishna V. ;
Yu, Byron M. .
JOURNAL OF NEURAL ENGINEERING, 2013, 10 (06)
[47]   Detecting high-dimensional determinism in time series with application to human movement data [J].
Ramdani, Sofiane ;
Bouchara, Frederic ;
Caron, Olivier .
NONLINEAR ANALYSIS-REAL WORLD APPLICATIONS, 2012, 13 (04) :1891-1903
[48]   Experimental investigation of high-dimensional quantum key distribution protocols with twisted photons [J].
Bouchard, Frederic ;
Heshami, Khabat ;
England, Duncan ;
Fickler, Robert ;
Boyd, Robert W. ;
Englert, Berthold-Georg ;
Sanchez-Soto, Luis L. ;
Karimi, Ebrahim .
QUANTUM, 2018, 2
[49]   Single cell proteomics in biomedicine: High-dimensional data acquisition, visualization, and analysis [J].
Su, Yapeng ;
Shi, Qihui ;
Wei, Wei .
PROTEOMICS, 2017, 17 (3-4)
[50]   Diffusion maps for high-dimensional single-cell analysis of differentiation data [J].
Haghverdi, Laleh ;
Buettner, Florian ;
Theis, Fabian J. .
BIOINFORMATICS, 2015, 31 (18) :2989-2998