Completed Research Project · Accepted At DNA32
Scalable Enumeration of Pareto-optimal Polymers
A first-authored DNA molecular programming paper on turning an infinite candidate space of molecular complexes into a finite, thermodynamically justified, and computationally usable set for equilibrium analysis.
One-page abstract
Finite
infinite complexes to finite candidates
Algebraic
Hilbert-basis characterization
Fast
covering-design enumeration
Venue
DNA32 conference
Status
Accepted; publication forthcoming
Area
DNA computing and molecular programming
Authors
Archit Patil, Minki Hhan, David Soloveichik
Primary Materials
Technical Areas
Project Summary
Engineered DNA systems are now large enough that verification is a computational problem in its own right. Equilibrium solvers such as COFFEE need a finite list of candidate polymers, but in a domain-monomer system even a finite set of monomer types can generate infinitely many possible complexes.
This work defines Pareto-optimal polymers as the complexes that cannot be split into independent parts without losing potential bonding. That definition gives a thermodynamic reason to discard suboptimal candidates: the split has the same enthalpy and more entropy, so it is favored.
The paper then proves that the remaining candidate set is finite and characterizes it with a Hilbert basis computation. To make the characterization practical, the algorithm restricts the number of distinct monomer types in a polymer and uses covering designs to reduce the number of Hilbert-basis computations.
Core Contributions
Thermodynamic filter
Pareto-suboptimal polymers can split into non-interacting parts without losing bonds, so entropy favors the split.
Finite characterization
The Pareto-optimal set is exactly captured by projecting a Hilbert basis from an augmented neutralized system.
Scalable enumeration
Support bounds and covering designs replace one hard global computation with fewer tractable subsystem computations.
Empirical result
Benchmarks show order-of-magnitude speedups while preserving nearly all equilibrium-relevant candidates.
Why It Matters
Finiteness is not enough. The finite set has to be computable.
Direct Hilbert-basis computation can become impractical even on moderate DNA molecular programming systems. The covering-design method trades one large computation for a structured family of smaller computations, while still retaining the support-bounded Pareto-optimal polymers needed for downstream concentration and leakage analysis.
- Model
- Geometry-free domain-monomer systems generalizing Thermodynamic Binding Networks to an unsaturated setting.
- Key object
- Pareto-optimal polymers, the candidates that cannot be split into non-interacting parts without losing bonds.
- Algebraic result
- Projection of a Hilbert basis from an augmented system with unit monomers that neutralize dangling domains.
- Scalability idea
- Bound the number of distinct monomer types per polymer and use covering designs to cover all smaller supports efficiently.
Abstract PDF
The accepted one-page abstract is embedded below and is also available as a direct PDF.