Programming Molecular Devices using Nucleic Acid Hairpins

<p>Nucleic Acid hairpins have been a subject of study for the last four decades. They are composed of single strand that is </p><p>hybridized to itself, and the central section forming an unhybridized loop. In nature, they stabilize single stranded RNA, serve as nucleation</p><p>sites for RNA folding, protein recognition signals, mRNA localization and regulation of mRNA degradation. On the other hand, </p><p>DNA hairpins in biological contexts have been studied with respect to forming cruciform structures that can regulate gene expression.</p><p>The use of DNA hairpins as fuel for synthetic molecular devices, including locomotion, was proposed and experimental demonstrated in 2003. They</p><p>were interesting because they bring to the table an on-demand energy/information supply mechanism. </p><p>The energy/information is hidden (from hybridization) in the hairpin’s loop, until required.</p><p>The energy/information is harnessed by opening the stem region, and exposing the single stranded loop section.</p><p>The loop region is now free for possible hybridization and help move the system into a thermodynamically favourable state.</p><p>The hidden energy and information coupled with </p><p>programmability provides another functionality, of selectively choosing what reactions to hide and </p><p>what reactions to allow to proceed, that helps develop a topological sequence of events. </p><p>Hairpins have been utilized as a source of fuel for many different DNA devices. In this thesis, we program four different </p><p>molecular devices using DNA hairpins, and experimentally validate them in the</p><p>laboratory. 1) The first device: A </p><p>novel enzyme-free autocatalytic self-replicating system composed entirely of DNA that operates isothermally. 2) The second</p><p>device: Time-Responsive Circuits using DNA have two properties: a) asynchronous: the final output is always correct </p><p>regardless of differences in the arrival time of different inputs.</p><p>b) renewable circuits which can be used multiple times without major degradation of the gate motifs </p><p>(so if the inputs change over time, the DNA-based circuit can re-compute the output correctly based on the new inputs).</p><p>3) The third device: Activatable tiles are a theoretical extension to the Tile assembly model that enhances </p><p>its robustness by protecting the sticky sides of tiles until a tile is partially incorporated into a growing assembly. </p><p>4) The fourth device: Controlled Amplification of DNA catalytic system: a device such that the amplification</p><p>of the system does not run uncontrollably until the system runs out of fuel, but instead achieves a finite</p><p>amount of gain.</p><p>Nucleic acid circuits with the ability </p><p>to perform complex logic operations have many potential practical applications, for example the ability to achieve point of care diagnostics.</p><p>We discuss the designs of our DNA Hairpin molecular devices, the results we have obtained, and the challenges we have overcome</p><p>to make these truly functional.</p>

Cumulon: Simplified Matrix-Based Data Analytics in the Cloud

<p>Cumulon is a system aimed at simplifying the development and deployment of statistical analysis of big data in public clouds. Cumulon allows users to program in their familiar language of matrices and linear algebra, without worrying about how to map data and computation to specific hardware and cloud software platforms. Given user-specified requirements in terms of time, monetary cost, and risk tolerance, Cumulon automatically makes intelligent decisions on implementation alternatives, execution parameters, as well as hardware provisioning and configuration settings -- such as what type of machines and how many of them to acquire. Cumulon also supports clouds with auction-based markets: it effectively utilizes computing resources whose availability varies according to market conditions, and suggests best bidding strategies for them. Cumulon explores two alternative approaches toward supporting such markets, with different trade-offs between system and optimization complexity. Experimental study is conducted to show the efficiency of Cumulon's execution engine, as well as the optimizer's effectiveness in finding the optimal plan in the vast plan space.</p>

Learning and Exploiting Camera Geometry for Computer Vision

<p>This work explores the use of statistical methods in describing and estimating camera poses, as well as the information feedback loop between camera pose and object detection. Surging development in robotics and computer vision has pushed the need for algorithms that infer, understand, and utilize information about the position and orientation of the sensor platforms when observing and/or interacting with their environment.</p><p>The first contribution of this thesis is the development of a set of statistical tools for representing and estimating the uncertainty in object poses. A distribution for representing the joint uncertainty over multiple object positions and orientations is described, called the mirrored normal-Bingham distribution. This distribution generalizes both the normal distribution in Euclidean space, and the Bingham distribution on the unit hypersphere. It is shown to inherit many of the convenient properties of these special cases: it is the maximum-entropy distribution with fixed second moment, and there is a generalized Laplace approximation whose result is the mirrored normal-Bingham distribution. This distribution and approximation method are demonstrated by deriving the analytical approximation to the wrapped-normal distribution. Further, it is shown how these tools can be used to represent the uncertainty in the result of a bundle adjustment problem.</p><p>Another application of these methods is illustrated as part of a novel camera pose estimation algorithm based on object detections. The autocalibration task is formulated as a bundle adjustment problem using prior distributions over the 3D points to enforce the objects' structure and their relationship with the scene geometry. This framework is very flexible and enables the use of off-the-shelf computational tools to solve specialized autocalibration problems. Its performance is evaluated using a pedestrian detector to provide head and foot location observations, and it proves much faster and potentially more accurate than existing methods.</p><p>Finally, the information feedback loop between object detection and camera pose estimation is closed by utilizing camera pose information to improve object detection in scenarios with significant perspective warping. Methods are presented that allow the inverse perspective mapping traditionally applied to images to be applied instead to features computed from those images. For the special case of HOG-like features, which are used by many modern object detection systems, these methods are shown to provide substantial performance benefits over unadapted detectors while achieving real-time frame rates, orders of magnitude faster than comparable image warping methods.</p><p>The statistical tools and algorithms presented here are especially promising for mobile cameras, providing the ability to autocalibrate and adapt to the camera pose in real time. In addition, these methods have wide-ranging potential applications in diverse areas of computer vision, robotics, and imaging.</p>

