April was Mathematics Awareness Month, whose theme this year was Mathematics and Biology. Even though April is over, it may not be too late to add my 2 cents, since, as Keith Devlin put this in his April's column, "... raising the public awareness of mathematics will always be an uphill battle." In that column, Devlin offers some information about what went on during MAM; more can be found at the official MAM site.

This year's April was my private MAM, with exactly a Mathematics and Biology theme. My wife, a school psychologist by trade, became fascinated with the modern theory of evolution as expounded by Richard Dawkins in his book The Selfish Gene. The book, which she finished reading in March, afforded us in April a series of interesting family discussions. Among laymen and philosophers, Dawkins is famous for raising the issue of cultural evolution, brought about with the emergence of memes, the new kind of replicators. Compared to Darwinian evolution, cultural evolution is orders of magnitude faster. Our brains are adapted by natural selection to the long-vanished way of life that our ancestors led as foragers in small nomadic bands [Pinker, p 42]. The adaptation took place over thousands of generations. By comparison, mathematical memes succeeded in penetrating the quintessential biological science - the theory of evolution - in a little more than 100 years.

Natural evolution is about replication and propagation of genes. Genes live on chromosomes, chromosomes live in cells. In most cells, chromosomes live in pairs. In the sex cells, the sperms and eggs, chromosomes come in singles. When two sex cells fuse into one, the newly formed cell receives one chromosome from each of the parent cells. From then on, it multiplies by dividing, all the while passing on exact copies of its own chromosomes - in pairs, of course (but not necessarily creating exact copies of itself.) Not unexpectedly, most of the fun occurs in production of sex cells each of which carries single chromosomes. Where do these come from?

The paired chromosomes that live in most cells are not identical: one chromosome is of the maternal and the other of the paternal lineage. The genes on the two chromosomes are also paired, genes in a pair being potentially responsible for one or more features of the future organism (the phenotype.) The paired genes are known as alleles of each other. Alleles may have different effects on the phenotype, but only one allele of the two is given an opportunity to make its contribution to the offspring's genetic makeup. The lucky alleles that are selected by chance compose the single chromosomes carried by the sex cells. The process of composition is known as the crossover. Mistakes made by nature and chance during the crossover are called mutations. Mistakes happen.

Mutations aside, the evolutionary process of gene propagation is best visualized on a genealogy tree. The degree of relatedness between the nodes on a tree has been used to explain emergence of altruism as a result of natural selection. The degree of relatedness is a direct application of simple mathematics in biology. Powerful as this concept is, it was neglected by ethologists for a long time. In a commentary to the second edition of the book, Dawkins employs other mathematical tools (graphing, exponential growth, logarithmic scale) to investigate the spread of the relatedness meme in the scientific community.

A gene A in a cell comes either from a paternal or maternal chromosome. As a matter of fact, human beings and apes share more than 90% of their genes. As the history and the every day life teaches us, commonly shared genes can't be used to explain any noticeable degree of altruism. The simplified account of relatedness, thus, takes into account only genes that are rare in the population. (The full theory and therefore its conclusions do not depend on this simplification.) On average, gene A is shared by either of the cell's ancestors with probability 1/2. In a parent, a gene B has a 50% chance to be picked by the crossover to carry on its eternal function. Either way one looks, the relatedness between parents and the offspring is given by 1/2. Down the tree, the relatedness is decreasing: between grandparents and grandchildren it's only 1/4, between great grandparents and great grandchildren it's only 1/8, and so on.

In general, given any two nodes on a tree, one can find their nearest ancestor or ancestors. (Existence of the nearest ancestors is a piece of mathematics that Dawkins takes for granted.) For each such nearest ancestor, count and add up the number of generations towards each of the nodes. For siblings, the number is 2: one step up, another down. For uncles and nieces, the number is 3 ( = 1 + 2); for cousins, it's 4 ( = 2 + 2), and so on. Raise 1/2 to this power. The result is a partial degree of relatedness between the two nodes. But some nodes (e.g., siblings) share more than one nearest ancestor. The (total) degree of relatedness is the sum of partial degrees over all available nearest ancestors. Siblings, having two common ancestors, are related with the degree of 1/4 + 1/4 = 1/2, exactly like parents and children! First cousins are related with the degree of 1/8 (= 1/16 + 1/16), but, in some cases, may be closer. Incest is not only immoral and unhealthy, it also screws up the neat scientific picture drawn so far.

The symmetry of the relatedness breaks down for ants and other Hymenoptera. A hymenopteran nest typically has only one mature queen - a female responsible for all the ongoing reproduction in the nest. In her youth she was once fortunate to find a mate. From this one encounter, she stored up the sperm to be used for the rest of her life. She rations the sperm to her eggs while they pass through her tubes. Some eggs receive the sperm, some do not. The latter (which grow into males) have no father and carry only single chromosomes. Therefore a gene in a male comes from his mother with the probability 1. On the other hand, the mother, which has two sets of chromosomes, apportions, through the crossover as usual, only half her genes to the offspring.

The story differs, of course, for the fertilized eggs, but it never becomes boring. Fertilized eggs develop into females that not only share a father, but they de facto were conceived from identical sperm cells. A little counting reveals that the relatedness between two sisters is 3/4, more than between parents and the offspring. It then looks reasonable that a female hymenoptera should devote itself to caring more for her mother (who keeps producing her dear siblings), rather than aspire to get offspring of her own.

