Catálogo de publicaciones - libros

This chapter suggests new directions in both graph theory and DNA self-assembly. The general problem faced here is the following: given a set P of paths and cycles, a set of forbidden structures, and a set of enforced structures, what are the graphs included in the set G() for = (, P, )? The model presented focuses in particular on DNA self-assembly and the set of structures obtained through this process. However, the idea of graph forbidding-enforcing systems can certainly be extended to other self-assembly processes in nature, as well as to the pure theoretical methods used to study the mathematical properties of graphs. In the case of DNA self-assembly, the evolution process is described in a very natural way as an increase in the cardinality of the matching set between vertices with complementary labels. For other types of applications, the concept of g-f-e systems may need to be adjusted in a different way that will be more suitable for simulating the evolution in those particular processes.

Taking into account the fact that the labels of the vertices are strings over a finite alphabet, one can consider theoretical questions in the context of formal language theory. It may be interesting to investigate the classes of graphs generated by a g-f-e system where the labels of belong to a given language taken from one of the Chomsky classes. On the other hand, considering finite languages and investigating how the structure of generated graphs depends on the g-f-e system could be useful in the study of cellular processes, where, for example, the function of signal transduction nets is fairly well understood.

We presented here an algorithm that, given a combinatorial set and parameter , predicts the secondary structures with lowest minimum free energies in the combinatorial set. When the number of words in each set of the overall input-set is considered to be a constant, our algorithm runs in () time. In our algorithms, given a combination , we look at the minimum free energy structure only. Extensions of these problems would be to find suboptimal structures (i.e. whose free energy is greater than the MFE), or to consider pseudoknots. Another problem for future work would be to find an algorithm with better running time, for example ( + ).

Self-assembly of nanostructures through template-matching hybridization reactions is potentially an important technique in nanotechnology. Given the possibility of errors in hybridization and the difficulty of designing DNA sequences on conventional computers, a viable alternative is to manufacture libraries of oligonucleotides for nanotechnology applications in the test tube. Thus, a protocol has been designed and tested to select mismatched oligonucleotides from a random starting material. Experiments indicate that the selected oligonucleotides are independent, and that there are about 10 000 distinct sequences. Such manufactured libraries are a potential enabling resource for DNA self-assembly in nanotechnology.