Optimal methods of encoding information for DNA computing.

摘要

Biomolecular computing is a field that studies biologically-based computational paradigms alternative to the traditional electronic ones. The strategy of DNA computing is to encode data in DNA strands and to apply molecular biology tools to perform arithmetic and logic operations. We look at the question of managing errors that arise in DNA-based computation, presenting several solutions to the problem of erroneous bio-computations from the perspective of formal language techniques. The objective of the thesis is the investigation of optimal methods of encoding information in DNA in a way that reduces errors associated with DNA computing.;The DNA strands used for computation need to have certain characteristics in order to avoid data loss and erroneous results. One source of problems comes from DNA code segments attaching to each other in unexpected ways and, as a result, making them unsuitable for computation. In this thesis we analyze the properties that guard against such phenomena and study the sets of sequences that ensure that no unwanted bindings occur during computation.;Another contribution of the thesis is the study of mathematical properties of languages used for encoding of data in DNA. Certain biological operations which can be performed on DNA sequences can be mathematically modelled as operations on words. This portion of the thesis is devoted to the study of such word operations and related language equations using formal language theory techniques.;Another aspect of DNA computing is rooted in the problem of building reliable systems out of unreliable components. Prior to construction of functional and practical computational devices with DNA, it is inevitable that they will be preceded by more simplistic and restricted mechanisms of limited reliability. Discovering how to combine the components of moderate reliability into larger systems with a desired reliability is key to the extension of computing capacity. For this purpose, finite automata can be viewed as an abstraction of a biocomputing process. This thesis investigates the construction of reliable finite automata from component finite automata that do not correctly accept their intended languages.;This thesis is based on articles [45], [53], third chapter of [28], as well as [48] and [49].;Keywords: theoretical DNA computing, DNA encodings, codes, language equations, formal languages.