We propose a biochemically plausible mechanism for constructing digital logic signals and gates of significant complexity within living cells. These mechanisms rely largely on co-opting existing biochemical machinery and binding proteins found naturally within the cell, replacing difficult protein engineering problems with more straightforward engineering of novel combinations of gene control sequences and gene coding regions. The resulting logic technology, although slow, allows us to engineer the chemical behavior of cells for use as sensors and effectors. One promising use of such technology is the control of fabrication processes at the molecular scale. / DARPA/ONR Ultrascale Computing Program under contract N00014-96-1-1228 and by the DARPA Embedded Computing Program under contract DABT63-95-C130.

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.

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.

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.

<p>Synthetic biology is an emerging technology field whose goal is to use biology as a substrate for engineering. Self-assembly is one of the many methods for fabricating such synthetic biosystems.</p><p>Self-assembly is a process where components spontaneously arrange themselves into organized aggregates by the selective affinity of substructures. DNA is an excellent candidate for making synthetic biological systems using self-assembly because of its modular structure and simple chemistry. This thesis describes several</p><p>techniques which use DNA as a nano-construction material and</p><p>explores the computational capabilities of DNA self-assembly.</p><p>For this dissertation, I set out to build a biomolecular computing device with several</p><p>useful properties, including compactness, robustness, high degrees of complexity, flexibility, scalability and easily characterized yields</p><p>and convergence rates. However, a unified device that satisfies all these properties is still many years away. Instead, this thesis presents designs, simulations,</p><p>and experimental results for several distinct DNA nano-systems, as</p><p>well as experimental protocols, each of which satisfies a subset of the above-mentioned properties. The hope is that the lessons learned from building all these biomolecular computational devices would bring us closer to our ultimate goal and would eventually pave the path for a computing device that satisfies all the properties. We experimentally demonstrate how we can reduce errors in tiling assembly using an optimized set of physical parameters. We propose a novel DNA tile design</p><p>which enforces directionality of growth, reducing assembly errors. We build simulation models to characterize damage in fragile nanostructures under the impact of various external forces. Furthermore, we investigate reversible computation as a means to provide self-repairability to such damaged structures.</p><p>We suggest two modifications of an existing DNA computing device,</p><p>called Whiplash PCR machine, which allow it to operate robustly outside of controlled laboratory conditions and allow it to implement a simple form of inter-device communication. We present analysis techniques which characterize the yields and time convergence of self-assembled DNA nanostructures. We also present an experimental demonstration of a novel DNA nanostructure which is capable of tiling the plane and could prove to be a way of building 3D DNA assemblies.</p> / Dissertation

<p>The manufacturing of molecular-scale computing systems requires a scalable, reliable, and economic approach to create highly interconnected, dense arrays of devices. As a candidate substrate for nanoscale logic circuits, DNA self-assembled nanostructures have the potential to fulfill these requirements. However, a number of open challenges remain, including the scalability of DNA self-assembly, long-range signal propagation, and precise patterning of functionalized components. These challenges motivate the development of theory and experimental techniques to illuminate the connections among the physical, optical, and thermodynamic properties of DNA self-assembled nanostructures. </p> <p>In this thesis, three tools are developed, validated, and applied to study the thermo-mechanical properties of DNA nanostructures: 1) a method to quantitatively measure the quality of DNA grid self-assembly, 2) a spectrofluorometer capable of capturing fluorescence and absorbance data under simultaneous multi-wavelength excitation, and 3) a Monte Carlo simulator that models the ensemble response of DNA nanostructures as simple harmonic oscillators. </p> <p>The broad contributions of this dissertation are as follows: 1) insight into the thermo-mechanical properties of DNA grid nanostructures, and 2) a categorization of self-assembly defects and their impact on proposed logic circuits. </p> <p>The results of the work presented in this dissertation show that: 1) the quality of self-assembly of DNA grid nanostructures can be quantitatively calculated to demonstrate the impact of changes in temperature or structure, 2) the optical absorbance of complex DNA nanostructures can be modeled to capture their thermo-mechanical properties (i.e., worst case within 10% of experimental melting temperatures and 70% of experimental thermodynamic parameters), 3) the structural resilience of DNA nanostructures can be quantifiably improved by chemical cross-linking with up to 60% retaining their original structure, and 4) DNA self-assembly introduces structural defects which create new fault models with respect to conventional technologies for logic circuits.</p> / Dissertation

