Skip to content

Instantly share code, notes, and snippets.

@XMPPwocky
Last active August 9, 2021 22:01
Show Gist options
  • Save XMPPwocky/28b77297371b12581c341281bfcfeed2 to your computer and use it in GitHub Desktop.
Save XMPPwocky/28b77297371b12581c341281bfcfeed2 to your computer and use it in GitHub Desktop.
Display the source blob
Display the rendered blob
Raw
Loading
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.

Some setup first...

# ye olde imports
import math, random
from statistics import mean, geometric_mean

Imagine a virus which is, somehow, a single protein with only 3 "amino acids" (actually just uppercase letters here, oh well)

Currently, only one type is circulating, which is "XYZ".

EXISTING_TYPE = "XYZ"

But there's a possible variant, the Super Nasty Variant, "BAD", which escapes antibodies and is hard to even create good antibodies against (meaning even a vaccine targeted specifically at it has trouble):

SUPER_NASTY_TYPE = "BAD"

Now we'll run a comically oversimplified simulation of evolution: starting from a population of 100 copies of the existing virus (XYZ)...

POPULATION_SIZE = 100

def make_starting_population(): return [EXISTING_TYPE] * POPULATION_SIZE

Each generation, every virus makes a copy of itself (to form a population twice as big), possibly mutating in the process.

Then, each virus may die (in this case, be neutralized by antibodies or whatever); the odds of survival each generation is the virus's fitness.

Note that the steady-state here happens for viruses with fitness of 0.5 (they make a copy of themselves each generation, but on average the original or the copy dies).

def evolve(starting_population, fitness):
    population = starting_population

    new_population = [virus for virus in population] 
    
    
    # each virus makes a copy of itself, maybe mutating...
    for virus in population:
        new_population.append(maybe_mutate(virus))

    # but then some maybe die, based on their fitness:
    population = []
    
    for virus in new_population:
        if fitness(virus) > random.random():
            # virus survived
            population.append(virus)
            
    if not population:
        population = [EXISTING_TYPE] # goofy hack so that the virus never completely dies out

    return population
MAX_GENERATIONS = 5000 # timeout to keep things sensible
def run_experiment(fitness_fn, quiet=True):
    population = make_starting_population()

    if not quiet: print("Generation\tPop. size\tAvg. fitness\tMax. fitness")
    for generation in range(MAX_GENERATIONS):
        if generation % 100 == 0:
            fitnesses = [fitness_fn(virus) for virus in population]
            avg_fitness = geometric_mean(fitnesses)
            max_fitness = max(fitnesses)
            if not quiet: print("{:5}\t\t{:8}\t{:5.4f}\t\t{:5.4f}".format(generation, len(population), avg_fitness, max_fitness))

        population = evolve(population, fitness_fn)
        if SUPER_NASTY_TYPE in population:
            if not quiet: print("Super Nasty Variant evolved in {} generations!".format(generation))
            return generation
        
    return MAX_GENERATIONS # didn't evolve at all, time ran out

def run_many_experiments(fitness_fn, num_experiments):
    results = []
    for experiment in range(num_experiments):
        generations_to_nasty = run_experiment(fitness_fn, quiet=True)
        results.append(generations_to_nasty)
        if generations_to_nasty != MAX_GENERATIONS:
            print("Experiment #{}: Super Nasty Variant evolved in {} generations".format(experiment, generations_to_nasty))
        else:
            print("Experiment #{}: Super Nasty Variant never evolved".format(experiment))
    print("On average, the variant showed up at generation {}".format(mean(filter(lambda r: r is not None, results))))

In this model, "mutations" are just random amino acid substitutions:

ERROR_RATE = 1e-3 # 1/1000 chance per amino acid to replace it with a random one

def random_letter():
    return chr(ord("A")+random.randint(0, 26))

