Resident fitness computation in linear time and other algorithmic aspects of interacting trajectories
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911589804802048 |
|---|---|
| author | Friedl, Katalin Nemkin, Viktória Tóbiás, András |
| author_facet | Friedl, Katalin Nemkin, Viktória Tóbiás, András |
| contents | Systems of interacting trajectories were recently studied in~\cite{HGSTW24}. Such a system of $[0,1]$-valued piecewise linear trajectories arises as a scaling limit of the system of logarithmic subpopulation sizes in a population-genetic model (more precisely, a Moran model) with mutation and selection. By definition, the resident fitness is initially 0 and afterwards it increases by the ultimate slope of each trajectory that reaches height 1.
We show that although the interaction of $n$ trajectories may yield $Ω(n^2)$ slope changes in total, the resident fitness function can be computed algorithmically in $O(n)$ time. Our algorithm uses the so-called continued lines representation of the system of interacting trajectories. In the special case of Poissonian interacting trajectories where the birth times of the trajectories form a Poisson process and the initial slopes are random and i.i.d., we provide a linear bound on the expected total number of slope changes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_11561 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Resident fitness computation in linear time and other algorithmic aspects of interacting trajectories Friedl, Katalin Nemkin, Viktória Tóbiás, András Data Structures and Algorithms Probability 68Q25, 68W40, 60K05, 92D15 Systems of interacting trajectories were recently studied in~\cite{HGSTW24}. Such a system of $[0,1]$-valued piecewise linear trajectories arises as a scaling limit of the system of logarithmic subpopulation sizes in a population-genetic model (more precisely, a Moran model) with mutation and selection. By definition, the resident fitness is initially 0 and afterwards it increases by the ultimate slope of each trajectory that reaches height 1. We show that although the interaction of $n$ trajectories may yield $Ω(n^2)$ slope changes in total, the resident fitness function can be computed algorithmically in $O(n)$ time. Our algorithm uses the so-called continued lines representation of the system of interacting trajectories. In the special case of Poissonian interacting trajectories where the birth times of the trajectories form a Poisson process and the initial slopes are random and i.i.d., we provide a linear bound on the expected total number of slope changes. |
| title | Resident fitness computation in linear time and other algorithmic aspects of interacting trajectories |
| topic | Data Structures and Algorithms Probability 68Q25, 68W40, 60K05, 92D15 |
| url | https://arxiv.org/abs/2502.11561 |