Dr. Mark Humphrys

School of Computing. Dublin City University.

Home      Blog      Teaching      Research      Contact

Search:

CA216      CA249      CA318

CA400      CA651      CA668


Nature's elegant algorithms

As engineers in machine evolution we can avoid many problems that nature has to solve.

But it is fascinating to see the "algorithms" that have evolved in nature to solve these problems.




How to build one genotype out of two genotypes

Basic problem:
"DNA" is instructions for how to build phenotype:

  How to build arms | How to build legs 
We want child to take the instructions from both parents:

  Father's How to build arms | Father's How to build legs 
  Mother's How to build arms | Mother's How to build legs 

Possibilities:

  1. Child takes all of both parents' DNA - But then you end up with 2 copies of the instructions. Which do you use?
    And what do you pass on? Does your child have 4 copies? And so on.

  2. Child takes part of father's DNA, part of mother's:
    DNA stays constant in size.
    Say each individual has 1 copy of instructions. Father has 1 copy. Mother has 1 copy. Father gives half and mother gives half.




Father gives half. Mother gives half. But how do the halves match?

Problem for nature: Need to synchronise the halves you get, so that don't get 2 copies of instructions for arms and no copies of instructions for legs.

How does nature do it? This was not understood until the mid-late 20th century.

Father's part (the "sperm") can't have only 1/2 copy of instructions when it leaves his body because it may not synchronise with the mother's 1/2 copy (the "egg"). Sperm would have to contain father's full DNA and then, when it got to egg, synchronise at that point with egg DNA to ensure full copy of instructions passed on.




Two copies of instructions - Nature's elegant algorithm

Nature has evolved an elegant solution as follows. Everyone carries precisely 2 copies of instructions, no more, no less. More than you need. For each instruction, you only actually use 1 copy (dominant/recessive genes).

Your father and mother both carried 2 copies also. They divided these to produce sperm and eggs ("gametes"), each containing 1 full copy. The 1-copy sperm and 1-copy egg come together to make new individual with 2 copies. Process repeats.

That's the basic scheme (not understood until 20th century, remember!)




Assortment and crossover

It is the process of sperm/egg-production at which the first major reshuffling takes place.

There are 23 chromosomes (strings) to make up the whole instruction set (for humans). Your mother/father has 2 copies:

c1,..,c23 (from grandfather)
d1,..,d23 (from grandmother)

The sperm/egg gets 1 copy of the instructions, but mixed up (independent assortment of chromosomes):

c1,d2,d3,c4,...,d23

Hence there are 223 possible combinations - massive genetic variety possible compared to asexual reproduction.

Secondly, even looking at a single chromosome string, new strings are created by crossover (there will also be mutation as well). For each chromosome at position i, we have 2 copies:

ci = 0000000000000000000 (from grandfather)
di = 1111111111111111111 (from grandmother)

DNA replication:

  0000000000000000000

  0000000000000000000

  1111111111111111111

  1111111111111111111
Possibly "cross over" the instructions of adjacent ones at some point (may be multiple crossovers):
  0000000000000000000

  0000000000000111111

  1111111111111000000

  1111111111111111111
Each sperm/egg gets one of these strands, for each of its 23 chromosomes. This process produces sperm/eggs in batches of 4, each with 1 copy of instructions. (In fact, sperm are produced 4 at a time alright, but with eggs, 3 of these 1-copy "gametes" are discarded, and 1 picked for the egg.)

The second reshuffling is when the 1-copy sperm and 1-copy egg get together. Child has 2 copies. Some genes will be dominant and some recessive. Genes that were dominant in parent may be completely missing in child, and grandparent's recessive gene is expressed again. Child grows up with 2 copies. Process repeats.




Crossover breaking genes

In nature a crossover may break the gene at the crossover site.
This may be a good thing (a useful mutation) or (more likely) a bad thing.
However, in the 2-copy system, this is only 1 of the copies. The other may have undergone its own crossover, but very unlikely to be the same point, so we still have a working copy just in case.



Alternatives to the 2-copy system

If the only reshuffling was who you mated with, then children could be a new combination alright, but all siblings would be the same. So there is further reshuffling - every sperm and egg is unique.

Synchronisation of 2 copies happens inside the same body - easier to control. The crossover mechanism ensures that we can mix up the instructions while ensuring that each sperm/egg still has 1 full copy.

Nature could presumably have just 1-copy individuals, get the 1-copy sperm DNA and 1-copy egg DNA together, and then make sure there was a crossover as above, and pick the child from one of the crossed over segments. Would probably get a lot of clones (crossover didn't happen). Also not as much diversity (don't get grandparent's recessive genes, as above). 2-copies also more robust in terms of error correction.

Interesting to consider why 2-copies has evolved everywhere, and not 3 or more, and not 1.





50-50 ratio - Further elegance in nature

If you have sexes, how on earth do you maintain a 50-50 coin flip for the sex of the offspring? In a machine algorithm, we can use a random number generator.

How can nature toss the coin so accurately so that 50 percent of population always is male and 50 percent female?

Each male carries 2 copies X, Y. Each female carries 2 copies X, X. Male produces millions of X sperm, millions of Y sperm, in proper proportions (doesn't have to count - it just takes millions of X-Y cells and splits them up). All female 1-copy eggs are X.

If a Y sperm fertilises egg, child has X plus Y (male).
If an X sperm, child is X plus X (female). And so it continues.

Interesting that men throughout history have berated their wives for producing daughters, e.g. Henry VIII, when of course it is the man's own sperm that decides the issue.

Anything we can learn from this natural "Monte Carlo" "algorithm" to ensure 50-50 ratios?





Machine evolution - 1 copy system

Machine evolution uses just 1 copy of instructions, because it can easily synchronise the two parents' copies.

If it used a 2-copy system, it would have to get involved in defining what is dominant/recessive.
e.g. 10 genes in genotype. 2 copies. Which is dominant/recessive?   210   possible choices.




Why did sex evolve?

Why is sexual reproduction a good search strategy?

Sex seems to be a way of maintaining better diversity in a population, by mixing up different building blocks, as opposed to asexual reproduction, where we depend on slow mutations from a common origin.

But still, once a solution is found, surely you settle down with asexual reproduction?

Yes, that may be true. Sex may be related to a (fast or slowly) changing fitness landscape. The fastest changing fitness landscape may, for example, be that caused by fast-evolving parasites. In a changing fitness landscape, we want to keep alive a diversity of solutions, so the population can move in one of many different directions when necessary. If there's only one genotype, and the Black Death kills it, then you go extinct.

But even if there is benefit for the species, how does that translate into benefit for the individual? The evolution of sex is a long-standing topic of debate.



Sexual selection

Sexual reproduction also introduces an objective, "run-time" selection of how well you are dealing with the current fitness landscape. Sexual selection (mate choice) means you get tested during your life on a basis other than pure survival. You have to have survived looking good (fit, healthy). You have to survive to adulthood, parasite-free, to be picked by a mate.

Sexual selection: The individuals choose their own mates according to preferences that can be encoded in the genes.

The problem with sexual selection is it leads to runaway effects like the peacock's tail.
We tend not to allow sexual selection / mate choice in machine evolution.



Feeds      w2mind.org

On Internet since 1987.