Scalable DNA algorithms – Scalmazene

The size of the instances that current experimental settings can solve by DNA assembly is very limitted (typically < 10). This is due to two limiting factors: an important error rate (~1/10.000), and the difficulty to generate enough significantly different strands for the reaction to be selective. In this project, we propose an experimental setting to break this scalability barrier by allowing to solve instance several orders of mangnitude larger. We will focus on solving graph algorithms, namely maze solving. The framework that we will implement in wetlab, relies on a small fixed number of strands or complexes, independent of the size of the input. Furthermore, we use a combination of randomness and determinism so that every error will be reversible until a correct solution is found. This will increase significantly the success rate at a very moderate cost (a slow down proportional to the size of the instance).