Scalable Enumeration of Pareto-optimal Polymers for Computing Equilibrium Concentrations

In the microscopic world of engineered biology, scientists are building complex machines out of DNA. These are not the long, twisting strands that carry genetic code in our cells, but short, synthetic pieces designed to snap together in specific patterns. When these pieces meet, they bind to one another, forming larger structures called complexes. The goal is to create systems that can perform logic, sense their environment, or assemble into specific shapes, much like a molecular factory. However, predicting how these systems behave is incredibly difficult. While a designer might start with a small set of DNA pieces, the laws of chemistry allow these pieces to combine in countless ways, creating an infinite number of possible structures. Some of these structures are the intended products, but many are accidental byproducts that clog the system or cause it to fail. To ensure these molecular machines work as planned, researchers must understand which structures will form and in what quantities when the system reaches a state of balance, known as equilibrium.

For decades, scientists have relied on computer programs to model these interactions, but these tools struggle when the systems become large. They operate by checking every possible way the DNA pieces could connect, a task that becomes impossible when the number of combinations explodes. A new approach, developed by researchers at the University of Texas at Austin and the Korea Advanced Institute of Science and Technology, offers a way to cut through this complexity without losing accuracy. Instead of trying to list every possible structure, the team focused on a specific, smaller group of structures that are thermodynamically stable. They proved that the vast majority of accidental, unstable structures are so unlikely to appear in a balanced system that they can be safely ignored. By filtering out these unlikely candidates, they reduced an infinite problem to a finite one, making it possible to analyze systems that were previously too large to study.

The researchers began by defining a concept they call Pareto-optimality. In simple terms, a structure is Pareto-optimal if it cannot be broken apart into smaller, independent pieces without breaking a chemical bond. If a large complex can be split into two separate parts that do not need to stick to each other, it is considered unstable. The laws of physics favor the split version because it creates more separate units, which increases disorder, or entropy, a key driver in chemical reactions. The team demonstrated mathematically that these unstable, split-able structures never appear in the most stable, lowest-energy state of a system. Furthermore, even in a real-world scenario where conditions are not perfectly ideal, the total amount of these unstable structures is so small compared to the stable ones that they have a negligible effect on the overall outcome. This finding allowed the researchers to discard the infinite sea of impossible or unlikely structures and focus only on the finite set of stable, Pareto-optimal polymers.

To find these stable structures, the team turned to a branch of mathematics known as the Hilbert basis. This method allows them to identify the fundamental building blocks of a system from which all other valid structures can be derived. In the past, this mathematical tool was only used for systems where every possible bond was forced to form, a scenario that does not reflect the messy reality of DNA chemistry where bonds can be weak or incomplete. The researchers extended this method to handle these more realistic, unsaturated conditions. They showed that the set of all stable structures corresponds exactly to a specific set of mathematical solutions, proving that the number of relevant structures is finite and can be calculated. However, even with this reduction, calculating the full set for large systems remained too slow for practical use. The number of calculations required grew so rapidly that it would take years to finish for a moderately complex system.

To solve this speed problem, the team introduced a strategy based on limiting the size of the structures they looked for. They reasoned that in many engineered systems, the most important structures are not made of every possible type of DNA piece available, but rather a smaller subset. They developed an algorithm that looks for stable structures containing no more than a specific number of different DNA types, a parameter they call the support bound. Instead of checking every possible combination of these types, which would still be too many, they used a clever mathematical technique called a covering design. This technique acts like a sieve, selecting a small, strategic set of groups to test. By running the complex calculations only on these selected groups, they could reconstruct the full set of relevant structures for the whole system without having to do the heavy lifting for every single possibility.

The effectiveness of this method was tested on several families of DNA systems described in recent scientific literature, including linear chains and tree-like structures of logic gates. In one test involving a chain of seven modules, the new method calculated the relevant structures in just 24 seconds. A direct, brute-force calculation of the same system took over 1,000 seconds, and for larger systems, the direct method would have taken hours or days, if it could be done at all. The researchers found that by setting the limit on the number of DNA types to a modest number, they recovered nearly all the structures that mattered for the system's behavior. The few structures they missed were so rare that they did not change the predicted outcome of the system. This approach allowed them to perform detailed leakage analysis, checking how much unintended product formed when inputs were removed, a task that was previously impossible for systems with more than a few modules.

The work provides a practical path forward for designing complex molecular systems. By combining a thermodynamic justification for ignoring unstable structures with a scalable algorithm that uses mathematical sieving, the researchers have made it possible to analyze DNA systems that were previously out of reach. Their method does not require the system to be perfect or the bonds to be strong; it works even when the chemistry is weak and incomplete. The ability to trade a small amount of theoretical completeness for a massive gain in speed gives engineers a new tool to verify their designs before building them in the lab. As the field of DNA computing moves toward larger and more intricate machines, this ability to efficiently predict equilibrium concentrations will be essential for ensuring that these molecular devices function as intended.