Fixation time in Moran process under strong selection
| Thesis title in Czech: | Čas fixace v Moranově procesu při silné selekci |
|---|---|
| Thesis title in English: | Fixation time in Moran process under strong selection |
| Key words: | evoluční dynamika|Moranův proces|graf |
| English key words: | evolutionary dynamics|Moran process|graph |
| Academic year of topic announcement: | 2023/2024 |
| Thesis type: | diploma thesis |
| Thesis language: | angličtina |
| Department: | Computer Science Institute of Charles University (32-IUUK) |
| Supervisor: | Bc. Josef Tkadlec, Ph.D. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 01.11.2023 |
| Date of assignment: | 15.11.2023 |
| Confirmed by Study dept. on: | 15.11.2023 |
| Date and time of defence: | 14.06.2024 09:00 |
| Date of electronic submission: | 02.05.2024 |
| Date of submission of printed version: | 02.05.2024 |
| Date of proceeded defence: | 14.06.2024 |
| Opponents: | Krishnendu Chatterjee |
| Guidelines |
| 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). |
| References |
| [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. |