際際滷

際際滷Share a Scribd company logo

EVOLUTION BEFORE DERWIN

Download as PPT, PDF
Basra Soni
Basra Soni

- Evolution can be viewed through an algorithmic lens, with natural selection and genetics represented as algorithms - Sex in evolution maximizes "mixability", or an organism's ability to perform well across a broad range of genetic combinations through increasing genetic variation - Computer science concepts like no-regret learning and multiplicative weight updates help explain how even weak selection can drive evolution through genetic drift and result in the emergence of complex traits over many generations

1 of 50
Download to read offline
Algorithmic Insights and the Theory of Evolution Christos H. Papadimitriou UC Berkeley
The Algorithm as a Lens It started with Alan Turing, 60 years ago Algorithmic thinking as a novel and productive way for understanding and transforming the Sciences Mathematics, Statistical Physics, Quantum Physics, Economics and Social Sciences This talk: Evolution
Evolution Before Darwin Erasmus Darwin
Before Darwin J.-B. Lamarck
Before Darwin Charles Babbage [Paraphrased] God created not species, but the Algorithm for creating species
Darwin, 1858 Common Ancestry Natural Selection
The Origin of Species Possibly the worlds most masterfully compelling scientific argument The six editions 1859, 1860, 1861, 1866, 1869, 1872
The Wallace-Darwin papers
Brilliant argument, and yet many questions left unasked, e.g.: How does novelty arise? What is the role of sex?
After Darwin A. Weismann [Paraphrased] The mapping from genotype to phenotype is one-way
Genetics Gregor Mendel [1866] Number of citations between 1866 and 1901: 3
The crisis in Evolution 1900 - 1920 Mendelians vs. Darwinians Geneticists vs. Biometricists/Gradualists
The Modern Synthesis 1920 - 1950 Fisher Wright - Haldane
Big questions remain e.g.: How does novelty arise? What is the role of sex?
Evolution and Algorithmic Insights How do you find a 3-billion long string in 3 billion years? L. G.Valiant At the Wistar conference (1967), Schutzenberger asked virtually the same question
Valiants Theory of Evolvability Which traits can evolve? Evolvability is a special case of statistical learning
Evolution and CS Practice: Genetic Algorithms [ca. 1980s] To solve an optimization problem create a population of solutions/genotypes who procreate through sex/genotype recombination with success proportional to their objective function value Eventually, some very good solutions are bound to arise in the soup
And in this Corner Simulated Annealing Inspired by asexual reproduction Mutations are adopted with probability increasing with fitness/objective differential (and decreasing with time)
The Mystery of Sex Deepens Simulated annealing (asexual reproduction) works fine Genetic algorithms (sexual reproduction) dont work In Nature, the opposite happens: Sex is successful and ubiquitous
?
A Radical Thought What if sex is a mediocre optimizer of fitness (= expectation of offspring)? What if sex optimizes something else? And what if this something else is its raison d 棚tre?
Mixability! In [LPDF 2008] we establish through simulations that: Natural selection under asex optimizes fitness But under sex it optimizes mixability: The ability of alleles (gene variants) to perform well with a broad spectrum of other alleles
Explaining Mixability Fitness landscape of a 2-gene organism 3 2 4 5 4 1 0 0 7 2 2 1 0 4 3 1 8 1 3 2 3 2 4 5 4 1 0 0 7 2 2 1 0 4 3 1 8 1 3 2 3 2 4 5 4 1 0 0 7 2 2 1 0 4 3 1 8 1 3 2 Rows: alleles of gene A Columns: alleles of gene B Entries: fitness of the combination
Explaining Mixability (cont) Asex will select the largest numbers 3 2 4 5 4 1 0 0 7 2 2 1 0 4 3 1 8 1 3 2 3 2 4 5 4 1 0 0 7 2 2 1 0 4 3 1 8 1 3 2 3 2 4 5 4 1 0 0 7 2 2 1 0 4 3 1 8 1 3 2
Explaining Mixability (cont) But sex will select the rows and columns with the largest average 3 2 4 5 4 1 0 0 7 2 2 1 0 4 3 1 8 1 3 2 3 2 4 5 4 1 0 0 7 2 2 1 0 4 3 1 8 1 3 2 3 2 4 5 4 1 0 0 7 2 2 1 0 4 3 1 8 1 3 2
Neutral Theory and Weak Selection Kimura 1970: Evolution proceeds not by leaps upwards, but mostly horizontally, through statistical drift Weak selection: the values in the fitness matrix are very close, say in [1 竜, 1 + 竜]
Changing the subject: The experts problem Every day you must choose one of n experts The advice of expert i on day t results in a gain G[i, t] in [-1, 1] Challenge: Do as well as the best expert in retrospect Surprise: It can be done! [Hannan 1958, Cover 1980, Winnow, Boosting, no-regret learning, MWUA, ]
Multiplicative weights update Initially, assign all experts same probability At each step, increase the probablity of each by (1 + 竜 G[I, t]) (and then normalize) Theorem: Does as well as the best expert MWUA solves: zero-sum games, linear programming, convex programming, network congestion,
Disbelief Computer scientists find it hard to believe that such a crude technique solves all these sophisticated problems The eye to this day gives me a cold shudder. [cf: Valiant on three billion bits and years]
Theorem [CLPV 2012]: Under weak selection, evolution is a game the players are the genes the strategies are the alleles the common utility is the fitness of the organism (coordination game) the probabilities are the allele frequencies game is played through multiplicative updates
There is more Recall the update (1 + 竜 G[i, t]) 竜 is the selection strength (1 + 竜 G[i, t]) is the alleles mixability! Variance preservation: multiplicative updates is known to enhance entropy Two mysteries united This is the role of sex in Evolution
Pointer Dogs
Pointer Dogs C. H. Waddington
Waddingtons Experiment (1952) Generation 1 Temp: 20o C
Waddingtons Experiment (1952) Generation 2-4 Temp: 40o C ~15% changed Select and breed those
Waddingtons Experiment (1952) Generation 5 Temp: 40o C ~60% changed Select and breed those
Waddingtons Experiment (1952) Generation 6 Temp: 40o C ~63% changed Select and breed those
Waddingtons Experiment (1952) () Generation 20 Temp: 40o C ~99% changed
Surprise! Generation 20 Temp: 20o C ~25% stay changed!!
Genetic Assimilation Adaptations to the environment become genetic!
Is There a Genetic Explanation? Function f ( x, h ) with these properties: Initially, Probx~p[0] [f ( x, h = 0)] 0% Then Probp[0][f ( x, 1)] 15% After breeding Probp[1][f ( x, 1)] 60% Successive breedings, Probp[20][f ( x,1)] 99% Finally, Probp[20][f ( x, 0)] 25%
A Genetic Explanation Suppose that red head is this Boolean function of 10 genes and high temperature red head = x1 + x2 + + x10 + 3h 10 Suppose also that the genes are independent random variables, with pi initially half, say.
A Genetic Explanation (cont.) In the beginning, no fly is red (the probability of being red is 2-n ) With the help of h = 1, a few become red If you select them and breed them, ~60% will be red!
Why 60%?
A Genetic Explanation (cont.) Eventually, the population will be very biased towards xi = 1 (the pis are close to 1) And so, a few flies will have all xi = 1 for all i, and they will stay red when h becomes 0
Generalize! Let B is any Boolean function n variables x1x2 xn(no h) Independent, with probabilities p = (p1 p2 pn) Satisfiability game: if B is satisfied, each variable gets 1, otherwise 1 - 竜 Repeated play by multiplicative weights
Boolean functions (cont.) Conjecture: This solves SAT Can prove it for monotone functions (in poly time) Can almost prove it in general (Joint work with Adi Livnat, Greg Valiant, Andrew Won)
Interpretation If there is a Boolean combination of a modestly large number of genes that creates an unanticipated trait conferring even a small advantage, then this combination will be discovered and eventually fixed in the population. With sex, all moderate-sized Boolean functions are evolvable.
Sooooo The theory of life is deep and fascinating Insights of an algorithmic nature can help make progress Evolution is a coordination game between genes played via multiplicative updates Novel viewpoint that helps understand the central role of sex in Evolution
Thank You!