Evolution proceeds entirely without design, by mere chance. This is to say that there exists a comprehensive and consistent explanation for every known facet of evolution based on the theory of probability and natural selection. Nonetheless, it is sometimes convenient to describe a phenomenon as if genes had a purpose and were developing survival strategies. Thus the language of game theory found its way into evolutionary biology. Besides altruistic attitude, evolution may lead to development of co-operation between different species or even individual genes. Dawkins devotes a whole chapter, The nice guys finish first, to the favorite puzzle [Costi] of game theory - the Prisoner's Dilemma. As described in Pinker,

There is no solution for a single trial. But, repeated trials allow players - partners in crime - to observe and study each other's behavior and develop a better paying strategy. Dawkins describes two competitions organized by Robert Axelrod that showed superiority of a simple strategy Tit for Tat: start mum, then do what your opponent did on the previous trial. In general, strategies were divided into two classes: nice and nasty. An adherent of a nice strategy never rats first, a nasty fellow does. It turns out that, on the whole, nice strategies outperformed the nasty ones.

Other chapters in Dawkins' book may be easily related to different branches of mathematics. There is no room to even touch on all the possibilities. Nowadays, ideas that are clearly mathematical play an important and vibrant role in biology. Interestingly, the opposite is also true. Biological insights led to the development of the theories of neural networks and genetic algorithms [Goldberg, Holland, Mitchell]. The latter is especially relevant to the theory of evolution.

The applet below applies a genetic algorithm to solving the Toads and Frogs puzzle. (The puzzle, due to its name, might have served as an edifying activity during the recent MAM.) You may want to first solve the puzzle by conventional means, but here is how the algorithm works.

Possible solutions are represented by a sequence of moves - chromosomes - with every move thought of as a gene. The puzzle squares are numbered left to right starting with 0. Moves are designated by the number of the square from which the move is made. At any particular stage of the puzzle, only two moves are possible.

All chromosomes have the same length which I chose to be 5 genes longer than necessary. Crossover is an operator that for a pair of chromosomes produces two other chromosomes. First it cuts the given chromosomes into two by selecting a "crossover point", which is the same for both chromosomes. Next the chromosomes are sliced together but only after swapping the right (or left) pieces. With a certain probability (I took it to be 1/2, although usually that probability is much smaller) the new chromosomes are subject to a random mutation. In addition to a simple gene replacement, I also built in a mutation specifically reflecting the structure of the (puzzle) chromosomes: pick a random sub-chromosome, a contiguous subsequence of genes, and perform a cyclic rotation of genes in that sub-chromosome.

Each chromosome is evaluated by a fitness function to determine its "evolutionary viability". Starting on the left I just count the number of moves that can be performed skipping the "ballast" ones (these are removed when a solution is found). The population of ten chromosomes is sorted according to their fitness. On a single evolutionary step either I replace all but the fittest chromosome or I replace only the two worst performers. The mating chromosomes are selected randomly with probabilities proportional to their fitness. That's all.

The search space for a 3 + 3 puzzle has a formidable number of elements: 7²⁰. The algorithm usually finds one of the two solutions in less than 1000 iterations. The algorithm takes about 20-30 steps to solve the 2 + 2 puzzle. It requires only little ingenuity to carry out the algorithm for a small puzzle manually.

This must be said, then: the puzzle may be simple, but searching for a solution in the space just described is not. Apart from the sheer size of the search space, every wrong move leads to a "false", local maximum of the fitness function. Watching the algorithm work, one can easily gain appreciation of the difficulty involved in solving a problem like this.

Genetic algorithms try to mimic natural evolution, but their justification rests on a mathematically sound theory developed by John Holland in the mid 1970s in his book Adaptation in Natural and Artificial Systems (1975). As the title applies, the same mathematical foundation underlies both natural and artificial systems. So it does not matter much whether adaptation of sequences of moves in the Toads and Frogs puzzle is judged artificial or not. It is natural, though, in at least one respect: it takes place in an environment that is absolutely natural for the bits and bytes that those chromosomes so naturally are.

References

1. R.Axelrod, The Evolution of Cooperation, Basic Books, 1984
2. J.L.Costi, Paradigms Lost, William Morrow And Company, 1989
3. J.L.Costi, Five Golden Rules, John Wiley & Sons, 1996
4. R.Dawkins, The Selfish Gene, Oxford University Press, new edition, 1989
5. D.E.Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, 1989
6. J.H.Holland, Adaptation in Natural and Artificial Systems, MIT, 1992
7. M.Mitchell, An Introduction to Genetic Algorithms, MIT, 1998
8. S.Pinker, How the Mind Works, W.W.Norton & Company, 1997

Alex Bogomolny has started and still maintains a popular Web site Interactive Mathematics Miscellany and Puzzles to which he brought more than 10 years of college instruction and, at least as much, programming experience. He holds M.S. degree in Mathematics from the Moscow State University and Ph.D. in Applied Mathematics from the Hebrew University of Jerusalem. He can be reached at alexb@cut-the-knot.com

Copyright © 1997-1999 Alexander Bogomolny