<p>This dissertation hypothesizes,</p><p><italic>"It is possible to design a self-assembled, nanoscale, high-speed, resonance energy transfer device exhibiting non-linear gain with a few molecules."</italic></p><p>The report recognizes DNA self-assembly, a relatively inexpensive and a massively parallel fabrication process, as a strong candidate for self-assembled RET systems. It successfully investigates into the design and simulations of a novel sequential self-assembly process employed to realize the goal of creating large, scalable, fully-addressable DNA nanostructure-substrate for future molecular circuitry. </p><p>As a pre-cursor to the final device modeling various RET wire designs for interconnecting nanocircuits are presented and their modeling and simulation results are discussed. A chromophore RET system using a biomolecular sensor as a proof-of-concept argument that shows it is possible to model and characterize chromophore systems as a first step towards device modeling is also discussed. </p><p>Finally, the thesis report describes in detail the design, modeling, characterization, and fabrication of the Closed-Diffusive Exciton Valve: a self-assembled, nanoscale (area of 17.34 nm<super>2</super>), high-speed (3.5 ps to 6 ps) resonance energy transfer device exhibiting non-linear gain using only 10 molecules, thus confirming the hypothesis. It also recognized improvements that can be made in the future to facilitate better device operation and suggested various applications.</p> / Dissertation

No description available.

In this thesis, we will discuss the construction of algorithms for solving Constraint Satisfaction Problems (CSPs), and describe two new ways of approaching them. Both approaches are based on the idea that it is sometimes faster to solve a large number of restricted problems than a single, large, problem. One of the strong points of these methods is that the intuition behind them is fairly simple, which is a definite advantage over many techniques currently in use. The first method, the covering method, can be described as follows: We want to solve a CSP with n variables, each having a domain with d elements. We have access to an algorithm which solves problems where the domain has size e &lt; d, and we want to cover the original problem using a number of restricted instances, in such a way that the solution set is preserved. There are two ways of doing this, depending on the amount of work we are willing to invest; either we construct an explicit covering and end up with a deterministic algorithm for the problem, or we use a probabilistic reasoning and end up with a probabilistic algorithm. The second method, called the partitioning method, relaxes the demand on the underlying algorithm. Instead of having a single algorithm for solving problems with domain less than d, we allow an arbitrary number of them, each solving the problem for a different domain size. Thus by splitting, or partitioning, the domain of the large problem, we again solve a large number of smaller problems before arriving at a solution. Armed with these new techniques, we study a number of different problems; the decision problems (d, l)-CSP and k-Colourability, together with their counting counterparts, as well as the optimisation problems Max Ind CSP, Max Value CSP, Max CSP, and Max Hamming CSP. Among the results, we find a very fast, polynomial space algorithm for determining k-colourability of graphs.

Aqueous droplets submerged in an oil-lipid mixture become enclosed by a lipid monolayer. The droplets can be connected to form robust networks of droplet interface bilayers (DIBs) with functions such as a biobattery and a light sensor. The discovery and characterization of an engineered nanopore with diode-like properties is enabling the construction of DIB networks capable of biochemical computing. Moreover, DIB networks might be used as model systems for the study of membrane-based biological phenomena. We develop and experimentally validate an electrical modeling approach for DIB networks. Electrical circuit simulations will be important in guiding the development of increasingly complex DIB networks. In cell membranes, the lipid compositions of the inner and outer leaflets differ. Therefore, a robust model system that enables single-channel electrical recording with asymmetric bilayers would be very useful. Towards this end, we incorporate lipid vesicles of different compositions into aqueous droplets and immerse them in an oil bath to form asymmetric DIBs (a-DIBs). Both α-helical and β-barrel membrane proteins insert readily into a-DIBs, and their activity can be measured by single-channel electrical recording. We show that the gating behavior of outer membrane protein G (OmpG) from Escherichia coli differs depending on the side of insertion in an asymmetric DIB with a positively charged leaflet opposing a negatively charged leaflet. The a-DIB system provides a general platform for studying the effects of bilayer leaflet composition on the behavior of ion channels and pores. Even with the small volumes (~100 nL) that can be used to form DIBs, the separation between two adjacent bilayers in a DIB network is typically still hundreds of microns. In contrast, dual-membrane spanning proteins require the bilayer separation to be much smaller; for example, the bilayer separation for gap junctions must be less than 5 nm. We designed a double bilayer system that consists of two monolayer-coated aqueous spheres brought into contact with each side of a water film submerged in an oil-lipid solution. The spheres could be brought close enough together such that they physically deflected without rupturing the double bilayer. Future work on quantifying the bilayer separation and studying dual-membrane spanning proteins with the double bilayer platform is planned.