Genetic Technology Mapping with Directed Acyclic Graphs

View all posters

Nicholas Roehner, Chris J. Myers

University of Utah, United States

As engineering foundations such as standards and abstraction begin to mature within synthetic biology, one limiting factor for the design of more complex genetic networks will be the availability and effectiveness of genetic design automation (GDA) software tools. Ideally, a synthetic biologist could design genetic networks at a fairly high level of abstraction, focusing on a desired behavior rather than the DNA components used to implement said behavior. Such a synthetic biologist would use GDA tools to automatically map behavioral descriptions to standardized sets of DNA components, thereby decreasing the expert knowledge and time required during the design process. To this end, we have developed a genetic technology mapping algorithm to map from a model of a genetic network written in the Systems Biology Markup Language (SBML) to a parts library of SBML models that are annotated with DNA components written in the Synthetic Biology Open Language (SBOL). Our algorithm builds on directed acyclic graph-based (DAG-based) mapping techniques originally used to map electronic circuits and can be divided into three steps. First, the algorithm constructs regulatory graph representations of the given genetic network and parts library and partitions them into rooted DAGs. Second, the algorithm converts these DAGs to a canonical form and matches the library DAGs to each node in the network DAG. Lastly, matches are selected via dynamic programming and recursive backtracking to obtain the solution set of DNA components with the fewest base pairs. Backtracking is necessary since each selected match can lead to a non-minimal solution by precluding subsequent selection of minimal matches that also introduce genetic cross-talk. As backtracking can be computationally expensive, we will continue to explore heuristics for reducing average computation time such as bounding solution size with the best solution size found so far.