EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Fixation times on directed graphs

David A Brewster, Martin A Nowak, Josef Tkadlec iD

PLOS Computational Biology · 18.07.2024 · 20 (7) · e1012299

DOI: 10.1371/journal.pcbi.1012299 ↗

Kurz gefasst

Fachartikel in der Zeitschrift PLOS Computational Biology, online erschienen am 18.07.2024. Verfasst von David A Brewster und 2 weiteren Autor:innen. Beteiligte Einrichtung: John A. Paulson School of Engineering and Applied Sciences, Harvard University, Cambridge, Massachusetts, United States of America. Hauptthemen laut MEDLINE: Algorithms, Computational Biology. Die Arbeit wurde bisher 5-mal zitiert (Crossref) und nennt 82 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Charles Univ, Univerzita Karlova v Praze.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Schlagwörter

MeSH-Schlagwörter (MEDLINE)

AlgorithmsComputational BiologyMutationModels, GeneticComputer SimulationBiological Evolution

Autor:innen und Institutionen

  • John A. Paulson School of Engineering and Applied Sciences, Harvard University, Cambridge, Massachusetts, United States of America.
  • Department of Mathematics, Harvard University, Cambridge, Massachusetts, United States of America.
  • Department of Organismic and Evolutionary Biology, Harvard University, Cambridge, Massachusetts, United States of America.
  • Computer Science Institute, Charles University, Prague, Czech Republic.

ORCID-Profile: Josef Tkadlec

Förderung

  • Charles Univ
  • Univerzita Karlova v Praze

Zitieren

APA

Brewster, D. A., Nowak, M. A., & Tkadlec, J. (2024). Fixation times on directed graphs. PLOS Computational Biology, 20(7), e1012299. https://doi.org/10.1371/journal.pcbi.1012299

Vancouver

Brewster DA, Nowak MA, Tkadlec J. Fixation times on directed graphs. PLOS Computational Biology. 2024;20(7):e1012299. doi:10.1371/journal.pcbi.1012299

BibTeX
@article{Brewster2024,
  author = {Brewster, David A and Nowak, Martin A and Tkadlec, Josef},
  title = {Fixation times on directed graphs},
  journal = {PLOS Computational Biology},
  year = {2024},
  volume = {20},
  number = {7},
  pages = {e1012299},
  doi = {10.1371/journal.pcbi.1012299}
}
Kostenlos starten →