In the past few years, several articles have been devoted to the study of molecular computing based on DNA in order to implement the algorithm to solve some NP-complete problems and simulate logic gates in silicon-based computers. A great deal of effort has been made on using DNA to implement simple logic gates, such as simple 1-bit comparators and simple adders, or to solve NP-complete problems, such as the Hamiltonian path problem, the traveling salesperson problem and the satisfiability problem. All of the methods rely on the capability of DNA computing which could perform computation in huge parallelism to produce all possible solutions where the answer may be derived from. In this thesis, we will first design a full bit-serial comparator that can perform the feedback operation. Then, we will design a word-parallel bit-serial sorter which uses our comparators as the elementary building components. Our design of sorters can be applied to any sorting network, such as bitonic sorter and odd-even merge sorter.

This paper presents a novel MEMS based DNA computer for solving SAT problems. No time-consuming sample preparation procedures and delicate sample applying equipment were required for the computing process. Moreover, experimental results show the bound DNA sequences can sustain the chemical solutions during computing processes such that the proposed method shall be useful in dealing with large scale problems. An algorithm based on a modified sticker model accompanied with a state-of-the-art MEMS-based microarray experiment is demonstrated to solve SAT problem which has long served as a benchmark in DNA computing. Unlike conventional DNA computing algorithms need an initial data pool to cover all correct and incorrect answers and further execute a series of separation procedures to destroy the unwanted ones, we built solutions in parts to satisfy one clause in one step, and eventually solve the entire Boolean formula through steps. Accordingly this algorithm greatly reduces the formation of unnecessary candidate solutions and shall be very practical as problem size grows. In this study, a novel MEMS-based technology including utilizing blank mask as the microarray substrate to prevent the self-fluorescent effect, a twin-mask back-side exposure process to improve the computing speed and a low-temperature backing process to prevent DNA damage during computing procedure. In addition, the minimal time requirement for DNA hybridization was also evaluated experimentally. The paper reports a novel computing method for solving SAT problem utilizing a state-of-art MEMS-based microarray. The advantage of this method is as the problem size scales up, it only needs to linearly increase the variety of sequences standing for variables and augment the array size. Therefore, while solving a complicated SAT problem, the numbers of DNA sample and the time for the computing process can be dramatically reduced with this approach.

Microfluidic devices are emerging as an attractive technology for automatically orchestrating the reactions needed in a biological computer. Thousands of microfluidic primitives have already been integrated on a single chip, and recent trends indicate that the hardware complexity is increasing at rates comparable to Moore's Law. As in the case of silicon, it will be critical to develop abstraction layers--such as programming languages and Instruction Set Architectures (ISAs)--that decouple software development from changes in the underlying device technology.Towards this end, this paper presents BioStream, a portable language for describing biology protocols, and the Fluidic ISA, a stable interface for microfluidic chip designers. A novel algorithm translates microfluidic mixing operations from the BioStream layer to the Fluidic ISA. To demonstrate the benefits of these abstraction layers, we build two microfluidic chips that can both execute BioStream code despite significant differences at the device level. We consider this to be an important step towards building scalable biocomputers.

