Harish Chandran

Estimating individual and average treatment effects from observational data is an important problem in many domains such as healthcare and e-commerce. In this paper, we advocate balance regularization of multi-head neural network architectures. Our work is motivated by representation learning techniques to reduce differences between treated and untreated distributions that potentially arise due to confounding factors. We further regularize the model by encouraging it to predict control outcomes… Show more

Estimating individual and average treatment effects from observational data is an important problem in many domains such as healthcare and e-commerce. In this paper, we advocate balance regularization of multi-head neural network architectures. Our work is motivated by representation learning techniques to reduce differences between treated and untreated distributions that potentially arise due to confounding factors. We further regularize the model by encouraging it to predict control outcomes for individuals in the treatment group that are similar to control outcomes in the control group. We empirically study the bias-variance trade-off between different weightings of the regularizers, as well as between inductive and transductive inference. Show less

DNA strand displacement circuits are powerful tools that can be rationally engineered to implement molecular computing tasks because they are programmable, cheap, robust and predictable. A key feature of these circuits is the use of catalytic gates to amplify signal. Catalytic gates tend to leak, that is, they generate output signal even in the absence of intended input. Leaks are harmful to the performance and correct operation of DNA strand displacement circuits. Here, we present "shadow… Show more

DNA strand displacement circuits are powerful tools that can be rationally engineered to implement molecular computing tasks because they are programmable, cheap, robust and predictable. A key feature of these circuits is the use of catalytic gates to amplify signal. Catalytic gates tend to leak, that is, they generate output signal even in the absence of intended input. Leaks are harmful to the performance and correct operation of DNA strand displacement circuits. Here, we present "shadow cancellation", a general-purpose technique to mitigate leak in catalytic DNA strand displacement circuits. Shadow cancellation involves constructing a parallel shadow circuit that mimics the primary circuit and has the same leak characteristics. It is situated in the same test tube as the primary circuit and produces "anti-background" DNA strands that cancel "background" DNA strands produced by leak. We demonstrate the feasibility and strength of the shadow leak cancellation approach through a challenging test case, a cross-catalytic feedback DNA amplifier circuit that leaks prodigiously. Shadow cancellation dramatically reduced the leak of this circuit and improved the signal-to-background difference by several folds. Unlike existing techniques, it makes no modifications to the underlying amplifier circuit and is agnostic to its leak mechanism. Shadow cancellation also showed good robustness to concentration errors in multiple scenarios. This work introduces a direction in leak reduction techniques for DNA strand displacement amplifier circuits, and can potentially be extended to other molecular amplifiers. Show less

DNA based nanostructures and devices are becoming ubiquitous in nanotechnology with rapid advancements in theory and experiments in DNA self-assembly which have led to a myriad of DNA nanodevices. However, the modeling methods used by researchers in the field for design and analysis of DNA nanostructures and nanodevices have not progressed at the same rate. Specifically, there does not exist a formal system that can capture the spectrum of the most frequently intended chemical reactions on DNA… Show more

DNA based nanostructures and devices are becoming ubiquitous in nanotechnology with rapid advancements in theory and experiments in DNA self-assembly which have led to a myriad of DNA nanodevices. However, the modeling methods used by researchers in the field for design and analysis of DNA nanostructures and nanodevices have not progressed at the same rate. Specifically, there does not exist a formal system that can capture the spectrum of the most frequently intended chemical reactions on DNA nanostructures and nanodevices which have branched and pseudo-knotted structures. In this paper we introduce a graph rewriting system for modeling DNA nanodevices. We define pseudo-DNA nanostructures ( PDNPDN s), which describe the sequence information and secondary structure of DNA nanostructures, but exclude modeling of tertiary structures. We define a class of labeled graphs called DNA graphs, that provide a graph theoretic representation of PDNs. We introduce a set of graph rewrite rules that operate on DNA graphs. Our DNA graphs and graph rewrite rules provide a powerful and expressive way to model DNA nanostructures and their reactions. These rewrite rules model most conventional reactions on DNA nanostructures, which include hybridization, dehybridization, base-stacking, and a large family of enzymatic reactions. A subset of these rewrite rules would likely be used for a basic graph rewrite system modeling most DNA devices, which use just DNA hybridization reactions, whereas other of our rewrite rules could be incorporated as needed for DNA devices for example enzymic reactions. To ensure consistency of our systems, we define a subset of DNA graphs which we call well-formed DNA graphs, whose strands have consistent 5′ to 3′ polarity. We show that if we start with an input set of well-formed DNA graphs, our rewrite rules produce only well-formed DNA graphs. We give four detailed example applications of our graph rewriting system. Show less

