Sequence Design for a Test Tube of Interacting Nucleic Acid Strands

We
describe an algorithm for designing the equilibrium base-pairing
properties of a test tube of interacting nucleic acid strands. A target
test tube is specified as a set of desired “on-target”
complexes, each with a target secondary structure and target concentration,
and a set of undesired “off-target” complexes, each
with vanishing target concentration. Sequence design is performed
by optimizing the test tube ensemble defect, corresponding to the
concentration of incorrectly paired nucleotides at equilibrium evaluated
over the ensemble of the test tube. To reduce the computational cost
of accepting or rejecting mutations to a random initial sequence,
the structural ensemble of each on-target complex is hierarchically
decomposed into a tree of conditional subensembles, yielding a forest
of decomposition trees. Candidate sequences are evaluated efficiently
at the leaf level of the decomposition forest by estimating the test
tube ensemble defect from conditional physical properties calculated
over the leaf subensembles. As optimized subsequences are merged toward
the root level of the forest, any emergent defects are eliminated
via ensemble redecomposition and sequence reoptimization. After successfully
merging subsequences to the root level, the exact test tube ensemble
defect is calculated for the first time, explicitly checking for the
effect of the previously neglected off-target complexes. Any off-target
complexes that form at appreciable concentration are hierarchically
decomposed, added to the decomposition forest, and actively destabilized
during subsequent forest reoptimization. For target test tubes representative
of design challenges in the molecular programming and synthetic biology
communities, our test tube design algorithm typically succeeds in
achieving a normalized test tube ensemble defect ≤1% at a design
cost within an order of magnitude of the cost of test tube analysis.