def maybe_mutate(virus):
    # random substitutions
    newvirus = virus
    
    for i in range(len(newvirus)):
        if random.random() < ERROR_RATE:
            # mutate this position
            newvirus = newvirus[:i] + random_letter() + newvirus[i+1:]
    return newvirus

If each of the individual 3 substitutions (X->B, Y->A, Z->D) required to get from the existing type to the Super Nasty Type confers a small advantage on its own...

SINGLE_SUBSTITUTION_FITNESS_GAIN = 1.05 # 5% advantage per substitution

BASE_FITNESS = 0.50001 # just a biiit above steady state...

def fitness_normal(virus):
    num_mutations = 0
    if virus[0] == "B": num_mutations += 1
    if virus[1] == "A": num_mutations += 1
    if virus[2] == "D": num_mutations += 1

    return BASE_FITNESS * pow(SINGLE_SUBSTITUTION_FITNESS_GAIN, num_mutations)

then within a few thousand generations, the Super Nasty Variant usually shows up:

run_many_experiments(fitness_normal, num_experiments=50)
Experiment #0: Super Nasty Variant evolved in 1241 generations
Experiment #1: Super Nasty Variant evolved in 442 generations
Experiment #2: Super Nasty Variant evolved in 2245 generations
Experiment #3: Super Nasty Variant evolved in 432 generations
Experiment #4: Super Nasty Variant evolved in 324 generations
Experiment #5: Super Nasty Variant evolved in 2128 generations
Experiment #6: Super Nasty Variant never evolved
Experiment #7: Super Nasty Variant never evolved
Experiment #8: Super Nasty Variant evolved in 437 generations
Experiment #9: Super Nasty Variant evolved in 435 generations
Experiment #10: Super Nasty Variant evolved in 2282 generations
Experiment #11: Super Nasty Variant evolved in 1179 generations
Experiment #12: Super Nasty Variant evolved in 2802 generations
Experiment #13: Super Nasty Variant never evolved
Experiment #14: Super Nasty Variant evolved in 1586 generations
Experiment #15: Super Nasty Variant evolved in 180 generations
Experiment #16: Super Nasty Variant evolved in 1589 generations
Experiment #17: Super Nasty Variant evolved in 447 generations
Experiment #18: Super Nasty Variant evolved in 1154 generations
Experiment #19: Super Nasty Variant evolved in 2522 generations
Experiment #20: Super Nasty Variant evolved in 2864 generations
Experiment #21: Super Nasty Variant evolved in 479 generations
Experiment #22: Super Nasty Variant evolved in 2289 generations
Experiment #23: Super Nasty Variant evolved in 3444 generations
Experiment #24: Super Nasty Variant evolved in 1355 generations
Experiment #25: Super Nasty Variant evolved in 270 generations
Experiment #26: Super Nasty Variant evolved in 766 generations
Experiment #27: Super Nasty Variant evolved in 2741 generations
Experiment #28: Super Nasty Variant evolved in 548 generations
Experiment #29: Super Nasty Variant evolved in 1571 generations
Experiment #30: Super Nasty Variant evolved in 607 generations
Experiment #31: Super Nasty Variant evolved in 2030 generations
Experiment #32: Super Nasty Variant evolved in 1845 generations
Experiment #33: Super Nasty Variant evolved in 820 generations
Experiment #34: Super Nasty Variant evolved in 264 generations
Experiment #35: Super Nasty Variant evolved in 1435 generations
Experiment #36: Super Nasty Variant never evolved
Experiment #37: Super Nasty Variant evolved in 4584 generations
Experiment #38: Super Nasty Variant evolved in 960 generations
Experiment #39: Super Nasty Variant evolved in 878 generations
Experiment #40: Super Nasty Variant evolved in 306 generations
Experiment #41: Super Nasty Variant evolved in 988 generations
Experiment #42: Super Nasty Variant evolved in 352 generations
Experiment #43: Super Nasty Variant evolved in 486 generations
Experiment #44: Super Nasty Variant evolved in 892 generations
Experiment #45: Super Nasty Variant evolved in 658 generations
Experiment #46: Super Nasty Variant evolved in 4847 generations
Experiment #47: Super Nasty Variant evolved in 4615 generations
Experiment #48: Super Nasty Variant never evolved
Experiment #49: Super Nasty Variant evolved in 2146 generations
On average, the variant showed up at generation 1829.3