The tile assembly model is a Turing universal model of self-assembly where a set of square shaped tiles with programmable sticky sides undergo coordinated self-assembly to form arbitrary shapes, thereby computing arbitrary functions. Activatable tiles are a theoretical extension to the Tile assembly model that enhances its robustness by protecting the sticky sides of tiles until a tile is partially incorporated into a growing assembly. In this article, we experimentally demonstrate a simplified… Show more

The tile assembly model is a Turing universal model of self-assembly where a set of square shaped tiles with programmable sticky sides undergo coordinated self-assembly to form arbitrary shapes, thereby computing arbitrary functions. Activatable tiles are a theoretical extension to the Tile assembly model that enhances its robustness by protecting the sticky sides of tiles until a tile is partially incorporated into a growing assembly. In this article, we experimentally demonstrate a simplified version of the Activatable tile assembly model. In particular, we demonstrate the simultaneous assembly of protected DNA tiles where a set of inert tiles are activated via a DNA polymerase to undergo linear assembly. We then demonstrate stepwise activated assembly where a set of inert tiles are activated sequentially one after another as a result of attachment to a growing 1-D assembly. We hope that these results will pave the way for more sophisticated demonstrations of activated assemblies. Show less

Molecular devices made of nucleic acids can perform complex information processing tasks at the nanoscale, with potential applications in biofabrication and smart therapeutics. However, limitations in the speed and scalability of such devices in a well-mixed setting can significantly affect their performance. In this article, we propose designs for localized circuits involving DNA molecules that are arranged on addressable substrates and interact via hybridization reactions. We propose designs… Show more

Molecular devices made of nucleic acids can perform complex information processing tasks at the nanoscale, with potential applications in biofabrication and smart therapeutics. However, limitations in the speed and scalability of such devices in a well-mixed setting can significantly affect their performance. In this article, we propose designs for localized circuits involving DNA molecules that are arranged on addressable substrates and interact via hybridization reactions. We propose designs for localized elementary logic circuits, which we compose to produce more complex devices, including a circuit for computing the square root of a four bit number. We develop an efficient method for probabilistic model checking of localized circuits, which we implement within the Visual DSD design tool. We use this method to prove the correctness of our circuits with respect to their functional specifications and to analyze their performance over a broad range of local rate parameters. Specifically, we analyze the extent to which our localized designs can overcome the limitations of well-mixed circuits, with respect to speed and scalability. To provide an estimate of local rate parameters, we propose a biophysical model of localized hybridization. Finally, we use our analysis to identify constraints in the rate parameters that enable localized circuits to retain their advantages in the presence of unintended interferences between strands. Show less

Molecular computing is computation done at the molecular scale. DNA computing is a class of molecular computing that does computation by the use of reactions involving DNA molecules. DNA computing has been by far the most successful (in scale and complexity of the computations and molecular assemblies done) of all known approaches to molecular computing, perhaps due in part to the very well established biotechnology and biochemistry on which its experimental demonstration relies, as well as the… Show more

Molecular computing is computation done at the molecular scale. DNA computing is a class of molecular computing that does computation by the use of reactions involving DNA molecules. DNA computing has been by far the most successful (in scale and complexity of the computations and molecular assemblies done) of all known approaches to molecular computing, perhaps due in part to the very well established biotechnology and biochemistry on which its experimental demonstration relies, as well as the frequent teaming of scientists in the field with multiple essential disciplines including chemistry, biochemistry, physics, material science, and computer science. Show less

The goal of synthetic biology is to design and assemble synthetic systems that mimic biological systems. One of the most fundamental challenges in synthetic biology is to synthesize artificial biochemical systems, which we will call meta-biochemical systems, that provide the same functionality as biological nucleic acids-enzyme systems, but that use a very limited number of types of molecules. The motivation for developing such synthetic biology systems is to enable a better understanding of… Show more

