Conference Agenda

Overview and details of the sessions of this conference. Please select a date or location to show only sessions at that day or location. Please select a single session for detailed view (with abstracts and downloads if available).

 
Session Overview
Session
MS150, part 2: Fitness landscapes and epistasis
Time:
Thursday, 11/Jul/2019:
3:00pm - 5:00pm

Location: Unitobler, F-112
30 seats, 54m^2

Presentations
3:00pm - 5:00pm

Fitness landscapes and epistasis

Chair(s): Kristina Crona (American University, Washington, USA), Joachim Krug (Uni Koeln, Germany), Lisa Lamberti (ETHZ, Switzerland)

Studying relations, effects and properties of modified genes or organisms is an important topic in biology with implications in evolution, drug resistance and targeting, and much more. Biological data can many times be represented in digital form, a mutation has occurred or not, a species is present in an ecological system, or not. A fitness landscape is a function from such bit strings to some measured quality.
A property of fitness landscapes is epistasis, which is a phenomenon describing dependency relations among effects of combinations of modified genes. Polyhedral decompositions, such as cube triangulations induced by fitness landscapes, provide a systematic approach to epistasis.
In this session, we aim at bringing researches of various areas of science together to discuss contact points between applied polyhedral geometry, statistics and biology, and present recent developments in the field.

 

(25 minutes for each presentation, including questions, followed by a 5-minute break; in case of x<4 talks, the first x slots are used unless indicated otherwise)

 

Shape theory, landscape topography and evolutionary dynamics

Joachim Krug, Malvika Srivastava
Uni Koeln, Germany

The increasing availability of highthroughput data has lead to an upsurge of interest in the quantitative characterization of fitness landscapes and the epistatic interactions they encode. After a brief introduction to the fitness landscape concept and its empirical basis, the talk will focus on a comparison between the geometric shape theory and more conventional combinatorial and graphtheoretic approaches. We will explore to what extent the geometric shape of a landscape constrains its topography and guides the dynamics of populations evolving on it, addressing in particular the potential of shape theory to predict the relative performance of recombining and nonrecombining populations. The investigation is based on probabilistic ensembles of fitness landscapes, primarily the houseofcards model comprising uncorrelated random fitness values.

 

Graphs, polytopes, and unpredictable evolution

Kristina Crona
American University, Washington, USA

Fitness graphs (cube orientations) and triangulations capture different aspects of fitness landscapes, in some sense analogous to first and second derivatives. However, the graphs are informative also about higher order interactions. By using graphs one can relate unpredictable fitness and unpredictable evolution. Specifically, higher order epistasis is associated with many peaks in the fitness landscapes. This result was verified by an exhaustive search of 193,270,310 4cube graphs distributed on 511,863 isomorphism classes, and applications of graph theory (including Hall's marriage theorem and chromatic polynomials). Fitness graphs can provide some intuition for genetic recombination, in particular for a category of landscapes where the benefit of recombination is dramatic. However, the limitation of fitness graphs is apparent since the effect of recombination is highly sensitive for curvature. Related open problems will be discussed.

 

Computational complexity as an ultimate constraint on evolution

Artem Kaznatcheev
University of Oxford, UK

Experiments show that evolutionary fitness landscapes can have a rich combinatorial structure due to epistasis. For some landscapes, this structure can produce a computational constraint that prevents evolution from finding local fitness optima -- thus overturning the traditional assumption that local fitness peaks can always be reached quickly if no other evolutionary forces challenge natural selection. Here, I introduce a distinction between easy landscapes of traditional theory where local fitness peaks can be found in a moderate number of steps and hard landscapes where finding local optima requires an infeasible amount of time. Hard examples exist even among landscapes with no reciprocal sign epistasis; on these semi-smooth fitness landscapes, strong selection weak mutation dynamics cannot find the unique peak in polynomial time. More generally, on hard rugged fitness landscapes that include reciprocal sign epistasis, no evolutionary dynamics -- even ones that do not follow adaptive paths -- can find a local fitness optimum quickly. Moreover, on hard landscapes, the fitness advantage of nearby mutants cannot drop off exponentially fast but has to follow a power-law that long term evolution experiments have associated with unbounded growth in fitness. Thus, the constraint of computational complexity enables open-ended evolution on finite landscapes. Knowing this constraint allows us to use the tools of theoretical computer science and combinatorial optimization to characterize the fitness landscapes that we expect to see in nature. I present candidates for hard landscapes at scales from single genes, to microbes, to complex organisms with costly learning (Baldwin effect) or maintained cooperation (Hankshaw effect). Just how ubiquitous hard landscapes (and the corresponding ultimate constraint on evolution) are in nature becomes an open empirical question.

 

Tropical Principal Component Analysis and its Applications to Phylogenomics

Ruriko Yoshida1, Leon Zhang2, Xu Zhang3
1Naval Postgraduate School, USA, 2University of California, Berkeley, USA, 3University of Kentucky, USA

Principal component analysis is a widely-used method for the dimensionality reduction of a given data set in a high-dimensional Euclidean space. Here we define and analyze two analogues of principal component analysis in the setting of tropical geometry. In one approach, we study the Stiefel tropical linear space of fixed dimension closest to the data points in the tropical projective torus; in the other approach, we consider the tropical polytope with a fixed number of vertices closest to the data points. We then give approximative algorithms for both approaches and apply them to phylogenetics, testing the methods on simulated phylogenetic data and on an empirical dataset of Apicomplexa genomes. This is joint work with Leon Zhang and Xu Zhang.