Browsing by Subject "Markov chains"

Decisions in health care must often be made under inherent uncertainty; from treating patients, to provisioning medical devices, to operational decisions at an outpatient clinic. The outcomes depend on the health of patients as well as the availability of health care professionals and resources. Complex models of clinic performance allow for experiments with new schedules and resource levels without the time, cost, unfeasibility, or risk of testing new policies in real clinics. Model-based methods quantify the effect of various uncertain factors such as the availability of personnel on health care quality indicators like patient wait times in a clinic.

Despite their purported value, few opportunities have existed to test models from data collection through optimization. This dissertation develops a clinic model from end-to-end, beginning with a description of the medical practice, to data collection, to model validation, to optimization. Specialty medical practice is abstracted into treatment steps, measured electronically, and verified through systematic observation. These data are anonymized and made available for researchers. A validation framework uses the data to develop and test candidate models, selecting one that maximizes predictive accuracy while retaining interpretability and reproducibility. The resulting model is used in improving schedules via heuristic optimization. Clustering the results reveals clinic performance groups that represent different goals in clinic quality.

High dimensional random dynamical systems are ubiquitous, including-but not limited to- cyber-physical systems, daily return on different stocks of S\&P 1500 and velocity profile of interacting particle systems around McKeanVlasov limit. Mathematically speaking, observed time series data can be captured via a stable $n-$ dimensional linear transformation `$A$' and additive randomness. System identification aims at extracting useful information about underlying dynamical system, given a length $N$ trajectory from it (corresponds to an $n \times N$ dimensional data matrix). We use spectral theorem for non-Hermitian operators to show that spatio-temperal correlations are dictated by the \emph{discrepancy between algebraic andgeometric multiplicity of distinct eigenvalues} corresponding to state transition matrix. Small discrepancies imply that original trajectory essentially comprises of multiple \emph{lower dimensional random dynamical systems living on $A$ invariant subspaces and are statistically independent of each other}. In the process, we provide first quantitative handle on decay rate of finite powers of state transition matrix $\|A^{k}\|$ . It is shown that when a stable dynamical system has only one distinct eigenvalue and discrepancy of $n-1$: $\|A\|$ has a dependence on $n$, resulting dynamics are \emph{spatially inseparable} and consequently there exist at least one row with covariates of typical size $\Theta\big(\sqrt{N-n+1}$ $e^{n}\big)$ i.e., even under stability assumption, covariates can \emph{suffer from curse of dimensionality }.

In the light of these findings we set the stage for non-asymptotic error analysis in estimation of state transition matrix $A$ via least squares regression on observed trajectory by showing that element-wise error is essentially a variant of well-know Littlewood-Offord problem and(can be extremely sensitive to dimension of the state space and number of iterations). We also show that largest singular value of the data matrix can be cursed by dimensionality even when state-transition matrix is stable. Overarching theme of this thesis is new theoretical results on spectral theorem for non-Hermitian operators, non-asymptotic behavior of high dimensional dynamical systems , which we incorporate with the work of Talagrand on concentration of measure phenomenon to better understand behavior of the structured random matrices(data matrix) and subsequently the performance of different learning algorithms with dependent data. Besides, we also show that there exists stable linear Gaussians with process level Talagrands' inequality linear in dimension of the state space(previously an open problem), along with deterioration of mixing times with increase in discrepancy between algebraic and geometric multiplicity of $A$.

DNA, the blueprint of life, is more than a carrier of genetic information. It offers a highly programmable substrate that can be used for computing, nanorobotics, and advanced imaging techniques. In this work, we use the programmable nature of synthetic DNA to engineer two novel applications. In the first part, DNA is programmed to improve the multiplexing capabilities of a fluorescence microscope while in the second part, we design a novel DNA computing architecture that uses a strand displacing polymerase enzyme. This thesis is a collection of 2 experimental papers, 2 theory papers, and 1 software paper. The general theme of this thesis is to exploit the programmable nature of DNA to develop new applications for the wider field of molecular biology, nanoimaging, and computer engineering.

Optical multiplexing is defined as the ability to study, detect, or quantify multiple objects of interest simultaneously. There are several ways to improve optical multiplexing, namely, using orthogonal wavelengths, multiple mesoscale geometries, orthogonal nucleic acid probes, or a combination of these. Most traditional techniques employ either the geometry or the color of single molecules to uniquely identify (or barcode) different species of interest. However, these techniques require complex sample preparation and multicolor hardware setup. In this work, we introduce a time-based amplification-free single-molecule barcoding technique using easy-to-design nucleic acid strands. A dye-labeled complementary reporter strand transiently binds to the programmed nucleic acid strands to emit temporal intensity signals. We program the DNA strands to emit uniquely identifiable temporal signals for molecular-scale fingerprinting. Since the reporters bind transiently to DNA devices, our method offers relative immunity to photobleaching. We use a single universal reporter strand for all DNA devices making our design extremely cost-effective. We show DNA strands can be programmed for generating a multitude of uniquely identifiable molecular barcodes. Our technique can be easily incorporated with the existing orthogonal methods that use wavelength or geometry to generate a large pool of distinguishable molecular barcodes thereby enhancing the overall multiplexing capabilities of single-molecule imaging. The proposed project has exciting transformative potential for nanoscale applications in fluorescence microscopy and cell biology since the development of temporal barcodes would allow for applications such as sensing miRNAs which are largely associated with disease diagnosis and therapeutics.

The regulation of cellular and molecular processes typically involves complex biochemical networks. Synthetic nucleic acid reaction networks (both enzyme-based and enzyme-free) can be systematically designed to approximate sophisticated biochemical processes. However, most of the prior experimental protocols for chemical reaction networks (CRNs) relied on either strand-displacement hybridization or restriction and exonuclease enzymatic reactions. These resulting synthetic systems usually suffer from either slow rates or leaky reactions. This work proposes an alternative architecture to implement arbitrary reaction networks, that is based entirely on strand-displacing polymerase reactions with nonoverlapping I/O sequences. First, the design for a simple protocol that can approximate arbitrary unimolecular and bimolecular reactions using polymerase strand displacement reactions is presented. Then these fundamental reaction systems are used as modules to show large-scale applications of the architecture, including an autocatalytic amplifier, a molecular-scale consensus protocol, and a dynamic oscillatory system. Finally, we engineer an \textit{in vitro} catalytic amplifier system as a proof-of-concept of our polymerase architecture since such sustainable amplifiers require careful sequence design and implementation.

Cloud computing appears to be a paradigm shift in service oriented computing. Massively scalable Cloud architectures are spawned by new business and social applications as well as Internet driven economics. Besides being inherently large scale and highly distributed, Cloud systems are almost always virtualized and operate in automated shared environments. The deployed Cloud services are still in their infancy and a variety of research challenges need to be addressed to predict their long-term behavior. Performance and dependability of Cloud services are in general stochastic in nature and they are affected by a large number of factors, e.g., nature of workload and faultload, infrastructure characteristics and management policies. As a result, developing scalable and predictive analytics for Cloud becomes difficult and non-trivial. This dissertation presents the research framework needed to develop high fidelity stochastic models for large scale enterprise systems using Cloud computing as an example. Throughout the dissertation, we show how the developed models are used for: (i) performance and availability analysis, (ii) understanding of power-performance trade-offs, (ii) resiliency quantification, (iv) cost analysis and capacity planning, and (v) risk analysis of Cloud services. In general, the models and approaches presented in this thesis can be useful to a Cloud service provider for planning, forecasting, bottleneck detection, what-if analysis or overall optimization during design, development, testing and operational phases of a Cloud.