The goal of synthetic biology is to design and assemble synthetic systems that mimic biological systems. One of the most fundamental challenges in synthetic biology is to synthesize artificial biochemical systems, which we will call meta-biochemical systems, that provide the same functionality as biological nucleic acids-enzyme systems, but that use a very limited number of types of molecules. The motivation for developing such synthetic biology systems is to enable a better understanding of the basic processes of natural biology, and also to enable re-engineering and programmability of synthetic versions of biological systems. One of the key aspects of modern nucleic acid biochemistry is its extensive use of protein enzymes that were originally evolved in cells to manipulate nucleic acids, and then later adapted by man for laboratory use. This practice provided powerful tools for manipulating nucleic acids, but also limited the extent of the programmability of the available chemistry for manipulating nucleic acids, since it is very difficult to predictively modify the behavior of protein enzymes. Meta-biochemical systems offer the possible advantage of being far easier to re-engineer and program for desired functionality. The approach taken here is to develop a biochemical system which we call meta-DNA (abbreviated as mDNA),Meta-DNA (mDNA) based entirely on strands of DNA as the only component molecules. Our work leverages prior work on the development of self-assembled DNA nanostructures. Our mDNA bases can be assembled to form flexible linear assemblies (single stranded mDNA) analogous to single stranded DNA, and can be hybridized to form stiff helical structures (duplex mDNA) analogous to double Double strand meta-DNA (dsmDNA) stranded DNA, and also can be denatured back to single stranded mDNA. We describe various isothermal hybridization reactions that manipulate our mDNA in powerful ways analogous to DNA–DNA reactions and the action of various enzymes on DNA. Show less

There is a growing need for sensitive and reliable nucleic acid detection methods that are convenient and inexpensive. Responsive and programmable DNA nanostructures have shown great promise as chemical detection systems. Here, we describe a DNA detection system employing the triggered self-assembly of a novel DNA dendritic nanostructure. The detection protocol is executed autonomously without external intervention. Detection begins when a specific, single-stranded target DNA strand (T)… Show more

There is a growing need for sensitive and reliable nucleic acid detection methods that are convenient and inexpensive. Responsive and programmable DNA nanostructures have shown great promise as chemical detection systems. Here, we describe a DNA detection system employing the triggered self-assembly of a novel DNA dendritic nanostructure. The detection protocol is executed autonomously without external intervention. Detection begins when a specific, single-stranded target DNA strand (T) triggers a hybridization chain reaction (HCR) between two, distinct DNA hairpins (α and β). Each hairpin opens and hybridizes up to two copies of the other. In the absence of T, α and β are stable and remain in their poised, closed-hairpin form. In the presence of T, α hairpins are opened by toe-hold mediated strand-displacement, each of which then opens and hybridizes two β hairpins. Likewise, each opened β hairpin can open and hybridize two α hairpins. Hence, each layer of the growing dendritic nanostructure can in principle accommodate an exponentially increasing number of cognate molecules, generating a high molecular weight nanostructure. This HCR system has minimal sequence constraints, allowing reconfiguration for the detection of arbitrary target sequences. Here, we demonstrate detection of unique sequence identifiers of HIV and Chlamydia pathogens. Show less

The control of matter and phenomena at the nanoscale is fast becoming one of the most important challenges of the 21st century with wide-ranging applications from energy and health care to computing and material science. Conventional top-down approaches to nanotechnology, having served us well for long, are reaching their inherent limitations. Meanwhile, bottom-up methods such as self-assembly are emerging as viable alternatives for nanoscale fabrication and manipulation.
A particularly… Show more

The control of matter and phenomena at the nanoscale is fast becoming one of the most important challenges of the 21st century with wide-ranging applications from energy and health care to computing and material science. Conventional top-down approaches to nanotechnology, having served us well for long, are reaching their inherent limitations. Meanwhile, bottom-up methods such as self-assembly are emerging as viable alternatives for nanoscale fabrication and manipulation.
A particularly successful bottom up technique is DNA self-assembly where a set of carefully designed DNA strands form a nanoscale object as a consequence of specific, local interactions among the different components, without external direction. The final product of the self-assembly process might be a static nanostructure or a dynamic nanodevice that performs a specific function. Over the past two decades, DNA self-assembly has produced stunning nanoscale objects such as 2D and 3D lattices, polyhedra and addressable arbitrary shaped substrates, and a myriad of nanoscale devices such as molecular tweezers, computational circuits, biosensors and molecular assembly lines. In this dissertation we study multiple problems in the theory, simulations and experiments of DNA self-assembly. Show less

The field of biomolecular computation started 3.5 billion years ago on earth when the first life forms evolved.What distinguished these simple organisms from a collection of inanimate molecules was the ability to process information and it is this ability of chemistry based computation that powers life in its various forms even today. Our attempts at exploiting this rich molecular tool set for computation have just begun. This chapter recounts some of the amazing experiments, starting from 1994… Show more

