Directed Acyclic Graph-Based Technology Mapping of Genetic Circuit Models

As
engineering foundations such as standards and abstraction begin
to mature within synthetic biology, it is vital that genetic design
automation (GDA) tools be developed to enable synthetic biologists
to automatically select standardized DNA components from a library
to meet the behavioral specification for a genetic circuit. To this
end, we have developed a genetic technology mapping algorithm that
builds on the directed acyclic graph (DAG) based mapping techniques
originally used to select parts for digital electronic circuit designs
and implemented it in our GDA tool, iBioSim. It is among the first
genetic technology mapping algorithms to adapt techniques from electronic
circuit design, in particular the use of a cost function to guide
the search for an optimal solution, and perhaps that which makes the
greatest use of standards for describing genetic function and structure
to represent design specifications and component libraries. This paper
demonstrates the use of our algorithm to map the specifications for
three different genetic circuits against four randomly generated libraries
of increasing size to evaluate its performance against both exhaustive
search and greedy variants for finding optimal and near-optimal solutions.