Graph-based Methods for the Design of DNA Computations

摘要: DNA computing is a rapidly evolving field utilizing molecules instead of silicon-based electronic units to perform calculations. The reliability such computations strongly depends on the sequences that represent information. Recently, thermodynamic constraints, based free energy hybridization between pairs single strands, are considered as most reliable criterion compose sequences. purpose this thesis provide contribution finding for encoding entities in mathematical problems. developed methods make use nearest neighbor model biological fundament. modelling method uses graph theory. work addresses following issues. first one evaluation encoding. performance predeveloped published sets vitro differs particular follow distinct models, since intended reactions not same. models using an principle proposed by Adleman [2] imply interactions, taken into account modern strand design applications. Therefore, comprising additional restrictions proposed, order more accurately assess candidate these models. performed with respect and allows find weak spots set words. second issue prediction pair strands. This comprises secondary structure DNA/DNA complex minimal (MFE), which usually referred MFE problem. effective solution problem main prerequisites thermodynamically sequence design. Contemporary thermal stability biomolecular complexes utilize paradigm dynamic programming energetically optimal complex. In work, novel developed. Based this, two proposed. compared currently used task. An concerns basic problems algorithmic Namely, all-pairs shortest path paths weight each nodes graph. There was memory saving technique calculations case bipartite graphs. It transformation matrix rules tropical (min-plus) algebra.