Harish Chandran

Harish Chandran

At Alphabet, I currently lead Behavior Models group within Waymo which is responsible to improve the quality of predictions about the behavior of agents the Waymo driven encounters in the real world. Previously, I worked on bring DeepMind technologies to Google products and making ranking and recommendations of posts on Google+ better. In graduate school, I worked on DNA self-assembly, nanoscience and theoretical self-assembly.
Authored Publications
Google Publications
Other Publications
Sort By
  • Title
  • Title, descending
  • Year
  • Year, descending
    Balance Regularized Neural Network Models for Causal Effect Estimation
    Mehrdad Farajtabar
    Andrew Lee
    Yuanjian Feng
    Vishal Gupta
    Peter Dolan
    Martin Szummer
    Causal Discovery & Causality-Inspired Machine Learning Workshop, NeurIPS 2020(2020)
    Preview abstract 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. View details
    Improving the Performance of DNA Strand Displacement Circuits by Shadow Cancellation
    Tianqi Song
    Nikhil Gopalkrishnan
    Abeer Eshra
    Sudhanshu Garg
    Reem Mokhtar
    Hieu Bui
    John Reif
    ACS Nano(2018)
    Preview abstract 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. View details
    Modeling DNA Nanodevices Using Graph Rewrite Systems
    Reem Mokhtar
    Sudhanshu Garg
    Hieu Bui
    Tianqi Song
    John Reif
    Springer International Publishing(2017), pp. 347-395
    Preview abstract 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 (PDNs), 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. View details
    Directed Enzymatic Activation of 1-D DNA Tiles
    Sudhanshu Garg
    Nikhil Gopalkrishnan
    Thomas H. LaBean
    John Reif
    ACS Nano(2015)
    Preview abstract 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. View details
    Probabilistic Analysis of Localized DNA Hybridization Circuits
    Neil Dalchau
    Nikhil Gopalkrishnan
    Andrew Phillips
    John Reif
    ACS Synthetic Biology(2015)
    Preview abstract 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 paper, 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. View details
    Meta-DNA: A DNA-Based Approach to Synthetic Biology
    Nikhil Gopalkrishnan
    Bernard Yurke
    John H. Reif
    Systems and Synthetic Biology: A Systematic Approach(2014)
    Preview abstract 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. Each base of a mDNA Meta-DNA (mDNA)is a DNA nanostructure. Our mDNA bases are paired similar to DNA bases, but have a much larger alphabet of bases, thereby providing increased power of base addressability. 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. Our work also leverages the abstract activatable tile model developed by Majumder et al. and prior work on the development of enzyme-free isothermal protocols based on DNA hybridization and sophisticated strand displacement hybridization reactions. 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 single strand mDNA (ssmDNA)Single strand meta-DNA (ssmDNA) into a double strand mDNA (dsmDNA)Double strand meta-DNA (dsmDNA) and heat denaturation of a dsmDNA Double strand meta-DNA (dsmDNA)into its component ssmDNA Single strand meta-DNA (ssmDNA)(analogous to DNA hybridization and denaturation), (ii) strand displacement of one ssmDNA Single strand meta-DNA (ssmDNA)by another (similar to strand displacement in DNA), (iii) restriction cuts on the backbones of ssmDNA Single strand meta-DNA (ssmDNA)and dsmDNA Double strand meta-DNA (dsmDNA)(similar to the action of restriction enzymes on DNA), (iv) polymerization chain reactions that extend ssmDNA Single strand meta-DNA (ssmDNA)on a template to form a complete dsmDNA Double strand meta-DNA (dsmDNA)(similar to the action of polymerase enzyme on DNA), (v) isothermal denaturation of a dsmDNA Double strand meta-DNA (dsmDNA)into its component ssmDNA Single strand meta-DNA (ssmDNA)(like the activity of helicase enzyme on DNA) and (vi) an isothermal replicator reaction which exponentially amplifies ssmDNA Single strand meta-DNA (ssmDNA)strands (similar to the isothermal PCR reaction). 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. View details
    DNA Computing
    Hieu Bui
    Sudhanshu Garg
    Nikhil Gopalkrishnan
    Reem Mokhtar
    John H. Reif
    Tianqi Song
    Computing Handbook(2014)
    Preview
    DNA Nanorobotics
    Nikhil Gopalkrishnan
    John H. Reif
    Nanorobotics(2013), pp. 355-382
    Preview abstract 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. View details
    Meta-DNA: Synthetic Biology via DNA Nanostructures and Hybridization Reactions
    Nikhil Gopalkrishnan
    Bernard Yurke
    John H. Reif
    Journal of The Royal Society Interface, 12(2012)
    Preview abstract 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. View details
    An Autonomously Self-assembling Dendritic DNA Nanostructure for Target DNA Detection
    Abhijit Rangnekar
    Geetha Shetty
    Erik A. Schultes
    John H. Reif
    Thomas H. LaBean
    Biotechnology Journal, 8(2012), pp. 221-227
    Preview abstract 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. View details
    Self-assembled DNA Nanostructures and DNA Devices
    John H. Reif
    Nikhil Gopalkrishnan
    Thomas H. LaBean
    Nanofabrication Handbook(2012), 299–328
    Tile Complexity of Linear Assemblies
    Nikhil Gopalkrishnan
    John H. Reif
    SIAM Journal on Computing, 41(2012), pp. 1051-1073
    Preview abstract 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. A particular challenge in DNA nanoscience is to form linear assemblies or rulers of a specified length using the smallest possible tile set, where any tile type may appear more than once in the assembly. The tile complexity of a linear assembly is the cardinality of the tile set that produces it. These rulers can then be used as components for construction of other complex structures. 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 nontrivial probabilistic constructions for forming linear assemblies in PTAM with tile sets of sublinear 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 $\Theta(\log N)$ using one pad per side of each tile. We prove a matching lower bound of $\Omega(\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. We further demonstrate how linear assemblies can be modified to produce assemblies with sharp tail bounds on distribution of lengths by concatenating various assemblies together. In particular, we show that for infinitely many $N$ we can get linear assemblies with exponentially dropping tail distributions using $O(\log^3 N)$ tile types. We also propose a simple extension to PTAM called $\kappa$-pad systems in which we associate $\kappa$ pads with each side of a tile, allowing abutting tiles to bind when at least one pair of corresponding pads match. This gives linear assemblies of expected length $N$ with a $2$-pad (two pads per side of each tile) tile set of cardinality $\Theta(\frac{\log N}{\log \log N})$ for infinitely many $N$. We show that we cannot get smaller tile complexity by proving a lower bound of $\Omega(\frac{\log N}{\log \log N})$ for each $N$ on the cardinality of the $\kappa$-pad ($\kappa$-pads per side of each tile) tile set required to form linear assemblies of expected length $N$ in standard $\kappa$-pad PTAM systems for any positive integer $\kappa$. The techniques that we use for deriving these tile complexity lower bounds are notable as they differ from traditional Kolmogorov complexity based information theoretic methods used for lower bounds on tile complexity. Also, Kolmogorov complexity based lower bounds do not preclude the possibility of achieving assemblies of very small tile multiset cardinality for infinitely many $N$. In contrast, our lower bounds are stronger as they hold for every $N$, rather than for almost all $N$. All our probabilistic constructions are free from co-operative tile binding errors. 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. View details
    Tile Complexity of Approximate Squares
    Nikhil Gopalkrishnan
    John H. Reif
    Algorithmica, 66(2012), pp. 1-17
    Preview abstract The standard Tile Assembly Model (TAM) of Winfree (Algorithmic self-assembly of DNA, Ph.D. thesis, 1998) 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(log1/ε/ log log 1/ε + log logεN/log log log ε N) tile types. We prove a matching lower bound by showing that ω(log1/ε/log log 1/ε + log log ε N/log log log log ε 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(log N\log log N) tile types. 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. View details
    Biomolecular Computing Systems
    Sudhanshu Garg
    Nikhil Gopalkrishnan
    John H. Reif
    Biomolecular Information Processing: From Logic Systems to Smart Sensors and Actuators(2012)
    Localized Hybridization Circuits
    Nikhil Gopalkrishnan
    Andrew Phillips
    John H. Reif
    DNA Computing and Molecular Programming(2011), pp. 64-83
    Preview abstract 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. View details
    High-Fidelity DNA Hybridization using Programmable Molecular DNA Devices
    Nikhil Gopalkrishnan
    John H. Reif
    DNA Computing and Molecular Programming(2010), pp. 59-70
    Preview abstract 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. View details
    The Tile Complexity of Linear Assemblies
    Nikhil Gopalkrishnan
    John H. Reif
    Automata, Languages and Programming(2009)
    Preview abstract 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. View details
    DNA Based Evolutionary Approach for Microprocessor Design Automation
    Nagarajan Venkateswaran
    Arjun Kumersh
    Adaptive and Natural Computing Algorithms(2007), pp. 11-22
    Preview abstract In a paper [1] 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. View details