Amplifiers for the Moran Process
- Submitting institution
-
The University of Essex
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 1388
- Type
- D - Journal article
- DOI
-
10.1145/3019609
- Title of journal
- Journal of the ACM
- Article number
- 5
- First page
- 1
- Volume
- 64
- Issue
- 1
- ISSN
- 0004-5411
- Open access status
- Technical exception
- Month of publication
- March
- Year of publication
- 2017
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
4
- Research group(s)
-
A - Artificial Intelligence (AI)
- Citation count
- 10
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- The Moran process is a randomized algorithm modelling how genetic mutations spread through spatially structured populations. The conference version won best paper (319 in track A) at ICALP'16, and likewise this leading-journal publication designs significant new "strongly-amplifying" structures, where mutations with any fixed evolutionary advantage almost certainly spread throughout the population. We demonstrate that previously published strong amplifiers are less effective than claimed by their authors' heuristic analyses, and less effective than ours, which are nearly optimal. This is the first mathematically rigorous analysis of strong amplifiers, including those previously proposed, taking into account dependencies between events and probability concentration.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -