Fixation times on directed graphs

Result code in 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>

Result on the web

<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>

Result language

angličtina

Original language name

Fixation times on directed graphs

Original language description

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 &quot;fast&quot; if it is at most a polynomial function in terms of the population size N. Here we study fixation times of advantageous mutants (r &gt; 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 &gt;= 1. Third, we identify a broad class of directed graphs with fast fixation times for any r &gt;= 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.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

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

Project

—

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2024

Confidentiality

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

Name of the periodical

PLoS Computational Biology

ISSN

1553-734X

e-ISSN

1553-7358

Volume of the periodical

20

Issue of the periodical within the volume

7

Country of publishing house

US - UNITED STATES

Number of pages

15

Pages from-to

e1012299

UT code for WoS article

001273204600001

EID of the result in the Scopus database

2-s2.0-85198928512