Fixation time in Moran process under strong selection
| Název práce v češtině: | Čas fixace v Moranově procesu při silné selekci |
|---|---|
| Název v anglickém jazyce: | Fixation time in Moran process under strong selection |
| Klíčová slova: | evoluční dynamika|Moranův proces|graf |
| Klíčová slova anglicky: | evolutionary dynamics|Moran process|graph |
| Akademický rok vypsání: | 2023/2024 |
| Typ práce: | diplomová práce |
| Jazyk práce: | angličtina |
| Ústav: | Informatický ústav Univerzity Karlovy (32-IUUK) |
| Vedoucí / školitel: | Bc. Josef Tkadlec, Ph.D. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 01.11.2023 |
| Datum zadání: | 15.11.2023 |
| Datum potvrzení stud. oddělením: | 15.11.2023 |
| Datum a čas obhajoby: | 14.06.2024 09:00 |
| Datum odevzdání elektronické podoby: | 02.05.2024 |
| Datum odevzdání tištěné podoby: | 02.05.2024 |
| Datum proběhlé obhajoby: | 14.06.2024 |
| Oponenti: | Krishnendu Chatterjee |
| Zásady pro vypracování |
| Moranův proces je náhodný proces, který modeluje šíření genetické mutace v populaci jedinců. Struktura populace je popsaná grafem G a síla mutace parametrem r>1 [1]. Důležitá veličina při zkoumání Moranova procesu je čas fixace, tedy střední hodnota počtu kroků, po nichž se mutace rozšíří do všech vrcholů (nebo zcela zanikne). Je známo, že čas fixace může být obecně exponenciální, ale v jistých režimech je nejvýše polynomiální (např. pokud G je neorientovaný [2,3] nebo pokud síla r je dostatečně velká [4]). Cílem práce je prozkoumat Moranův proces ve speciální limitě $r=\infty$ a dokázat silnější odhady na čas fixace pro různé třídy grafů (ne/orientované grafy, regulární grafy, DAGy). |
| Seznam odborné literatury |
| [1] Lieberman E, Hauert C, Nowak MA. Evolutionary dynamics on graphs. Nature. 2005 Jan 20;433(7023):312-6.
[2] Díaz J, Goldberg LA, Mertzios GB, Richerby D, Serna M, Spirakis PG. Approximating fixation probabilities in the generalized moran process. Algorithmica. 2014 May;69:78-91. [3] Goldberg LA, Lapinskas J, Richerby D. Phase transitions of the Moran process and algorithmic consequences. Random Structures & Algorithms. 2020 May;56(3):597-647. [4] Brewster DA, Nowak MA, Tkadlec J. Fixation times on directed graphs. arXiv preprint arXiv:2308.02762. 2023 Aug 5. |