The field of biomolecular computation started 3.5 billion years ago on earth when the first life forms evolved.What distinguished these simple organisms from a collection of inanimate molecules was the ability to process information and it is this ability of chemistry based computation that powers life in its various forms even today. Our attempts at exploiting this rich molecular tool set for computation have just begun. This chapter recounts some of the amazing experiments, starting from 1994 which demonstrated how one could process information and perform computation at the molecular scale using DNA. Show less

This chapter overviews the current state of the emerging discipline of DNA nanorobotics that make use of synthetic DNA to self-assemble operational molecular-scale devices. Recently there have been a series of quite astonishing experimental results—which have taken the technology from a state of intriguing possibilities into demonstrated capabilities of quickly increasing scale and complexity. We first state the challenges in molecular robotics and discuss why DNA as a nanoconstruction material… Show more

This chapter overviews the current state of the emerging discipline of DNA nanorobotics that make use of synthetic DNA to self-assemble operational molecular-scale devices. Recently there have been a series of quite astonishing experimental results—which have taken the technology from a state of intriguing possibilities into demonstrated capabilities of quickly increasing scale and complexity. We first state the challenges in molecular robotics and discuss why DNA as a nanoconstruction material is ideally suited to overcome these. We then review the design and demonstration of a wide range of molecular-scale devices; from DNA nanomachines that change conformation in response to their environment to DNA walkers that can be programmed to walk along predefined paths on nanostructures while carrying cargo or performing computations, to tweezers that can repeatedly switch states. We conclude by listing major challenges in the field along with some possible future directions. Show less

Can a wide range of complex biochemical behaviour arise from repeated applications of a highly reduced class of interactions? In particular, can the range of DNA manipulations achieved by protein enzymes be simulated via simple DNA hybridization chemistry? In this work, we develop a biochemical system which we call meta-DNA (abbreviated as mDNA), based on strands of DNA as the only component molecules. Various enzymatic manipulations of these mDNA molecules are simulated via toehold-mediated… Show more

Can a wide range of complex biochemical behaviour arise from repeated applications of a highly reduced class of interactions? In particular, can the range of DNA manipulations achieved by protein enzymes be simulated via simple DNA hybridization chemistry? In this work, we develop a biochemical system which we call meta-DNA (abbreviated as mDNA), based on strands of DNA as the only component molecules. Various enzymatic manipulations of these mDNA molecules are simulated via toehold-mediated DNA strand displacement reactions. We provide a formal model to describe the required properties and operations of our mDNA, and show that our proposed DNA nanostructures and hybridization reactions provide these properties and functionality. Our meta-nucleotides are designed to form flexible linear assemblies (single-stranded mDNA (ssmDNA)) analogous to single-stranded DNA. We describe various isothermal hybridization reactions that manipulate our mDNA in powerful ways analogous to DNA–DNA reactions and the action of various enzymes on DNA. These operations on mDNA include (i) hybridization of ssmDNA into a double-stranded mDNA (dsmDNA) and heat denaturation of a dsmDNA into its component ssmDNA, (ii) strand displacement of one ssmDNA by another, (iii) restriction cuts on the backbones of ssmDNA and dsmDNA, (iv) polymerization reactions that extend ssmDNA on a template to form a complete dsmDNA, (v) synthesis of mDNA sequences via mDNA polymerase chain reaction, (vi) isothermal denaturation of a dsmDNA into its component ssmDNA, and (vii) an isothermal replicator reaction that exponentially amplifies ssmDNA strands and may be modified to allow for mutations. Show less

This chapter overviews the past and current state of the emerging research area in the field of nanoscience that make use of synthetic DNA to self-assemble into DNA nanostructures and to make operational molecular-scale devices. Recently there have been a series of quite astonishing experimental results - which have taken the technology from a state of intriguing possibilities into demonstrated capabilities of quickly increasing scale and complexity. We discuss the design and demonstration of… Show more

This chapter overviews the past and current state of the emerging research area in the field of nanoscience that make use of synthetic DNA to self-assemble into DNA nanostructures and to make operational molecular-scale devices. Recently there have been a series of quite astonishing experimental results - which have taken the technology from a state of intriguing possibilities into demonstrated capabilities of quickly increasing scale and complexity. We discuss the design and demonstration of molecular-scale devices that make use of DNA nanostructures to achieve: molecular patterning, molecular computation, amplified sensing and nanoscale transport. We particularly emphasize molecular devices that make use of techniques that seem most promising, namely ones that are programmable (the tasks executed can be modified without entirely redesigning the nanostructure) and autonomous (executing steps with no external mediation after starting). Show less