More Related Content

EVOLUTION BEFORE DERWIN

  • 1. Algorithmic Insights and the Theory of Evolution Christos H. Papadimitriou UC Berkeley
  • 2. The Algorithm as a Lens It started with Alan Turing, 60 years ago Algorithmic thinking as a novel and productive way for understanding and transforming the Sciences Mathematics, Statistical Physics, Quantum Physics, Economics and Social Sciences This talk: Evolution
  • 3. Evolution Before Darwin Erasmus Darwin
  • 5. Before Darwin Charles Babbage [Paraphrased] God created not species, but the Algorithm for creating species
  • 7. The Origin of Species Possibly the worlds most masterfully compelling scientific argument The six editions 1859, 1860, 1861, 1866, 1869, 1872
  • 9. Brilliant argument, and yet many questions left unasked, e.g.: How does novelty arise? What is the role of sex?
  • 10. After Darwin A. Weismann [Paraphrased] The mapping from genotype to phenotype is one-way
  • 11. Genetics Gregor Mendel [1866] Number of citations between 1866 and 1901: 3
  • 12. The crisis in Evolution 1900 - 1920 Mendelians vs. Darwinians Geneticists vs. Biometricists/Gradualists
  • 13. The Modern Synthesis 1920 - 1950 Fisher Wright - Haldane
  • 14. Big questions remain e.g.: How does novelty arise? What is the role of sex?
  • 15. Evolution and Algorithmic Insights How do you find a 3-billion long string in 3 billion years? L. G.Valiant At the Wistar conference (1967), Schutzenberger asked virtually the same question
  • 16. Valiants Theory of Evolvability Which traits can evolve? Evolvability is a special case of statistical learning
  • 17. Evolution and CS Practice: Genetic Algorithms [ca. 1980s] To solve an optimization problem create a population of solutions/genotypes who procreate through sex/genotype recombination with success proportional to their objective function value Eventually, some very good solutions are bound to arise in the soup
  • 18. And in this Corner Simulated Annealing Inspired by asexual reproduction Mutations are adopted with probability increasing with fitness/objective differential (and decreasing with time)
  • 19. The Mystery of Sex Deepens Simulated annealing (asexual reproduction) works fine Genetic algorithms (sexual reproduction) dont work In Nature, the opposite happens: Sex is successful and ubiquitous
  • 20. ?
  • 21. A Radical Thought What if sex is a mediocre optimizer of fitness (= expectation of offspring)? What if sex optimizes something else? And what if this something else is its raison d 棚tre?
  • 22. Mixability! In [LPDF 2008] we establish through simulations that: Natural selection under asex optimizes fitness But under sex it optimizes mixability: The ability of alleles (gene variants) to perform well with a broad spectrum of other alleles
  • 23. Explaining Mixability Fitness landscape of a 2-gene organism 3 2 4 5 4 1 0 0 7 2 2 1 0 4 3 1 8 1 3 2 3 2 4 5 4 1 0 0 7 2 2 1 0 4 3 1 8 1 3 2 3 2 4 5 4 1 0 0 7 2 2 1 0 4 3 1 8 1 3 2 Rows: alleles of gene A Columns: alleles of gene B Entries: fitness of the combination
  • 24. Explaining Mixability (cont) Asex will select the largest numbers 3 2 4 5 4 1 0 0 7 2 2 1 0 4 3 1 8 1 3 2 3 2 4 5 4 1 0 0 7 2 2 1 0 4 3 1 8 1 3 2 3 2 4 5 4 1 0 0 7 2 2 1 0 4 3 1 8 1 3 2
  • 25. Explaining Mixability (cont) But sex will select the rows and columns with the largest average 3 2 4 5 4 1 0 0 7 2 2 1 0 4 3 1 8 1 3 2 3 2 4 5 4 1 0 0 7 2 2 1 0 4 3 1 8 1 3 2 3 2 4 5 4 1 0 0 7 2 2 1 0 4 3 1 8 1 3 2
  • 26. Neutral Theory and Weak Selection Kimura 1970: Evolution proceeds not by leaps upwards, but mostly horizontally, through statistical drift Weak selection: the values in the fitness matrix are very close, say in [1 竜, 1 + 竜]
  • 27. Changing the subject: The experts problem Every day you must choose one of n experts The advice of expert i on day t results in a gain G[i, t] in [-1, 1] Challenge: Do as well as the best expert in retrospect Surprise: It can be done! [Hannan 1958, Cover 1980, Winnow, Boosting, no-regret learning, MWUA, ]
  • 28. Multiplicative weights update Initially, assign all experts same probability At each step, increase the probablity of each by (1 + 竜 G[I, t]) (and then normalize) Theorem: Does as well as the best expert MWUA solves: zero-sum games, linear programming, convex programming, network congestion,
  • 29. Disbelief Computer scientists find it hard to believe that such a crude technique solves all these sophisticated problems The eye to this day gives me a cold shudder. [cf: Valiant on three billion bits and years]
  • 30. Theorem [CLPV 2012]: Under weak selection, evolution is a game the players are the genes the strategies are the alleles the common utility is the fitness of the organism (coordination game) the probabilities are the allele frequencies game is played through multiplicative updates
  • 31. There is more Recall the update (1 + 竜 G[i, t]) 竜 is the selection strength (1 + 竜 G[i, t]) is the alleles mixability! Variance preservation: multiplicative updates is known to enhance entropy Two mysteries united This is the role of sex in Evolution
  • 33. Pointer Dogs C. H. Waddington
  • 35. Waddingtons Experiment (1952) Generation 2-4 Temp: 40o C ~15% changed Select and breed those
  • 36. Waddingtons Experiment (1952) Generation 5 Temp: 40o C ~60% changed Select and breed those
  • 37. Waddingtons Experiment (1952) Generation 6 Temp: 40o C ~63% changed Select and breed those
  • 38. Waddingtons Experiment (1952) () Generation 20 Temp: 40o C ~99% changed
  • 40. Genetic Assimilation Adaptations to the environment become genetic!
  • 41. Is There a Genetic Explanation? Function f ( x, h ) with these properties: Initially, Probx~p[0] [f ( x, h = 0)] 0% Then Probp[0][f ( x, 1)] 15% After breeding Probp[1][f ( x, 1)] 60% Successive breedings, Probp[20][f ( x,1)] 99% Finally, Probp[20][f ( x, 0)] 25%
  • 42. A Genetic Explanation Suppose that red head is this Boolean function of 10 genes and high temperature red head = x1 + x2 + + x10 + 3h 10 Suppose also that the genes are independent random variables, with pi initially half, say.
  • 43. A Genetic Explanation (cont.) In the beginning, no fly is red (the probability of being red is 2-n ) With the help of h = 1, a few become red If you select them and breed them, ~60% will be red!
  • 45. A Genetic Explanation (cont.) Eventually, the population will be very biased towards xi = 1 (the pis are close to 1) And so, a few flies will have all xi = 1 for all i, and they will stay red when h becomes 0
  • 46. Generalize! Let B is any Boolean function n variables x1x2 xn(no h) Independent, with probabilities p = (p1 p2 pn) Satisfiability game: if B is satisfied, each variable gets 1, otherwise 1 - 竜 Repeated play by multiplicative weights
  • 47. Boolean functions (cont.) Conjecture: This solves SAT Can prove it for monotone functions (in poly time) Can almost prove it in general (Joint work with Adi Livnat, Greg Valiant, Andrew Won)
  • 48. Interpretation If there is a Boolean combination of a modestly large number of genes that creates an unanticipated trait conferring even a small advantage, then this combination will be discovered and eventually fixed in the population. With sex, all moderate-sized Boolean functions are evolvable.
  • 49. Sooooo The theory of life is deep and fascinating Insights of an algorithmic nature can help make progress Evolution is a coordination game between genes played via multiplicative updates Novel viewpoint that helps understand the central role of sex in Evolution