A DNA-based Finite State Transducer
Résumé
Deoxyribonucleic acid (DNA) computing is an emerging eld wherein the biological properties of DNA are used to carry out computation. As DNA can also be used as a building material with movable parts, the combination of those two aspects allows scientists to design nanomachines easily. However, one main concerns is the lack of automation of existing mechanisms. This limits their potential applications as it is not possible to use nanomachines in a non- controlled environment that is, almost anything that is outside of a test tube. The goal of this work is thus to design a completely automated mechanism that will reduce the amount of operations required from the user. We have designed a nite state transducer that can eliminate the need to add control strands to the solution, one of the most common external operations. Our transducer uses polymerase to generate the output described by the input strands present in the solution. As it can work at a wide range of temperatures our transducer can facilitate the design of more complex nanomachines while making the ex- isting ones, that rely on control strands, more autonomous. Moreover, as it can generate a wide variety of outputs, our transducer can also be useful to DNA mechanisms that are computation-intensive. For example, with nondeterministic polynomial (NP)-complete problem solvers, it can generate test strands when needed instead of having all of them crowding the solution.