Studying Recommender Systems to Enhance Distributed Computing Schedulers

<p>Distributed Computing frameworks belong to a class of programming models that allow developers to</p><p> launch workloads on large clusters of machines. Due to the dramatic increase in the volume of</p><p> data gathered by ubiquitous computing devices, data analytic workloads have become a common</p><p> case among distributed computing applications, making Data Science an entire field of</p><p> Computer Science. We argue that Data Scientist's concern lays in three main components: a dataset,</p><p> a sequence of operations they wish to apply on this dataset, and some constraint they may have</p><p> related to their work (performances, QoS, budget, etc). However, it is actually extremely</p><p> difficult, without domain expertise, to perform data science. One need to select the right amount</p><p> and type of resources, pick up a framework, and configure it. Also, users are often running their</p><p> application in shared environments, ruled by schedulers expecting them to specify precisely their resource</p><p> needs. Inherent to the distributed and concurrent nature of the cited frameworks, monitoring and </p><p> profiling are hard, high dimensional problems that block users from making the right</p><p> configuration choices and determining the right amount of resources they need. Paradoxically, the </p><p> system is gathering a large amount of monitoring data at runtime, which remains unused.</p><p> In the ideal abstraction we envision for data scientists, the system is adaptive, able to exploit</p><p> monitoring data to learn about workloads, and process user requests into a tailored execution</p><p> context. In this work, we study different techniques that have been used to make steps toward</p><p> such system awareness, and explore a new way to do so by implementing machine learning</p><p> techniques to recommend a specific subset of system configurations for Apache Spark applications.</p><p> Furthermore, we present an in depth study of Apache Spark executors configuration, which highlight</p><p> the complexity in choosing the best one for a given workload.</p>

Algorithms for Geometric Matching, Clustering, and Covering

<p>With the popularization of GPS-enabled devices such as mobile phones, location data are becoming available at an unprecedented scale. The locations may be collected from many different sources such as vehicles moving around a city, user check-ins in social networks, and geo-tagged micro-blogging photos or messages. Besides the longitude and latitude, each location record may also have a timestamp and additional information such as the name of the location. Time-ordered sequences of these locations form trajectories, which together contain useful high-level information about people's movement patterns.</p><p>The first part of this thesis focuses on a few geometric problems motivated by the matching and clustering of trajectories. We first give a new algorithm for computing a matching between a pair of curves under existing models such as dynamic time warping (DTW). The algorithm is more efficient than standard dynamic programming algorithms both theoretically and practically. We then propose a new matching model for trajectories that avoids the drawbacks of existing models. For trajectory clustering, we present an algorithm that computes clusters of subtrajectories, which correspond to common movement patterns. We also consider trajectories of check-ins, and propose a statistical generative model, which identifies check-in clusters as well as the transition patterns between the clusters. </p><p>The second part of the thesis considers the problem of covering shortest paths in a road network, motivated by an EV charging station placement problem. More specifically, a subset of vertices in the road network are selected to place charging stations so that every shortest path contains enough charging stations and can be traveled by an EV without draining the battery. We first introduce a general technique for the geometric set cover problem. This technique leads to near-linear-time approximation algorithms, which are the state-of-the-art algorithms for this problem in either running time or approximation ratio. We then use this technique to develop a near-linear-time algorithm for this</p><p>shortest-path cover problem.</p>

Distributed Feature Selection in Large n and Large p Regression Problems

<p>Fitting statistical models is computationally challenging when the sample size or the dimension of the dataset is huge. An attractive approach for down-scaling the problem size is to first partition the dataset into subsets and then fit using distributed algorithms. The dataset can be partitioned either horizontally (in the sample space) or vertically (in the feature space), and the challenge arise in defining an algorithm with low communication, theoretical guarantees and excellent practical performance in general settings. For sample space partitioning, I propose a MEdian Selection Subset AGgregation Estimator ({\em message}) algorithm for solving these issues. The algorithm applies feature selection in parallel for each subset using regularized regression or Bayesian variable selection method, calculates the `median' feature inclusion index, estimates coefficients for the selected features in parallel for each subset, and then averages these estimates. The algorithm is simple, involves very minimal communication, scales efficiently in sample size, and has theoretical guarantees. I provide extensive experiments to show excellent performance in feature selection, estimation, prediction, and computation time relative to usual competitors.</p><p>While sample space partitioning is useful in handling datasets with large sample size, feature space partitioning is more effective when the data dimension is high. Existing methods for partitioning features, however, are either vulnerable to high correlations or inefficient in reducing the model dimension. In the thesis, I propose a new embarrassingly parallel framework named {\em DECO} for distributed variable selection and parameter estimation. In {\em DECO}, variables are first partitioned and allocated to m distributed workers. The decorrelated subset data within each worker are then fitted via any algorithm designed for high-dimensional problems. We show that by incorporating the decorrelation step, DECO can achieve consistent variable selection and parameter estimation on each subset with (almost) no assumptions. In addition, the convergence rate is nearly minimax optimal for both sparse and weakly sparse models and does NOT depend on the partition number m. Extensive numerical experiments are provided to illustrate the performance of the new framework.</p><p>For datasets with both large sample sizes and high dimensionality, I propose a new "divided-and-conquer" framework {\em DEME} (DECO-message) by leveraging both the {\em DECO} and the {\em message} algorithm. The new framework first partitions the dataset in the sample space into row cubes using {\em message} and then partition the feature space of the cubes using {\em DECO}. This procedure is equivalent to partitioning the original data matrix into multiple small blocks, each with a feasible size that can be stored and fitted in a computer in parallel. The results are then synthezied via the {\em DECO} and {\em message} algorithm in a reverse order to produce the final output. The whole framework is extremely scalable.</p>