Optimal Part and Module Selection for Synthetic Gene Circuit Design Automation

An
integral challenge in synthetic circuit design is the selection
of optimal parts to populate a given circuit topology, so that the
resulting circuit behavior best approximates the desired one. In some
cases, it is also possible to reuse multipart constructs or modules that have been already built and experimentally
characterized. Efficient part and module selection algorithms are
essential to systematically search the solution space, and their significance
will only increase in the following years due to the projected explosion
in part libraries and circuit complexity. Here, we address this problem
by introducing a structured abstraction methodology and a dynamic
programming-based algorithm that guaranties optimal part selection.
In addition, we provide three extensions that are based on symmetry
check, information look-ahead and branch-and-bound techniques, to
reduce the running time and space requirements. We have evaluated
the proposed methodology with a benchmark of 11 circuits, a database
of 73 parts and 304 experimentally constructed modules with encouraging
results. This work represents a fundamental departure from traditional
heuristic-based methods for part and module selection and is a step
toward maximizing efficiency in synthetic circuit design and construction.