Shakespeare’s Birthday and Evolution | Byte Size Biology (original) (raw)

William Shakespeare was baptized April 26, 1564. His birthday is traditionally commemorated on April 23 (incidentally, that is also the date of his death, in 1616). One interesting connection between Shakespeare and evolution was made by Richard Dawkins in his book The Blind Watchmaker: I am talking about the Weasel program. Weasel is an elegant illustration of the process that drives evolution by natural selection: random variation in offspring, coupled with non-random selection. The connection to Shakespeare is in the quote from Hamlet: “Methinks it is like a weasel”. Achieving this exact sentence through random processes alone (a monkey hacking away at a typewriter) would take and estimated 1040 generations. But achieving it through random mutations coupled with targeted selection makes for a much shorter number of generations: less than 100, usually.

If you are unfamiliar with the Weasel program, read the Wikipedia entry before reading on.

In honor of The Bard’s birthday, I have penned a short Python program which performs Weasel. You may need to tweak it for Windows (remove the first #! line which is a Linux thing). When running the program, the user selects 3 parameters: the target net result (in the form of a string), the number of offspring per generation, and the mutation rate.

Here is a demo run, with 300 offspring per generation, and a mutation rate of 0.05 per position:

./weasel.py "methinks it is like a weasel" 300 0.05 1 ,<o?[}= g!yq[}?*v=.+ :y<<:g 2 ,<o?[}= gjyq[}?v=.m :y<<eg 3 ,<o?[}= gjyq[ ?*v=.m :y<<eg 4 ,<o?[}= ijyq[ ?v=.m :y<<eg 5 ,<o?[k= ijyq[ ?*v=.m :y<<eg 6 g<o?[k= ijyq[ lv=.m :y<<eg 7 g<o?[k= ijyq[ l*ve.m :y<<eg 8 g<o?[k= ij q[ lve.m :y<<eg 9 `v<o?[k= ij qs lve.m :p<<eg 10 ev<o?[k= ij qs lve.v :paieg 11 ev<o?[k( ij qs lke.v :paieg 12 ev<o?[k( it qs lke.v :paieg 13 ev<o?[k( it qs l_ke.v wpaieg 14 ev<oi[k( it qs l_ke.v wpaieg 15 ev<oi[k( it qs l_ke.a wpaieg 16 ev<oi[k( it [s l_ke.a wpaiel 17 ev<oi[k( it is l_ke.a wpaiel 18 ev<oi[k( it is l_ke.a weael 19 ev<oi[k( it is l_ke.a weael 20 mv<oi[k( it is l_ke.a wea*el 21 mv<oi[k( it is llke\a weasel 22 mv<,i[k( it is llke\a weasel 23 mv<hi[k( it is llke\a weasel 24 mvzhi[k( it is like\a weasel 25 mvzhi[k( it is like\a weasel 26 mv(hi[k( it is like\a weasel 27 mv(hi[ks it is like\a weasel 28 mv(hi[ks it is like\a weasel 29 mv(hi[ks it is like\a weasel 30 mvthi[ks it is like&a weasel 31 mvthi[ks it is like&a weasel 32 mvthimks it is like&a weasel 33 mvthimks it is like&a weasel 34 mvthimks it is like&a weasel 35 mvthimks it is like&a weasel 36 mvthimks it is like&a weasel 37 mxthimks it is like&a weasel 38 mxthimks it is like&a weasel 39 mxthimks it is like&a weasel 40 mxthimks it is like&a weasel 41 mxthimks it is like&a weasel 42 mxthimks it is like&a weasel 43 mxthimks it is like a weasel 44 mxthimks it is like a weasel 45 mxthilks it is like a weasel 46 mxthilks it is like a weasel 47 mxthilks it is like a weasel 48 mxthinks it is like a weasel 49 mxthinks it is like a weasel 50 mxthinks it is like a weasel 51 mxthinks it is like a weasel 52 mxthinks it is like a weasel 53 mxthinks it is like a weasel 54 mxthinks it is like a weasel 55 mxthinks it is like a weasel 56 mxthinks it is like a weasel 57 mxthinks it is like a weasel 58 methinks it is like a weasel

And here is the Python code:

#!/usr/bin/python import string import random import sys import copy

Copyright(C) 2011 Iddo Friedberg

Released under Biopython license. http://www.biopython.org/DIST/LICENSE

Do not remove this comment

ALLCHARS = string.lowercase+' '+string.punctuation def loopweasel(target_string,n_offspring,mut_rate): i = 1 target_string = target_string.lower() current_string = list(''.join(random.choice(ALLCHARS) for i in range(len(target_string)))) print " %s" % target_string while target_string != ''.join(current_string): print "%4d %s" % (i,''.join(current_string)) i += 1 offsprings = create_offspring(current_string, n_offspring,mut_rate) current_string = evolve_string(offsprings, target_string) print "%4d %s" % (i,''.join(current_string))

def create_offspring(current_string,n_offspring,mut_rate): offspring_list = [] for i in (range(n_offspring)): offspring = [] for c in current_string: if random.random() < mut_rate: offspring.append(random.choice(ALLCHARS)) else: offspring.append(c) offspring_list.append(offspring) return offspring_list

def diffseq(a,b): diffcount = 0 for i,j in zip(a,b): if i != j: diffcount += 1 return diffcount

def evolve_string(offspring_list, target_string): best_match = (2000,'') for offspring in offspring_list: diffscore = diffseq(offspring, target_string) if diffscore < best_match[0]: best_match = (diffscore,offspring) return best_match[1]

if name == 'main': if len(sys.argv) < 4: print "Usage: weasel target_string n_offspring mutation_rate" print print "target_string: the string you would eventually evolve into" print "n_offspring: number of offspring per generation" print "mutation_rate rate of mutation per position, 0=< m <1" sys.exit(1) target_string = sys.argv[1] n_offspring = int(sys.argv[2]) mut_rate = float(sys.argv[3]) for i in target_string: if i not in ALLCHARS: print "Error, string can only contain %s" % ALLCHARS sys.exit(1) if mut_rate >= 1.0 or mut_rate < 0: print "Error: 0 =< mutation rate < 1" sys.exit(1) loopweasel(target_string,n_offspring, mut_rate)

A quick guide: “loopweasel” (line 11) is the main bit that loops through generations. In each loop iteration it first calls “create_offspring” (line 25) which creates a list with the “offspring” strings (300 in the above example). Mutations are inserted (or not) in line 30. Control returns to loopweasel, which calls evolve_string (line 44). All offspring strings are score to the target (“methinks it is like a weasel”) string, using the “diffseq” code (line 37). (Is there a built-in way in Python for doing that? I could not find any.) The best scoring match is not he chosen offspring. It is printed, and the loop is repeated. Repeat until best-fitted offspring matches the target string.

It is actually quite fun to play with different mutation rates and offspring / generation numbers. Try it. Then rent a good Shakespeare movie. As a horror fan, I’m going to watch Titus tonight.

Titus Andronicus. Source: Wikipedia