Durante las dos últimas décadas ha surgido una colaboración estrecha entre informáticos, bioquímicos y biólogos moleculares, que ha dado lugar a la investigación en un área conocida como la computación biomolecular. El trabajo en esta tesis pertenece a este área, y estudia un modelo de cómputo llamado sistema de empalme (splicing system). El empalme es el modelo formal del corte y de la recombinación de las moléculas de ADN bajo la influencia de las enzimas de la restricción.Esta tesis presenta el trabajo original en el campo de los sistemas de empalme, que, como ya indica el título, se puede dividir en dos partes. La primera parte introduce y estudia nuevos modelos finitos de empalme. La segunda investiga aspectos de complejidad (tanto computacional como descripcional) de los sistema de empalme. La principal contribución de la primera parte es que pone en duda la asunción general que una definición finita, más realista de sistemas de empalme es necesariamente débil desde un punto de vista computacional. Estudiamos varios modelos alternativos y demostramos que en muchos casos tienen más poder computacional. La segunda parte de la tesis explora otro territorio. El modelo de empalme se ha estudiado mucho respecto a su poder computacional, pero las consideraciones de complejidad no se han tratado apenas. Introducimos una noción de la complejidad temporal y espacial para los sistemas de empalme. Estas definiciones son utilizadas para definir y para caracterizar las clases de complejidad para los sistemas de empalme. Entre otros resultados, presentamos unas caracterizaciones exactas de las clases de empalme en términos de clases de máquina de Turing conocidas. Después, usando una nueva variante de sistemas de empalme, que acepta lenguajes en lugar de generarlos, demostramos que los sistemas de empalme se pueden usar para resolver problemas. Por último, definimos medidas de complejidad descriptional para los sistemas de empalme. Demostramos que en este respecto los sistemas de empalme finitos tienen buenas propiedades comparados / Over the last two decades, a tight collaboration has emerged between computer scientists, biochemists and molecular biologists, which has spurred research into an area known as DNAComputing (also biomolecular computing). The work in this thesis belongs to this field, and studies a computational model called splicing system. Splicing is the formal model of the cutting and recombination of DNA molecules under the influence of restriction enzymes.This thesis presents original work in the field of splicing systems, which, as the title already indicates, can be roughly divided into two parts: 'Finite models of splicing' on the onehand and 'their complexity' on the other. The main contribution of the first part is that it challenges the general assumption that a finite, more realistic definition of splicing is necessarily weal from a computational point of view. We propose and study various alternative models and show that in most cases they have more computational power, often reaching computational completeness. The second part explores other territory. Splicing research has been mainly focused on computational power, but complexity considerations have hardly been addressed. Here we introduce notions of time and space complexity for splicing systems. These definitions are used to characterize splicing complexity classes in terms of well known Turing machine classes. Then, using a new accepting variant of splicing systems, we show that they can also be used as problem solvers. Finally, we study descriptional complexity. We define measures of descriptional complexity for splicing systems and show that for representing regular languages they have good properties with respect to finite automata, especially in the accepting variant.

Recently, DNA computing is one of powerful tools that can be designed for solving NP-complete problems. The powers of DNA computing are that it has great ability of massive data storage and it can process those data in parallel. Some of hard problems, such as the traveling salesperson problem and the Hamiltonian cycle problem, have been solved with the brute force method in DNA computing. After DNA computing is performed, all feasible solutions for the problem are stored implicitly in the tubes. However, the correct answer still cannot be extracted or reported absolutely, because that the concentration of the correct solutions might be lower than other bad solutions. In this paper, we will increase the concentration of the correct answer for fault-tolerant ability.

In this paper I describe and extend a new DNA computing paradigm introduced in Blumberg for building massively parallel machines in the DNA-computing models described by Adelman, Cai et. al., and Liu et. al. Employing only DNA operations which have been reported as successfully performed, I present an implementation of a Connection Machine, a SIMD (single-instruction multiple-data) parallel computer as an illustration of how to apply this approach to building computers in this domain (and as an implicit demonstration of PRAM equivalence). This is followed with a description of how to implement a MIMD (multiple-instruction multiple-data) parallel machine. The implementations described herein differ most from existing models in that they employ explicit communication between processing elements (and hence strands of DNA).

In this paper I present a new model that employs a biological (specifically DNA -based) substrate for performing computation. Specifically, I describe strategies for performing parallel function application in the DNA-computing models described by Adelman, Cai et. al., and Liu et. al. Employing only DNA operations which can presently be performed, I discuss some direct algorithms for computing a variety of useful mathematical functions on DNA, culminating in an algorithm for minimizing an arbitrary continuous function. In addition, computing genetic algorithms on a DNA substrate is briefly discussed.

