Evolutionary Graph Dynamics

User Interface of the Program:

This is an Visualized Microbe Evolving Simulation Based on Evolutionary Dynamics.
As demonstrated in the implementation section and in the test results, the project successfully implemented all designed models and a fully compliant evolutionary process. For ease of use, the software supports the user to easily modify the values in the user interface and view the data generated by the model evolution process.

In nature, organisms undergo neutral or non-neutral mutations in their genes when they reproduce. Mutations in an individual may spread to the entire population or disappear. The process is influenced by both natural selection and random drift. Nevertheless, evolution is not entirely beneficial, as in the case of cancer, where malignant cells multiply and normal cells die. Based on evolutionary graph dynamics and in order to investigate the effects of different population structures on evolution, this project abstracts the structure of biological populations and the evolutionary process, using computers to construct simulations of different evolutionary models and their evolutionary processes. By using the modelling implemented in this project, the effects of different population structures on the rate of evolution are explored.

1. Software Design

   1. Components of the System

In the UML diagram above it can be seen visually that the program is divided into the following components to implement the different functions.
a. GridGenerator:
Used to implement the Square Lattice structure
b. MyGraph: Graph information class
c. MyGraphMain:
The starter component for starting the whole project
d. MyGraphUtil: Set as graph tool
e. MyGraphView:
used to generate and set up the user interface
f. MyThread:
In this component, the project overrides the thread run method so that different structures have their own threads.
g. MyUtil:
Integrates several functional components such as:
-Generation of weights
-Determining whether an input value is a decimal or a number

  2. Data structures and algorithms

The project plans to use the methods provided in GraphStream to generate and store the nodes, edges, and the structure graph of the population structure graph due to the need to store the node types to better distinguish between mutant and resident.
This library uses both Array and HashMap data structure type for the storage of the nodes and edges. It makes it easier to manipulate the graph data, generating nodes and edges by invoking the methods in GraphStream.
In order to distinguish between the mutant and resident in the population structure, the project will use the MAP data structure to facilitate the storage of node-type data from the graph.
More generally, the project plans to create Map-type data structures for each node to make it easier to determine the type of individual.

Design Algorithms:

a. Weighted Randomization algorithm:
Implements random selection after weighting of edges b. Square construction algorithm:
dynamically constructs graphs based on the number of rows and columns entered by the user c. Suppressed graph construction algorithm:
dynamically constructs graphs based on the number of individuals entered by the user
d. Star graph construction algorithm:
dynamically constructs graphs based on the number of individuals entered by the user
e. Super Star construction algorithm:
dynamically constructs graphs based on the number of individuals entered by the user
f. Fixation probability algorithms:
Fixed probability algorithms for different population structures based on evolutionary dynamics are implemented in code and displayed on the page
g. Actual fixed probability algorithm:
Calculates fixation probabilities for the actual evolved results and displays them on the page to compare with the actual fixed probabilities

2. Implementation:

1. Population Structure Implementation

1. Implement Square Lattice Structure Graph

2. Implement Burst Structure Graph

3. Implement Star Structure Graph

The star structure is analogous to the Burst structure, but the star structure is not a single-root graph.
In contrast, each vertex on the periphery of the star structure has outgoing edges pointing to the central node. In such a case, the central node is no longer the cold node.
Natural selection will be amplified, whereas the burst structure will suppress natural selection and amplify the effects of genetic drift.

The code implementation for the star structure is based on the implementation block for the Burst Structure, as indicated in the figure. For constructing the star structure, this code block also uses FOR loop to generate periphery nodes. In each loop, a periphery node is generated and add two directed edges at the same time: One pointing from that node to the central node, and one is pointing from the central node to that node.

4. Implement Super Star Structure Graph

It can be seen that the connections between nodes in the superstar structure in evolutionary graph dynamics are complex but not irregular. A clever solution is to think of the Super Star structure as a 'blade'. After a single blade has been generated, Using FOR loop repeat to generate the blades. Such complex shapes can be completed in this way. The core of implementing a superstar structure is how to implement a blade. The blade generation is inspired by breadth search, first adding the first layer of cold blue nodes and the edges from the centre point to the cold blue nodes. After generating all the nodes in the first layer, the hot node in the second layer is added, along with edges pointing from the cold node in the first layer to that hot node. Eventually, the edges pointing from the hot node to the centre are added. This approach is made more evident in the code.

After the implementation of one blade, the idea of generating the Super Star Structure became apparent: a for loop was added to generate the five blades as shown in the Super Star Structure illustration repeatedly. As the number of points and edges in the superstar structure is relatively dense, this project uses the CSS style setting method provided by GraphStream to adjust the style of the generated structure, making it look more exciting and intuitive.

3. Evaluation:

In addition to functional testing of the software implementation, the reliability of the models was also an important metric to be achieved in this project.
Therefore, after the models were constructed, Model Tests were applied to each model to check the accuracy of the model. This is a bit like black box testing.
Research in theoretical biology gives formulas for calculating the Fixation probability of the evolution of the corresponding population structure.
For different types of population structure, the relevant studies point to the following probability of their mutants producing a lineage that takes over the entire population.

The final code used to implement the superstar structure is shown in the diagram. Unlike the default use of straight edges and other styles, the structure is displayed as shown in the diagram after the CSS style is applied. ![Uploading image.png…]()

4. Conclusion:

1. For the software implementation component:
   As demonstrated in the implementation section and in the test results, the project successfully implemented all designed models and a fully compliant evolutionary process.
   For ease of use, the software supports the user to easily modify the values in the user interface and view the data generated by the model evolution process.
2. For the experiment component:
   The implementation of the experiments can be viewed in the “Implementation-Experiment implementation”.
   The results of the experiments show that different populations have different effects on evolution.
   The effects of natural selection on evolution are amplified in Square Lattice structures, Star structures and Superstar Structures: dominant mutant is more likely to propagate throughout the population.

Furthermore, the experimental results show that:

For the same Population Size and one Mutant with same Mutant Fitness, the effect of these structures in amplifying natural selection is ranked as follows:

Superstar Structures > Star structures > Square Lattice structures

Moreover, amazingly, The Burst Structure is suppressing natural selection.
Regardless of the fitness of the mutant individuals in the experimental data, the Evolutionary Rate of the population is approximately 1/N:

Mutation propagates back to the entire population only when the central node is selected. This show that the evolutionary process of Burst Structure is affected by random drift.