But if at least 2 mutations must occur together to get a fitness gain...

def fitness_new(virus):
    num_mutations = 0
    if virus[0] == "B": num_mutations += 1
    if virus[1] == "A": num_mutations += 1
    if virus[2] == "D": num_mutations += 1

    # now, without at least 2 mutations, it's no better than no mutations:
    if num_mutations < 2: num_mutations = 0
        
    return BASE_FITNESS * pow(SINGLE_SUBSTITUTION_FITNESS_GAIN, num_mutations)

... it's much rarer (and slower) for the variant to evolve in the first place, even though it's just as bad when it does show up.

run_many_experiments(fitness_new, num_experiments=50)
Experiment #0: Super Nasty Variant never evolved
Experiment #1: Super Nasty Variant evolved in 4135 generations
Experiment #2: Super Nasty Variant never evolved
Experiment #3: Super Nasty Variant never evolved
Experiment #4: Super Nasty Variant never evolved
Experiment #5: Super Nasty Variant never evolved
Experiment #6: Super Nasty Variant never evolved
Experiment #7: Super Nasty Variant evolved in 1162 generations
Experiment #8: Super Nasty Variant never evolved
Experiment #9: Super Nasty Variant never evolved
Experiment #10: Super Nasty Variant never evolved
Experiment #11: Super Nasty Variant never evolved
Experiment #12: Super Nasty Variant never evolved
Experiment #13: Super Nasty Variant never evolved
Experiment #14: Super Nasty Variant never evolved
Experiment #15: Super Nasty Variant evolved in 2569 generations
Experiment #16: Super Nasty Variant never evolved
Experiment #17: Super Nasty Variant evolved in 2209 generations
Experiment #18: Super Nasty Variant never evolved
Experiment #19: Super Nasty Variant evolved in 4961 generations
Experiment #20: Super Nasty Variant never evolved
Experiment #21: Super Nasty Variant never evolved
Experiment #22: Super Nasty Variant evolved in 4375 generations
Experiment #23: Super Nasty Variant never evolved
Experiment #24: Super Nasty Variant never evolved
Experiment #25: Super Nasty Variant evolved in 1390 generations
Experiment #26: Super Nasty Variant never evolved
Experiment #27: Super Nasty Variant never evolved
Experiment #28: Super Nasty Variant never evolved
Experiment #29: Super Nasty Variant never evolved
Experiment #30: Super Nasty Variant never evolved
Experiment #31: Super Nasty Variant evolved in 1398 generations
Experiment #32: Super Nasty Variant never evolved
Experiment #33: Super Nasty Variant never evolved
Experiment #34: Super Nasty Variant evolved in 2539 generations
Experiment #35: Super Nasty Variant never evolved
Experiment #36: Super Nasty Variant never evolved
Experiment #37: Super Nasty Variant never evolved
Experiment #38: Super Nasty Variant never evolved
Experiment #39: Super Nasty Variant never evolved
Experiment #40: Super Nasty Variant evolved in 2509 generations
Experiment #41: Super Nasty Variant never evolved
Experiment #42: Super Nasty Variant evolved in 4194 generations
Experiment #43: Super Nasty Variant never evolved
Experiment #44: Super Nasty Variant never evolved
Experiment #45: Super Nasty Variant never evolved
Experiment #46: Super Nasty Variant never evolved
Experiment #47: Super Nasty Variant never evolved
Experiment #48: Super Nasty Variant never evolved
Experiment #49: Super Nasty Variant never evolved
On average, the variant showed up at generation 4528.82
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment