Colonization times in Moran process on graphs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F25%3A10504424" target="_blank" >RIV/00216208:11320/25:10504424 - isvavai.cz</a>

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=heJU3QrUdV" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=heJU3QrUdV</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1371/journal.pcbi.1012868" target="_blank" >10.1371/journal.pcbi.1012868</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Colonization times in Moran process on graphs

Popis výsledku v původním jazyce

Moran Birth-death process is a standard stochastic process that is used to model natural selection in spatially structured populations. A newly occurring mutation that invades a population of residents can either fixate on the whole population or it can go extinct due to random drift. The duration of the process depends not only on the total population size n, but also on the spatial structure of the population. In this work, we consider the Moran process with a single type of individuals who invade and colonize an otherwise empty environment. Mathematically, this corresponds to the setting where the residents have zero reproduction rate, thus they never reproduce. The spatial structure is represented by a graph. We present two main contributions. First, in contrast to the Moran process in which residents do reproduce, we show that the colonization time is always at most a polynomial function of the population size n. Namely, we show that colonization always takes at most 12n3-12n2 expected steps, and for each n, we identify the slowest graph where it takes exactly that many steps. Moreover, we establish a stronger bound of roughly n2.5 steps for undirected graphs and an even stronger bound of roughly n2 steps for so-called regular graphs. Second, we discuss various complications that one faces when attempting to measure fixation times and colonization times in spatially structured populations, and we propose to measure the real duration of the process, rather than counting the steps of the classic Moran process.

Název v anglickém jazyce

Colonization times in Moran process on graphs

Popis výsledku anglicky

Moran Birth-death process is a standard stochastic process that is used to model natural selection in spatially structured populations. A newly occurring mutation that invades a population of residents can either fixate on the whole population or it can go extinct due to random drift. The duration of the process depends not only on the total population size n, but also on the spatial structure of the population. In this work, we consider the Moran process with a single type of individuals who invade and colonize an otherwise empty environment. Mathematically, this corresponds to the setting where the residents have zero reproduction rate, thus they never reproduce. The spatial structure is represented by a graph. We present two main contributions. First, in contrast to the Moran process in which residents do reproduce, we show that the colonization time is always at most a polynomial function of the population size n. Namely, we show that colonization always takes at most 12n3-12n2 expected steps, and for each n, we identify the slowest graph where it takes exactly that many steps. Moreover, we establish a stronger bound of roughly n2.5 steps for undirected graphs and an even stronger bound of roughly n2 steps for so-called regular graphs. Second, we discuss various complications that one faces when attempting to measure fixation times and colonization times in spatially structured populations, and we propose to measure the real duration of the process, rather than counting the steps of the classic Moran process.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2025

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

PLoS Computational Biology

ISSN

1553-734X

e-ISSN

1553-7358

Svazek periodika

21

Číslo periodika v rámci svazku

5

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

12

Strana od-do

e1012868

Kód UT WoS článku

001481670600002

EID výsledku v databázi Scopus

2-s2.0-105004710081