The Complexity of Genetic Diversity

DOI10.4230/LIPICS.ESA.2016.65zbMATH Open1397.68087arXiv1411.6322OpenAlexW2558601593MaRDI QIDQ4606337FDOQ4606337

Georgios Piliouras, Ruta Mehta, Sadra Yazdanbod, Ioannis Panageas

Publication date: 2 March 2018

Abstract: A key question in biological systems is whether genetic diversity persists in the long run under evolutionary competition or whether a single dominant genotype emerges. Classic work by Kalmus in 1945 has established that even in simple diploid species (species with two chromosomes) diversity can be guaranteed as long as the heterozygote individuals enjoy a selective advantage. Despite the classic nature of the problem, as we move towards increasingly polymorphic traits (e.g. human blood types) predicting diversity and understanding its implications is still not fully understood. Our key contribution is to establish complexity theoretic hardness results implying that even in the textbook case of single locus diploid models predicting whether diversity survives or not given its fitness landscape is algorithmically intractable. We complement our results by establishing that under randomly chosen fitness landscapes diversity survives with significant probability. Our results are structurally robust along several dimensions (e.g., choice of parameter distribution, different definitions of stability/persistence, restriction to typical subclasses of fitness landscapes). Technically, our results exploit connections between game theory, nonlinear dynamical systems, complexity theory and biology and establish hardness results for predicting the evolution of a deterministic variant of the well known multiplicative weights update algorithm in symmetric coordination games which could be of independent interest.

Full work available at URL: https://arxiv.org/abs/1411.6322

zbMATH Keywords

optimizationdynamical systemsstabilitycomplexityequilibrium

Mathematics Subject Classification ID

Genetics and epigenetics (92D10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Decision theory for games (91A35)

Cited In (4)

• Title not available (Why is that?)
• Bifurcation mechanism design -- from optimal flat taxes to better cancer treatments
• Mutation, Sexual Reproduction and Survival in Dynamic Environments
• The combinatorics of hidden diversity

This page was built for publication: The Complexity of Genetic Diversity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4606337)