Fixation times on directed graphs
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F24%3A10486575" target="_blank" >RIV/00216208:11320/24:10486575 - isvavai.cz</a>
Výsledek na webu
<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=nfFzEd.867" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=nfFzEd.867</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1371/journal.pcbi.1012299" target="_blank" >10.1371/journal.pcbi.1012299</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Fixation times on directed graphs
Popis výsledku v původním jazyce
Computing the rate of evolution in spatially structured populations is difficult. A key quantity is the fixation time of a single mutant with relative reproduction rate r which invades a population of residents. We say that the fixation time is "fast" if it is at most a polynomial function in terms of the population size N. Here we study fixation times of advantageous mutants (r > 1) and neutral mutants (r = 1) on directed graphs, which are those graphs that have at least some one-way connections. We obtain three main results. First, we prove that for any directed graph the fixation time is fast, provided that r is sufficiently large. Second, we construct an efficient algorithm that gives an upper bound for the fixation time for any graph and any r >= 1. Third, we identify a broad class of directed graphs with fast fixation times for any r >= 1. This class includes previously studied amplifiers of selection, such as Superstars and Metafunnels. We also show that on some graphs the fixation time is not a monotonically declining function of r; in particular, neutral fixation can occur faster than fixation for small selective advantages.
Název v anglickém jazyce
Fixation times on directed graphs
Popis výsledku anglicky
Computing the rate of evolution in spatially structured populations is difficult. A key quantity is the fixation time of a single mutant with relative reproduction rate r which invades a population of residents. We say that the fixation time is "fast" if it is at most a polynomial function in terms of the population size N. Here we study fixation times of advantageous mutants (r > 1) and neutral mutants (r = 1) on directed graphs, which are those graphs that have at least some one-way connections. We obtain three main results. First, we prove that for any directed graph the fixation time is fast, provided that r is sufficiently large. Second, we construct an efficient algorithm that gives an upper bound for the fixation time for any graph and any r >= 1. Third, we identify a broad class of directed graphs with fast fixation times for any r >= 1. This class includes previously studied amplifiers of selection, such as Superstars and Metafunnels. We also show that on some graphs the fixation time is not a monotonically declining function of r; in particular, neutral fixation can occur faster than fixation for small selective advantages.
Klasifikace
Druh
J<sub>imp</sub> - Č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)
Návaznosti výsledku
Projekt
—
Návaznosti
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Ostatní
Rok uplatnění
2024
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ů
Údaje specifické pro druh výsledku
Název periodika
PLoS Computational Biology
ISSN
1553-734X
e-ISSN
1553-7358
Svazek periodika
20
Číslo periodika v rámci svazku
7
Stát vydavatele periodika
US - Spojené státy americké
Počet stran výsledku
15
Strana od-do
e1012299
Kód UT WoS článku
001273204600001
EID výsledku v databázi Scopus
2-s2.0-85198928512