Design of a flexible component gathering algorithm for converting cell-based models to graph representations for use in evolutionary search
In both solutions, a direct connection was made between the cut response to regeneration of the missing region, head or tail, respectively. Although each search found a solution to the experiment at hand, the solutions were limited in their flexibility to respond to other permutations. As expected, neither network was capable of solving the reverse problem as their was no selective pressure in the evolutionary search. Nonetheless, these results show that our evolutionary search process is capable of finding solutions using our connected component analysis to convert cell-based individuals into graphs, which are compared with the appropriate target extracted from the PlanformDB using the graph edit difference evaluation metric.
The inflexible network solutions emphasize the importance of searching for solutions using rigorous fitness criteria and why an automated approach is necessary. Future experiments will target networks that are capable of handling both anterior and posterior ablations. Simulation snapshots contain a detailed description of the current state of the simulation, including a list of all cells, their location, shape, genomes, metabolic equations, environmental conditions, and the concentration of all resources. Thus, snapshots provide much richer information about the cells and individuals than the graph formalism and will provide opportunities to develop additional fitness metrics to complement graph edit distance in the future.
One of the challenges in the biological sciences is the development of new methods for data visualization and integration to provide informative and predictive insight into the scientific process. Computer models hold great promise in this area, but often involve significant human interaction and time. In this study, we laid the foundation for a system of automated model discovery and development that incorporates shape-based experimental data from a repository of documented experiments. Graphs are a powerful and convenient means of describing morphological data. Using comparison methods, such as the graph difference evaluation, one can easily search such a database for results that are similar or identical. We showed that the utility of the graph difference evaluation could be further extended as a fitness evaluation metric during evolutionary search. This method was combined with a cell-based modeling platform to model basic regeneration of the planarian flatworm. Agent-based models are particularly amenable to this approach as they are tractable to simulated experimental manipulations combined with fully emergent outcomes. The ability to automate these behaviors fits nicely into an automated discovery system that can be driven by a genetic algorithm search engine. Furthermore, simulators that include robust visualization capabilities make it very convenient for the scientist to evaluate or experiment on a set of search results.
Planarian worms provide an excellent model system for developing such an automated search process due to the plethora of experimental data in the literature, and now available in a curated database (PlanformDB). However, the principles inherent in this design are extensible to any system where shape is an integral component of the observable outcomes. That said, developing model discovery systems that automatically incorporate experimental data is a general and attainable goal that is not limited to systems dependent upon morphological data.The challenge of describing phenotypic outcomes based upon morphological characteristics is challenging for biological systems and cell-based computational models alike. We showed that converting cell-based simulation output into graphs can be achieved using a component gathering algorithm that identifies regions and their juxtaposition to each other and converts them into nodes joined by linkages. The resulting graphs can be stored to a database and easily reconstructed later and/or compared with other graphs using algorithms such as the graph edit distance. These comparisons and the resulting metric were incorporated into an evolutionary search where the genetic algorithm retrieved its target morphology from a data repository of experimental outcomes and used the graph edit distance as a fitness metric to drive development. Using a small population size of 30 individuals, our mutation and crossover frequencies were sufficient to generate a solution state in as few as 19 generations for the experiments shown in Figure 6(a).
The method for converting a simulation snapshot to a graph formulation works well, and the converted morphologies reflected shape and positions of body regions relative to each other in space. The graph-based fitness function thus accurately distinguishes the shapes of different morphologies, but does have difficulty predicting which morphology will more likely regenerate into the target morphology. To improve the effectiveness of our graph-based fitness function, future work will seek to automate the optimization of the graph edit costs to not only reflect the shapes of individuals, but also to favor morphologies that are more likely to regenerate into the target individual. The optimization of graph edit costs needs to be automated since tweaking graph edit costs allows one to achieve a more accurate graph comparison for some cases, but there is no perfect parameter assignment that covers all cases, and so it should be chosen depending on the needs and design of the experiment.
Future work will also develop additional morphological based fitness functions to act side by side with the graph edit distance fitness function. This will allow researchers to choose from among multiple morphological fitness operators, possibly combining the output of several evaluators instead of assigning a fitness value based on one fitness function evaluation.
Cellsim is an agent-based modeling platform whose principle agents are cellular in nature. These cells and their behaviors are rooted in biology as the environment, interactions, metabolism, and signaling networks are designed based upon biological primitives. Cells are capable of proliferating, growing, dividing, dying, and regulating metabolic and genetic networks in response to changes in their local environment, including cell interactions and signaling. As a result, cells have emergent properties as they are autonomous, evolvable, exhibit inheritance, and are contingent upon their neighbors. Another important feature of this system is its ability to be automated and manipulated using a genetic algorithm search engine [17].
The versatile genetic algorithm associated with Cellsim was expanded as part of this work and includes many parameters to customize the common elements of a genetic algorithm, such as number of crossovers, mutation rates, selection criteria, and population size.
Formally, to transform the morphology graph g1 into graph g2, a sequence of operations (the edit path) must be performed [23,24]. The edit distance between two graphs is defined as the minimum cost edit path that transforms graph g1 into graph g2 as represented in Equation 2.
where P(g1,g2) is the set of edit paths that transform graph g1 into g2, c is the edit cost function and e i denotes an edit operation. Generally speaking, determining the graph edit distance requires that we examine the set of paths that transform g1 to g2 and calculate the path costs for each. This is non-trivial but can be achieved in an optimally efficient manner using the A* best-first search algorithm [26].
The graph edit distance calculation has been adapted for comparing planaria graph representations. A list of edit operations and an example of the corresponding costs used in this paper are given in Table 1.
For simplicity, we are working with worms whose graph representations are devoid of organs for this analysis, but will include them in later experiments.
The minimal path cost between two graphs g1 and g2 is found using the A* search algorithm. The possible edit paths can be viewed as forming a tree, where the edges of the tree are individual edit operations and the nodes are graphs. The inner nodes of the tree correspond to partially edited graphs, and the leaf nodes represent complete edit paths, all of which terminate at the target graph. The search for the minimal edit path starts with one of the graphs, say g1, as the root of the tree, and defines the possible branches from this node to be all possible single edit operations that could be applied to the original graph g1. At each step of the A* search, the algorithm expands (explores) the branch of the tree that leads to a node on the search frontier that has the minimum estimated total path cost. The minimum estimated total path cost is derived from the sum of the cost of the edits required to reach the node being expanded from the root, plus an estimate of the total cost of the edits required to reach the goal state (graph g2) from the node being expanded. The algorithm terminates the first time it expands the goal state, as the path that it finds at this point is guaranteed to be optimal.
Tim Andersen and Jeff Habig are former employees of Crowley Davis Research who developed the Cellsim platform, but are no longer associated with the company in any way and declare no financial interest or conflict of interest for themselves or any other authors. Crowley Davis Research is not directly involved in this project.
Component gathering design, development, and analysis (MB, NC, and TA). Modeling, network design, and genetic algorithm searches (JH). Experimental design and interpretation (JH, TA, and ML). Graph-edit distance evaluation and live planarian experiments (DL). Manuscript preparation (MB, JH, and TA). All authors read and approved the final manuscript.
We would like to thank past and present employees of Crowley Davis Research for their hard work on the Cellsim platform and for making it available for these studies. This work was made available through an NSF-CDI grant(EF-1124665 and EF-1124651).