Self-assembly is fundamental to both biological processes and nanoscience. Key features of self-assembly are its probabilistic nature and local programmability. These features can be leveraged to design better self-assembled systems. The conventional Tile Assembly Model (TAM) developed by Winfree using Wang tiles is a powerful, Turing-universal theoretical framework which models varied self-assembly processes. The tile complexity of a linear assembly is the cardinality of the tile set that… Show more

Self-assembly is fundamental to both biological processes and nanoscience. Key features of self-assembly are its probabilistic nature and local programmability. These features can be leveraged to design better self-assembled systems. The conventional Tile Assembly Model (TAM) developed by Winfree using Wang tiles is a powerful, Turing-universal theoretical framework which models varied self-assembly processes. The tile complexity of a linear assembly is the cardinality of the tile set that produces it. While square assemblies have been extensively studied, many questions remain about fixed length linear assemblies, which are more basic constructs yet fundamental building blocks for molecular architectures. In this work, we extend TAM to take advantage of inherent probabilistic behavior in physically realized self-assembled systems by introducing randomization. We describe a natural extension to TAM called the Probabilistic Tile Assembly Model (PTAM). A restriction of the model, which we call the standard PTAM is considered in this report. Prior work in DNA self-assembly strongly suggests that standard PTAM can be realized in the laboratory. In TAM, a deterministic linear assembly of length N requires a tile set of cardinality at least N. In contrast, we show various non-trivial probabilistic constructions for forming linear assemblies in PTAM with tile sets of sub-linear cardinality, using techniques that differ considerably from existing assembly techniques. In particular, for any given N, we demonstrate linear assemblies of expected length N with a tile set of cardinality Θ(log N) using one pad per side of each tile. We prove a matching lower bound of Ω(log N) on the tile complexity of linear assemblies of any given expected length N in standard PTAM systems using one pad per side of each tile. Show less

Molecular computing executed via local interactions of spatially contiguous sets of molecules has potential advantages of (i) speed due to increased local concentration of reacting species, (ii) generally sharper switching behavior and higher precision due to single molecule interactions, (iii) parallelism since each circuit operates independently of the others and (iv) modularity and scalability due to the ability to reuse DNA sequences in spatially separated regions. We propose detailed… Show more

Molecular computing executed via local interactions of spatially contiguous sets of molecules has potential advantages of (i) speed due to increased local concentration of reacting species, (ii) generally sharper switching behavior and higher precision due to single molecule interactions, (iii) parallelism since each circuit operates independently of the others and (iv) modularity and scalability due to the ability to reuse DNA sequences in spatially separated regions. We propose detailed designs for local molecular computations that involve spatially contiguous molecules arranged on addressable substrates. The circuits act via enzyme-free DNA hybridization reaction cascades. Our designs include composable OR, AND and propagation Boolean gates, and techniques to achieve higher degree fan-in and fan-out. A biophysical model of localized hybridization reactions is used to estimate the effect of locality on reaction rates. We also use the Visual DSD simulation software in conjunction with localized reaction rates to simulate a localized circuit for computing the square root of a four bit number. Show less

The hybridization of complementary nucleic acid strands is the most basic of all reactions involving nucleic acids, but has a major limitation: the specificity of hybridization reactions depends critically on the lengths of the complementary pairs of strands and can drop to very low values for sufficiently long strands. This reduction in specificity occurs especially in the presence of noise in the form of other competing strands that have sequence segments identical to the target. This limits… Show more

The hybridization of complementary nucleic acid strands is the most basic of all reactions involving nucleic acids, but has a major limitation: the specificity of hybridization reactions depends critically on the lengths of the complementary pairs of strands and can drop to very low values for sufficiently long strands. This reduction in specificity occurs especially in the presence of noise in the form of other competing strands that have sequence segments identical to the target. This limits the scale and accuracy of biotechnology and nanotechnology applications which depend on hybridization reactions. Our paper develops techniques for ensuring specific high-fidelity DNA hybridization reactions for target strands of arbitrary length. Our protocol is executed autonomously, without external mediation and driven by a series of conversions of single stranded DNA into duplex DNA that help overcome kinetic energy traps, similar to DNA walkers. Show less

