Parameterised approximation of the fixation probability of the dominant mutation in the multi-type Moran process. (English) Zbl 07921855
Summary: The multi-type Moran process is an evolutionary process on a connected graph \(G\) in which each vertex has one of \(k\) types and, in each step, a vertex \(v\) is chosen to reproduce its type to one of its neighbours. The probability of a vertex \(v\) being chosen for reproduction is proportional to the fitness of the type of \(v\). So far, the literature was almost solely concerned with the 2-type Moran process in which each vertex is either healthy (type 0) or a mutant (type 1), and the main problem of interest has been the (approximate) computation of the so-called fixation probability, i.e., the probability that eventually all vertices are mutants. In this work we initiate the study of approximating fixation probabilities in the multi-type Moran process on general graphs. Our main result is an FPTRAS (fixed-parameter tractable randomised approximation scheme) for computing the fixation probability of the dominant mutation; the parameter is the number of types and their fitnesses. In the course of our studies we also provide novel upper bounds on the expected absorption time, i.e., the time that it takes the multi-type Moran process to reach a state in which each vertex has the same type.
MSC:
| 68Qxx | Theory of computing |
References:
| [1] | Arvind, Vikraman; Raman, Venkatesh, Approximation algorithms for some parameterized counting problems, (Bose, Prosenjit; Morin, Pat, Algorithms and Computation, 13th International Symposium. Algorithms and Computation, 13th International Symposium, ISAAC 2002 Vancouver, BC, Canada, November 21-23, 2002, Proceedings. Algorithms and Computation, 13th International Symposium. Algorithms and Computation, 13th International Symposium, ISAAC 2002 Vancouver, BC, Canada, November 21-23, 2002, Proceedings, Lecture Notes in Computer Science, vol. 2518, 2002, Springer), 453-464 · Zbl 1019.68135 |
| [2] | Beerenwinkel, Niko; Antal, Tibor; Dingli, David; Traulsen, Arne; Kinzler, Kenneth W.; Velculescu, Victor E.; Vogelstein, Bert; Nowak, Martin A., Genetic progression and the waiting time to cancer, PLoS Comput. Biol., 3, 11, e225, November 2007 |
| [3] | Chao, Brian; Schweinsberg, Jason, A spatial mutation model with increasing mutation rates, 2021, CoRR |
| [4] | Chatterjee, Krishnendu; Ibsen-Jensen, Rasmus; Nowak, Martin A., Faster Monte-Carlo algorithms for fixation probability of the Moran process on undirected graphs, (42nd International Symposium on Mathematical Foundations of Computer Science. 42nd International Symposium on Mathematical Foundations of Computer Science, LIPIcs, vol. 83, 2017, Schloss Dagstuhl - Leibniz-Zentrum für Informatik), 61:1-61:13 · Zbl 1447.92274 |
| [5] | Díaz, Josep; Goldberg, Leslie Ann; Mertzios, George B.; Richerby, David; Serna, Maria; Spirakis, Paul G., Approximating fixation probabilities in the generalized Moran process, Algorithmica, 69, 1, 78-91, May 2014 · Zbl 1303.92095 |
| [6] | Díaz, Josep; Goldberg, Leslie Ann; Richerby, David; Serna, Maria, Absorption time of the Moran process, Random Struct. Algorithms, 49, 1, 137-159, 2016 · Zbl 1344.05135 |
| [7] | Etheridge, A. M.; Griffiths, R. C., A coalescent dual process in a Moran model with genic selection, Theor. Popul. Biol., 75, 4, 320-330, 2009 · Zbl 1213.92038 |
| [8] | Ferreira, Eliza M.; Neves, Armando G. M., Fixation probabilities for the Moran process with three or more strategies: general and coupling results, J. Math. Biol., 81, 1, 277-314, July 2020 · Zbl 1437.91073 |
| [9] | Fisher, R. A., On the dominance ratio, Proc. R. Soc. Edinb., 42, 321-341, 1923 |
| [10] | Goldberg, Leslie Ann; Lapinskas, John; Richerby, David, Phase transitions of the Moran process and algorithmic consequences, Random Struct. Algorithms, 56, 3, 597-647, 2020 · Zbl 1444.92072 |
| [11] | Hajek, Bruce, Hitting-time and occupation-time bounds implied by drift analysis with applications, Adv. Appl. Probab., 14, 3, 502-525, 1982 · Zbl 0495.60094 |
| [12] | He, Jun; Yao, Xin, Drift analysis and average time complexity of evolutionary algorithms, Artif. Intell., 127, 1, 57-85, 2001 · Zbl 0971.68129 |
| [13] | Lanchier, Nicolas, Wright-Fisher and Moran models, (Lanchier, Nicolas, Stochastic Modeling. Stochastic Modeling, Universitext, 2017, Springer International Publishing), 203-218 · Zbl 1360.60002 |
| [14] | Lieberman, Erez; Hauert, Christoph; Nowak, Martin A., Evolutionary dynamics on graphs, Nature, 433, 7023, 312-316, January 2005 |
| [15] | Mitzenmacher, Michael; Upfal, Eli, Probability and Computing: Randomized Algorithms and Probabilistic Analysis, 2005, Cambridge University Press · Zbl 1092.60001 |
| [16] | Moran, P. A.P., Random processes in genetics, Math. Proc. Camb. Philos. Soc., 54, 1, 60-71, 1958 · Zbl 0091.15701 |
| [17] | Nowak, Martin A., Evolutionary Dynamics: Exploring the Equations of Life, 2006, Harvard University Press · Zbl 1115.92047 |
| [18] | Wright, Sewall, Evolution in Mendelian populations, Genetics, 16, 2, 97-159, 1931 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
