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 条
  • [1] Martingales and fixation probabilities of evolutionary graphs
    Monk, T.
    Green, P.
    Paulin, M.
    PROCEEDINGS OF THE ROYAL SOCIETY A-MATHEMATICAL PHYSICAL AND ENGINEERING SCIENCES, 2014, 470 (2165):
  • [2] Martingales and the fixation time of evolutionary graphs with arbitrary dimensionality
    Monk, Travis
    van Schaik, Andre
    ROYAL SOCIETY OPEN SCIENCE, 2022, 9 (05):
  • [3] On the expected l∞-norm of high-dimensional martingales
    Harvey, Nicholas J. A.
    Liaw, Christopher
    Portella, Victor S.
    STOCHASTIC PROCESSES AND THEIR APPLICATIONS, 2025, 183
  • [4] Exact results for fixation probability of bithermal evolutionary graphs
    Houchmandzadeh, Bahram
    Vallade, Marcel
    BIOSYSTEMS, 2013, 112 (01) : 49 - 54
  • [5] Percolation on High-Dimensional Product Graphs
    Diskin, Sahar
    Erde, Joshua
    Kang, Mihyun
    Krivelevich, Michael
    RANDOM STRUCTURES & ALGORITHMS, 2025, 66 (01)
  • [6] Bayesian inference for high-dimensional decomposable graphs
    Lee, Kyoungjae
    Cao, Xuan
    ELECTRONIC JOURNAL OF STATISTICS, 2021, 15 (01): : 1549 - 1582
  • [7] Cliques in high-dimensional random geometric graphs
    Avrachenkov, Konstantin E.
    Bobu, Andrei V.
    APPLIED NETWORK SCIENCE, 2020, 5 (01)
  • [8] Percolation on irregular high-dimensional product graphs
    Diskin, Sahar
    Erde, Joshua
    Kang, Mihyun
    Krivelevich, Michael
    COMBINATORICS PROBABILITY AND COMPUTING, 2024, 33 (03) : 377 - 403
  • [9] Testing for High-Dimensional Geometry in Random Graphs
    Bubeck, Sebastien
    Ding, Jian
    Eldan, Ronen
    Racz, Miklos Z.
    RANDOM STRUCTURES & ALGORITHMS, 2016, 49 (03) : 503 - 532
  • [10] Interactive High-Dimensional Visualization of Social Graphs
    Wakita, Ken
    Takami, Masanori
    Hosobe, Hiroshi
    2015 IEEE PACIFIC VISUALIZATION SYMPOSIUM (PACIFICVIS), 2015, : 303 - 310