The conventional Tile Assembly Model (TAM) developed by Winfree using Wang tiles is a powerful, Turing-universal theoretical framework which models varied self-assembly processes. We describe a natural extension to TAM called the Probabilistic Tile Assembly Model (PTAM) to model the inherent probabilistic behavior in physically realized self-assembled systems. A particular challenge in DNA nanoscience is to form linear assemblies or rulers of a specified length using the smallest possible tile… Show more

The conventional Tile Assembly Model (TAM) developed by Winfree using Wang tiles is a powerful, Turing-universal theoretical framework which models varied self-assembly processes. We describe a natural extension to TAM called the Probabilistic Tile Assembly Model (PTAM) to model the inherent probabilistic behavior in physically realized self-assembled systems. A particular challenge in DNA nanoscience is to form linear assemblies or rulers of a specified length using the smallest possible tile set. These rulers can then be used as components for construction of other complex structures. In TAM, a deterministic linear assembly of length N requires a tile set of cardinality at least N. In contrast, for any given N, we demonstrate linear assemblies of expected length N with a tile set of cardinality Θ(logN) and prove a matching lower bound of Ω(logN). We also propose a simple extension to PTAM called κ-pad systems in which we associate κ pads with each side of a tile, allowing abutting tiles to bind when at least one pair of corresponding pads match and prove analogous results. All our probabilistic constructions are free from co-operative tile binding errors and can be modified to produce assemblies whose probability distribution of lengths has arbitrarily small tail bounds dropping exponentially with a given multiplicative factor increase in number of tile types. Thus, for linear assembly systems, we have shown that randomization can be exploited to get large improvements in tile complexity at a small expense of precision in length. Show less

In a paper presented to BICS 2006, a basic methodology for microprocessor design automation using DNA sequences was proposed. A refined methodology with new schemes for traversal, encoding, recombination, and processor evaluation are proposed in this paper. Moreover concepts such as mutation, graphical decoding and environment simulation are introduced and a new technique for creating DNA based algorithms used in the mutation process is also presented. The proposed methodology is then… Show more

In a paper presented to BICS 2006, a basic methodology for microprocessor design automation using DNA sequences was proposed. A refined methodology with new schemes for traversal, encoding, recombination, and processor evaluation are proposed in this paper. Moreover concepts such as mutation, graphical decoding and environment simulation are introduced and a new technique for creating DNA based algorithms used in the mutation process is also presented. The proposed methodology is then generalized to extend its application to other domains. This paper presents a conceptual framework whose implementation aspects are still under investigation. Show less

The standard Tile Assembly Model (TAM) of Winfree is a mathematical theory of crystal aggregations via monomer additions with applications to the emerging science of DNA self-assembly. Self-assembly under the rules of this model is programmable and can perform Turing universal computation. Many variations of this model have been proposed and the canonical problem of assembling squares has been studied extensively.
We consider the problem of building approximate squares in TAM. Given any… Show more

The standard Tile Assembly Model (TAM) of Winfree is a mathematical theory of crystal aggregations via monomer additions with applications to the emerging science of DNA self-assembly. Self-assembly under the rules of this model is programmable and can perform Turing universal computation. Many variations of this model have been proposed and the canonical problem of assembling squares has been studied extensively.
We consider the problem of building approximate squares in TAM. Given any ε∈(0,1/4] we show how to construct squares whose sides are within (1±ε)N of any given positive integer N using O(log 1/ε / loglog 1/ε + loglog εN / logloglog εN)tile types. We prove a matching lower bound by showing that Ω(log 1/ε / loglog 1/ε + loglog εN / logloglog εN) tile types are necessary almost always to build squares of required approximate dimensions. In comparison, the optimal construction for a square of side exactly N in TAM uses O(logN / loglogN).
The question of constructing approximate squares has been recently studied in a modified tile assembly model involving concentration programming. All our results are trivially translated into the concentration programming model by assuming arbitrary (non-zero) concentrations for our tile types. Indeed, the non-zero concentrations could be chosen by an adversary and our results would still hold.
Our construction can get highly accurate squares using very few tile types and are feasible starting from values of N that are orders of magnitude smaller than the best comparable constructions previously suggested. At an accuracy of ε=0.01, the number of tile types used to achieve a square of size 107 is just 58 and our constructions are proven to work for all N≥13130. If the concentrations of the tile types are carefully chosen, we prove that our construction assembles an L×L square in optimal assembly time O(L) where (1−ε)N≤L≤(1+ε)N. Show less