Abstract
A Quantitative Model of Innovation in Evolution
Leslie Valiant, Harvard University
I will describe a computational learning model of evolution in which all the following notions have definitions: the function being computed, the representation of the function, the evolutionary mechanism that produces variation in the representation, and the fitness of a representation. It would appear that all these notions need to have definitions if we are to account quantitatively for how the complex mechanisms, that apparently need millions of bits of information just to describe, could have evolved with the numbers of generations and individuals available. Biology suggests that the fundamental level at which evolution takes place is at the level of the expression functions of individual proteins in terms of each other, as the genome undergoes mutations. A quantitative explanation of how evolution at this level could have achieved what it apparently has would seem to be an achievable scientific goal.
On the Power and the Limits of Evolvability
In this talk I'll describe a technique for converting learning algorithms in the statistical query framework into evolution algorithms in L. Valiant's model. This technique implies a characterization of the power of the model and I'll overview the following results based on this characterization:(a) evolvability of most learnable classes of functions for fixed input distributions;(b) hardness of evolvability without distributional assumptions;(c) robustness of the model to many natural modifications of the definition.
Attribute-efficient Evolution
L. Valiant introduced a computational framework to study evolvability and Feldman showed that certain types of learning algorithms could be converted to evolutionary mechanisms in Valiant's framework. I will focus on the complexity of representations of evolutionary mechanisms. Most previously studied algorithms may result in fairly complex representations. Biological constraints suggest that the representations have low complexity, such as short cascades (low-depth) and sparsity. I will present a couple of mechanisms for the evolution of sparse linear functions under a large class of smooth distributions. These evolutionary mechanisms are attribute-efficient in the sense that the sparsity of the representations and the number of generations depend on the sparsity of the target function and the accuracy parameter, but not the total number of variables. Based on joint work with E. Angelino.
What Functions Do Gene Expression Levels Represent?
Elaine Angelino, Harvard University
I will give an introduction to mechanisms that regulate gene expression levels and describe an algebraic framework for modeling these systems. Gene expression level can be viewed as a function of a physical system described by a continuous time Markov chain over system states. Transitions between these states depend on physical properties, e.g., the rates of chemical reactions. Markov chain theory indicates that gene expression level is a rational function in terms of these transition rates. In the course of this talk, I will attempt to bridge two complementary points of view: chemical reaction network theory and statistical physics.