HyperMu’NmGA
Do you have questions or comments about this model? Ask them here! (You'll first need to log in.)
HyperMu'NmGA
*** Effect of Hypermutation Cycles in a NetLogo Minimal Genetic Algorithm ***
WHAT IS IT?
We have previously developed a simple genetic algorithm, its aim was to search for the solution to an elementary arithmetic problem (Leuci, 2020). This model is here modified to explore the effect of a mutator gene and the consequent entrance into a hypermutation state. The phenomenon has a particular concern in the case of tumorigenesis and in a more general way, in cells and tissues submitted to chronic environmental or genomic stress (Leuci, 2017). Nevertheless, the instance is still debated. To shed light on these themes we have designed this model assuming the following statements:
- mutator genes come from an impairment process of genes involved in genome stabilization;
- mutator phenotype is a quantitative character and it can assume positive or negative values: when it is negative it protects against mutations, on the contrary, when positive it enhances the probability of mutations; in the first case they can act as some protooncogenes, able to protect against mutagenesis, repairing DNA mismatch; in the second case they can act as some oncogenes that enhance mutagenesis and tumorigenesis; (Sherr, 2004)
- mutator genes can act on themselves leading toward a more severe mutagenic activity or toward a reversion (triggering a hypermutations cycle).
The model was mainly inspired by the studies of Taddei et al. (1997) and Sniegowski et al. (1997); they led their research on asexually reproducing cells (E. coli) engaged in adaptation experiments. This model allows for simulate also the influence of homologous recombination in the control of mutators element diffusion; this second feature is related to sexual reproduction maintenance, which is another debated issue in evolutionary biology (Becks L, Agrawal AF, 2012; Melián CJ et al. 2012; Raynes Y et al. 2011).
HOW IT WORKS
Every agent (turtle) owns a “chromosome” representing a candidate solution to the assigned problem. The chromosomes are made up of a string of digits, each one representing a "gene"; genes can mutate and, if the population includes sexual turtles, chromosomes can recombine exchanging fragments (sequence of genes) with the chromosome carried by another turtle. So the best answer is searched fundamentally in two steps: mutation and selective reproduction of (part of) the fittest chromosome. Mutations happen randomly with a given frequency altered, if any, by the presence of another genetic element that is the mutator gene: it can enhance or suppress the mutation rate on the chromosome.
Reproduction is selective and involves the most performing agents; it can happen in two alternative ways, named "sexual" and "asexual". Sexual reproduction is linked to a recombination event that takes place between a randomly chosen turtle (recipient) and the most performing one (donor) that offers a fragment of its chromosome to the first one; the two turtles taking part in this process will be highlighted by a link. Recombination leads to the formation of a new hybrid chromosome made up of the chromosome of the recipient turtle where a fragment of genes (i.e. digits) included between two randomly chosen loci, is replaced by the corresponding sequence copied by the donor turtle's chromosome. In asexual reproduction, the mutation is the unique source of variability and the donor turtle (i.e. one of the best performers) clones entirely its genome into a recipient turtle.
A more detailed description of the model can be found in the ODD-protocol.
HOW TO USE IT
SETUP button creates the selected number of turtles set by TURTLES-NUMBER slider. Each of them carries one chromosome constituted by a string long of no more than 20 genes, as chosen by the user, through the GENES-NUMBER slider. Initially, all chromosomes show low suitability.
SEARCH buttons launch a block of instructions that after the detection of the current best and worst chromosomes, recall the recombination and mutation operators. There are two kinds of search buttons: SEARCH runs one cycle only; SEARCH/STOP runs the program indefinitely; the same button is useful to stop a run.
Input Tools
Sliders:
TURTLES-NUMBER: set the number of turtles and consequently the number of chromosomes;
GENES-NUMBER: set the number of genes along one chromosome; each gene can store a digit (from 0 to 9);
BASIC_MUTATION-RATES: set the level of environmental mutagenicity acting on a single gene;
HyM-RATIO could be seen as the genome fraction occupied by regulative elements (mutator, mateswitch, mutatorswitch)
Mu-EXPRESSIVITY represents the strength of mutators' genes.
Choosers:
FITNESS-FUNCTION: in the "string-value" mode, it computes the numerical value of the chromosomal strings; in the "hamming" mode it computes the Hamming proximity to the optimal chromosomal string. The fitness range is different as a consequence of the selected fitness function: it is between 10^(genes-number - 1) and 10^genes-number - 1 for string-value mode; it is between 0 and genes-number for hamming mode.
REPRODUCE: it can assume three alternative values: sexual, asexual, and sex/asex; the first one leads to a recombination event, and the second one leads to the cloning of the entire genome of one of the best-performing turtles into another turtle. The two modes can coexist in a turtles population ("sex/asex" mode); in a mixed population, the sex gene can mutate but not recombine (in order to maintain balanced the reproductive diversity of the populations).
MUTATE_BY: it offers four different mutation ways. "simple mutagenesis" is the conventional name for a process producing only one point-mutations on a structural gene; the frequency of simple mutagenesis is constant. If mutagenesis does not follow a "simple" way, the mutations weight can mutate for each turtle: the default value is 1: in this case, the mutator allele produces just point mutations; when it will be lower than 1 the mutator allele behaves as an "antimutator"; when it is higher than 1 he mutator allele behaves as a "multimutator" producing more point mutations (as many as the whole part of its numerical value); mutations can beat mutator itself, leading toward hypermutation. In this case, the chooser offers three options "additive mutator" makes the mutator gene act on itself as an additive factor that randomly increases or decreases itself operating as an algebraic addend; on the contrary, "multiplicative mutator" acts on itself as an algebraic coefficient. The third mode allows the coexistence of both mutational modes in the turtles' population.
Output Tools
Monitors:
- BEST FITNESS displays the current best candidate solution (chromosome string);
- AV.MU displays the current mean of mutator genes value inside the turtles' population;
- MIN.M displays the lowest average of mutators' values recorded during one experiment;
- MAX.M displays the highest average of mutators' values recorded during one experiment;
Plots:
- CHROMOSOMES FITNESS plots the variation of the best and the worse chromosome
- % REPRODUCTION plots the percentage of asexually and sexually reproducing turtles
- % MUTATORS plots the percentage of additive and multiplicative mutating turtles
- MUTATORS DISTRIBUTION is a histogram showing the distribution of the mutator genes values between 15 and -15.
Output:
- a display shows some relevant notes about the state of one experiment.
THINGS TO NOTICE
The genes along the chromosome should be considered as structural genes, because they all codify for a candidate solution to the problem. Regulative genes are not located along the chromosome.
When HyM-RATIO is null hypermutation cycles are suspended that is mutator genes do not mutate and their activity does not undergo to variation
During reproduction (sexual, asexual, or both) the turtle that is taken as the recipient one is always a randomly chosen turtle (not necessarily the worst performing).
The code includes some stop conditions calibrated for experiments led with BASIC_MUTATION-RATES 5E-6, TURTLES-NUMBER 85, GENES-NUMBER 12.
- In presence of mutator genes, often their frequency and activity can increase, so it is interesting to follow their fate after the best solution is reached; in this case, the experiment is stopped when the average value of the mutator genes is reduced by 30% with respect to the default value (i.e. 1); but if this condition is not reached at 500000 ticks after the problem solution, muatators’ value reduction is considered potentially endless and the experiment is stopped.
- If the mean of mutators genes value is under one and the ticks number is more than 750000 in the condition we have used in our experiments program the experiment execution is stopped because the evolutive potential is very low and is unlikely an ultimate solution could be found.
- If mutator genes are not active, the experiment ends when the best solution is reached.
THINGS TO TRY
A first step could be to search the relationship between the BASICMUTATION-RATE (environmental mutagenicity) and the TICKS' number you need to get the optimal solution under "simple mutagenesis" setting, with or without recombination; the range of BASICMUTATION-RATE values could be set between 1E-8 and 1E-4: indeed, according to Peck, K. M. and Lauring A. S. (2018) DNA viruses typically have mutation rates on the order of 1E-8 to 1E-6 substitutions per nucleotide site per cell infection, RNA viruses are genetically more unstable having mutation rates on the order of 1E-6 to 1E-4 substitutions per nucleotide site per cell infection.
A second step could be to check the effectiveness of the different kinds of selective reproduction. It looks like nature favourites sexual reproduction but it is still debated why. A hypothesis is that the role of sexual reproduction and homologous recombination is to pack favourable traits and unfavourable traits into distinct genomes, so that selection can act more rapidly and more precisely (Lensky, 2001).
During adaptation processes, an important stage could be the emergence of the mutator or antimutator phenotypes and the consequent adjustment of the mutation rate operated by selection; this feature shows a particular interest when occurs under stress (Hoffmann and Hercus, 2000). If it is allowed to replace a biological challenge with a computational one, the model would offer a set of tools to design a plan of experiments to study the different kinds of emerging dynamics.
EXTENDING THE MODEL
The model could be extended in order to study the mutator genes' behaviour and the reproduction mode in the background of a more challenging problem-solving process.
RELATED MODELS
- Leuci, Cosimo (2017). “Starfish Planet” (Version 3) Info Tab. NetLogo Modeling Commons. http://modelingcommons.org/browse/one_model/4949#model_tabs_browse_nlw
- Leuci, Cosimo (2020, January 30). “MGA - Minimal Genetic Algorithm” (Version 1.1.0). CoMSES Computational Model Library. Retrieved from: https://doi.org/10.25937/db7w-zt41
CREDITS AND REFERENCES
Becks, L., Agrawal, A.F. (2012, May) "The Evolution of Sex Is Favoured During Adaptation to New Environments". PLoS Biol. 10 (5): e1001317. https://doi.org/10.1371/journal.pbio.1001317
Hoffmann, A.A., and Hercus, M.J. (2000, March) "Environmental Stress as an Evolutionary Force" BioScience, 5 (3): 217-226. https://doi.org/10.1641/0006-3568(2000)050[0217:ESAAEF]2.3.CO;2
Lensky, R.E.(2001, October 19) Come Fly, and Leave the Baggage Behind" Science 294 (5542): 533-534. https://doi.org/10.1126/science.1066241
Melián CJ, Alonso D, Allesina S, Condit RS, Etienne RS (2012, March) "Does Sex Speed Up Evolutionary Rate and Increase Biodiversity?" PLoS Comput. Biol. 8(3): e1002414. https://doi.org/10.1371/journal.pcbi.1002414
Peck, K. M. and Lauring A. S. (2018, July) "Complexity of viral mutation rates" Journal of Virology vol. 92 (14): e01031-17. https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6026756/pdf/e01031-17.pdf
Raynes Y, Gazzara M R, Sniegowski P D (2011, June 07) "Mutator dynamics in sexual and asexual experimental populations of yeast" BMC Evolutionary Biology 11: 158 http://www.biomedcentral.com/1471-2148/11/158
Sherr, C. J. (2004, January 23) "Principles of Tumor Suppression" Cell, 116: 235–246. https://doi.org/10.1016/S0092-8674(03)01075-4
Sniegowski, P., Gerrish, P. and Lenski R. (1997, June) "Evolution of high mutation rates in experimental populations of E. coli" Nature 387: 703–705. https://doi.org/10.1038/42701
Taddei, F., Radman, M., Maynard-Smith, J., Toupance, B., Gouyon, P. H., and Godelle, B. (1997, June) "Role of mutator alleles in adaptive evolution" Nature 387: 700–702. https://doi.org/10.1038/42696
Wilensky, U. (1999). NetLogo. http://ccl.northwestern.edu/netlogo/. Center for Connected Learning and Computer-Based Modeling, Northwestern Institute on Complex Systems, Northwestern University, Evanston, IL.
COPYRIGHT AND LICENSE
Copyright 2022 Cosimo Leuci.
This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike 3.0 International License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc-sa/3.0/ or send a letter to Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.
Comments and Questions
;; _______________________________________________________________________________________________________________ ;; ;; -------------------- HyperMu'NmGA --------------------------------------------------------- HyperMu'NmGA ;; HyperMu'NmGA --------------------------------------------------------- HyperMu'NmGA --------------------- ;; _______________________________________________________________________________________________________________ globals [best_result ;; the numerical value of the chromosome closer to the solution worst_result ;; the numerical value of the chromosome more distant from the solution eureka-time ;; the ticks elapsed to find the optimal solution eureka! ;; binary variable turning on when the optimal solution has just reached reduction-time;; the ticks required to get a 30% reduction of the mutator genes values average donor ;; the turtle having the best chromosome recipient ;; a random turtle different from the donor chromcopy ;; the copy of the chromosome carried by the donor turtle mutcopy ;; the copy of the mutaror gene carried by the donor turtle mate_swcopy ;; the copy of the mate_switch gene carried by the donor turtle mutator_swcopy;; the copy of the mutator_switch gene carried by the donor turtle max-mut.av ;; the highest mutators average value recorded before the problem solution min-mut.av ;; the lowest mutators average value recorded before the problem solution a-split ;; the position of one extreme in a donor's chromosome fragment b-split ;; the position of the second extreme a in a donor's chromosome fragment counter ;; a counter usefull in different blocks ] turtles-own [chromosome ;; a string of digits representing a candidate solution to the problem mutator ;; a gene able to impact positively or negatively on the genetic stability of the ;; chromosome and of itself; its strength is quantified by a whole number mutator_switch;; a gene able to determine the mutation mode; mate_switch ;; a gene able to determine the reproduction mode; ;; it harbours a binary variable: 0 for asexual reproduction, 1 for sexual reproduction fitness ;; the numerical value of the chromosomal strings (if string-value fitness-function mode) ;; or the Hamming distance complement (i.e. the proximity) to the best chromosomal ;; string (if hamming fitness-function mode) ] ;; ---------- SETUP PROCEDURES ------------------------------------------------------------------------------- ;; --------------------------------------------------------------------------------------------------------------- to setup ;; reset parameters and create a number of turtles set by the user clear-all set counter 0 reset-ticks create-turtles turtles-number [ set shape "circle 2" set size 2.3 fd random 15 genotype/fenotype-construction ] message0 set eureka-time 0 end to genotype/fenotype-construction ;; the genotype (chromosome) and the corresponding phenotype (fitness) of the turtle are initially equal to the ;; first answer that is usually given by children to the problem: "what is the greatest number of n digits?" set fitness 10 ^ (genes-number - 1) ;; the initial formal fitness value is converted into a string: it will be the chromosome structure set chromosome word fitness "" set label chromosome ;; chromosome is displayed as label ;; in the "hamming" mode, the fitness function is replaced by the complement of the Hamming distance ;; (i.e. the "Hamming proximity") to the optimal solution if fitness-function = "hamming" [compute-fitness] set mutator 1 set max-mut.av 1 set min-mut.av 1 ;; defining mate_switch gene if reproduction = "asexual" [set mate_switch 0] if reproduction = "sexual" [set mate_switch 1] if reproduction = "sex/asex" [set mate_switch random 2] ;; defining mutator_switch gene if mutate_by = "simple mutagenesis" [set mutator_switch -1] if mutate_by = "additive mutator" [set mutator_switch 0] if mutate_by = "multiplicative mutator" [set mutator_switch 1] if mutate_by = "both mutators" [set mutator_switch random 2] end ;; ---------- RUNTIME PROCEDURES ----------------------------------------------------------------------------- ;; --------------------------------------------------------------------------------------------------------------- to search ask turtles [move] ;; thew worse and the best fitness value are detected set worst_result min [fitness] of turtles set best_result max [fitness] of turtles ;; a message is sent to output when the optimal solution is reached (the solutions are differently detected ;; depending on the chosen fitness function) if eureka-time = 0 and (best_result = 10 ^ genes-number - 1 or best_result = genes-number) [ set eureka-time ticks set eureka! 1 message1 if mutate_by = "simple mutagenesis" [stop] ] ;; max-mut.av and min-mut.av are recorded before the optimal solution is reached if eureka-time = 0 [ if max-mut.av < mean [mutator] of turtles [set max-mut.av mean [mutator] of turtles] if min-mut.av > mean [mutator] of turtles [set min-mut.av mean [mutator] of turtles] ] ;; other STOP conditions if eureka-time > 0 [set reduction-time ticks - eureka-time] if eureka-time > 0 and mean [mutator] of turtles < 0.7 [message2 stop] if eureka-time = 0 and ticks >= 750000 and max [mutator] of turtles < 1 [message3 stop] if eureka-time > 0 and min [mutator] of turtles >= 1.5 and reduction-time > 500000 [message4 stop] ;; two alternative kinds of selective reproduction are admitted: sexual and asexual ;; they take place if the diversity between all chromosomes is not null clear-links if best_result != worst_result [ set donor [who] of one-of turtles with [fitness = best_result] set chromcopy [chromosome] of turtle donor set mutcopy [mutator] of turtle donor set mate_swcopy [mate_switch] of turtle donor set mutator_swcopy [mutator_switch] of turtle donor set recipient [who] of one-of turtles with [fitness != best_result] ask turtle donor [ create-link-to turtle recipient if mate_switch = 0 [cloning] if mate_switch = 1 [recombination] ] ] ;; mutations occur randomly, the frequency is related to the basic mutation-rate (the mutagenicity ;; of the environment) and the total gene number of turtles population if random-float 1 < basic_mutation-rate * turtles-number * (genes-number + 3) [ask one-of turtles [mutation] ] tick set eureka! 0 end ;; TALK TO ME! --------------------------------------------------------------------------------------------------- to message0 output-print "*** HyperMu'NmGA ***" output-print " " end to message1 output-print " OPTIMAL SOLUTION" output-print " reached on " output-print word " tick: " eureka-time end to message2 output-print " " output-print " Mutators mean went" output-print " down 30% under the" output-print " starting value after" output-type " ticks: " output-type reduction-time end to message3 output-print " " output-print " Low evolutive" output-print " potential" end to message4 output-print " " output-print " No mutator < 1.5" output-print " possible endless" output-print " hypermutation status" end ;; GOOD VIBRATIONS ----------------------------------------------------------------------------------------------- to-report patches-ahead [rad dis] ; reports to turtles a set of patches ahead report [patches in-radius rad] of patch-ahead dis end to move ifelse (any? other turtles-on patches-ahead 1 1) [ bk 1 lt random-float 360] [fd 0.001] end ;; Operator 1. FITNESS FUNCTIONS ;; ---------------------------------------------------------------------------------------------------------------- to compute-fitness set fitness 0 set counter 0 if fitness-function = "hamming" [hamming-proximity] if fitness-function = "string-value" [ set fitness read-from-string chromosome] set label chromosome end to hamming-proximity if counter = length chromosome [set counter 0 stop] if item counter chromosome = "9" [ set fitness fitness + 1 ] set counter counter + 1 hamming-proximity end ;; Operator 2. REPRODUCTION ;; ---------------------------------------------------------------------------------------------------------------- to cloning ask turtle recipient [ set chromosome chromcopy set mutator mutcopy set mutator_switch mutator_swcopy set mate_switch mate_swcopy compute-fitness ] end to recombination ;; homologous recombination occurs between the chromosome of a randomly chosen turtle (recipient) and the ;; chromosome of (one of) the most performing one (donor) that offers a code's fragment of its chromosome ;; to the first turtle; the two involved turtles will be highlighted by a link set counter 0 set a-split random genes-number set b-split random genes-number ask turtle recipient [ hybridization compute-fitness] end to hybridization ;; the two selected chromosomal strings give place to hybridization according to a mechanism ;; similar to the crossing-over following to bacterial conjugation; strings are looped, ;; as occur usually in bacterial chromosomes or plasmids ifelse a-split < b-split [set chromosome replace-item (a-split + counter) chromosome (item (a-split + counter) chromcopy) set counter (counter + 1) if counter < b-split - a-split [hybridization]] [if b-split < a-split [set chromosome replace-item ((a-split + counter) mod genes-number) chromosome (item ((a-split + counter) mod genes-number) chromcopy) set counter (counter + 1) if counter < genes-number - a-split + b-split [hybridization]] ] ;; if required, the three donor's regulative genes are transferred into the recipient turtle if reproduction = "sex/asex" [set mate_switch 1] if mutate_by != "simple mutagenesis" [ if random-float 1 < hym-ratio [set mutator mutcopy] if mutate_by = "both mutators" [if random-float 1 < 0.5 [ set mutator_switch mutator_swcopy] ] ] end ;; Operator 3: MUTAGENESIS ;; ---------------------------------------------------------------------------------------------------------------- to mutation ;; simple mutagenesis doesn't involve mutator genes ifelse mutate_by = "simple mutagenesis" [point-mutation compute-fitness if reproduction = "sex/asex" [ ;; mutation of the reproduction mode if random-float 1 < 0.5 [set mate_switch ((mate_switch + 1) mod 2)] ] ] ;; hypermutation can produce a mutation of a structural gene as well as a mutation on the mutator gene; ;; the last one determines the mutation number along the chromosome: it can be 0, 1 or more (multimutation) [if random-float 1 > hym-ratio [multimutation compute-fitness] if random-float 1 < hym-ratio [hypermutation] ;; when the population is reproductively heterogeneous, also the mate_switch gene can mutate if reproduction = "sex/asex" [ if random-float 1 * mutator * mu-expressivity > hym-ratio [ set mate_switch ((mate_switch + 1) mod 2)] ;; mutation of the reproduction mode ] ;; when the population is mutationally heterogeneous, also the mutator_switch gene can mutate if mutate_by = "both mutators" [ if random-float 1 * mutator * mu-expressivity > hym-ratio [ set mutator_switch ((mutator_switch + 1) mod 2)] ;; mutation of the mutator mode ] ] end to point-mutation ;; point-mutations hit randomly only one gene set chromosome replace-item random genes-number chromosome word random 10 "" end to multimutation ;; the multimutations imply different point-mutations in a unique mutation event ;; the number of contemporary point-mutations is determined by the variable stored in the mutator-gene ifelse mutator < genes-number * 4 [repeat mutator [point-mutation]] ;; if the mutator value is too high (more than four times the number of the chromosome genes) in order to avoid ;; overflow events, the number of point-mutations is cut to four times the number of chromosome genes [repeat genes-number * 4 [point-mutation] ] end to hypermutation ;; mutator gene can mutate itself in two alternative ways (additive or multiplicative, decided by ;; mutator_switch gene), the self-mutation effect can be modulated also by the mutator-expressivity parameter set mutator mutator + (random 3 - 1) * mutator ^ mutator_switch * mu-expressivity end
There are 7 versions of this model.
Attached files
File | Type | Description | Last updated | |
---|---|---|---|---|
HyperMu’NmGA.png | preview | HyperMu-Reflection | almost 5 years ago, by Cosimo Leuci | Download |
READ_ME.txt | data | attachment | almost 2 years ago, by Cosimo Leuci | Download |