Previous research on DNA computing has shown that DNA algorithms are useful to solve some combinatorial problems, such as the Hamiltonian path problem and the traveling salesman problem. The basic concept implicit in previous DNA algorithms is the brute force method. That is, all possible solutions are created initially, then inappropriate solutions are eliminated, and finally the remaining solutions are correct or the best ones. However, correct solutions may be destroyed while the procedure is executed. In order to avoid such an error, we recommend combining the conventional concepts of DNA computing with a heuristic optimization method and apply the new approach to design strategies. In this thesis, we present a DNA algorithm based on ant colony optimization (ACO) for solving the traveling salesman problem (TSP). Our method manipulates DNA strands of candidate solutions initially. Even if the correct solutions are destroyed during the process of filtering out, the remaining solutions can be reconstructed and correct solutions can be reformed. After filtering out inappropriate solutions, we employ control of melting temperature to amplify the surviving DNA strings proportionally. The product is used as the input and the iteration is performed repeatedly. Accordingly, the concentration of correct solutions will be increased. Our results agree with that obtained by conventional ant colony optimization algorithms and are better than that obtained by genetic algorithms. The same idea can be applied to design methods for solving other combinatorial problems with DNA computing.

It has been previously shown that DNA computing can solve those problems currently intractable on even the fastest electronic computers. The algorithm design for DNA computing, however, is not straightforward. A strong background in both the DNA molecule and computer engineering are required to develop efficient DNA computing algorithms. After Adleman solved the Hamilton Path Problem using a combinatorial molecular method, many other hard computational problems were investigated with the proposed DNA computer. The existing models from which a few DNA computing algorithms have been developed are not sufficiently powerful and robust, however, to attract potential users. This thesis has described research performed to build a new DNA computing model based on various new algorithms developed to solve the 3-Coloring problem. These new algorithms are presented as vehicles for demonstrating the advantages of the new model, and they can be expanded to solve other NP-complete problems. These new algorithms can significantly speed up computation and therefore achieve a consistently better time performance. With the given resource, these algorithms can also solve problems of a much greater size, especially as compared to existing DNA computation algorithms. The error rate can also be greatly reduced by applying these new algorithms. Furthermore, they have the advantage of dynamic updating, so an answer can be changed based on modifications made to the initial condition. This new model makes use of the huge possible memory by generating a ``lookup table'' during the implementation of the algorithms. If the initial condition changes, the answer changes accordingly. In addition, the new model has the advantage of decoding all the strands in the final pool both quickly and efficiently. The advantages provided by the new model make DNA computing an efficient and attractive means of solving computationally intense problems.

Interactions between DNA molecules can be used to perform computation. These DNA computing systems often use DNA molecules as freely diusing reactants in a well-mixed solution. We demonstrate how DNA walkers tethered to an origami-templated track can perform computation. A DNA walker can block a track that intersects with its own, preventing another walker from stepping down this blocked track. These blockages are primitive operations that can be used to perform computation. This thesis demonstrates how blocking interactions between DNA walkers can evaluate formulae posed in propositional logic. When anchorages in the track are viewed as networked machines and the DNA walker is viewed as a coordinated message passed between them, DNA walker circuits can be modelled as a distributed system. Techniques from formal veri- cation can be used to check this system for errors, determining the probability with which the system will end up in a certain state. This forms the basis of a compiler that can automatically design a DNA walker circuit that evaluates a given propositional formula within a specied error tolerance. To show how DNA walker circuits can be simplied, we create a propositional logic system called blocking logic that is proven to be both sound and complete. DNA walker circuits can be implemented and measured experimentally by using fluorescence spectrophotometry to track the position of a walker on the track. To demonstrate proof of principle, circuits were built that implement NOT and NOR operators. To make these circuits operate with minimal error, dierent sources of possible error were investigated and quantied. Cumulatively, the novel contributions that this thesis makes to the eld are: • the experimental design and implementation of a DNA computing system that uses DNA walkers, • probabilistic model checking software that automatically designs these DNA walker circuits, • a propositional logic system that can simplify a DNA walker circuit to an equivalent circuit that uses fewer tracks.