DNA assembly and recombination for hamiltonian paths and binary words

摘要

We present a new and simple encoding of the edges of a directed graph in DNA molecules that adds on a high flexibility to the design of the initial library for problems like the Hamiltonian path problem. This encoding allows assembly of sequences by sticky ends, by overlapping assembly and by bridges. The edges are encoded in two not complementary strands and the fragmentation and reassembly of subpaths is possible. We also describe a process for reading the vertices present in a strand based on the length of the restriction fragments generated after cutting with a restriction enzyme. Our encoding can be transformed easily to the more general encoding of binary words. The overlapping assembly serves to construct the library (paths or words) and, in conjunction with a restriction enzyme, serves to recombine subpaths or binary words respectively.