Topics in randomized numerical linear algebra

<p>This thesis studies three classes of randomized numerical linear algebra algorithms, namely: (i) randomized matrix sparsification algorithms, (ii) low-rank approximation algorithms that use randomized unitary transformations, and (iii) low-rank approximation algorithms for positive-semidefinite (PSD) matrices. </p> <p>Randomized matrix sparsification algorithms set randomly chosen entries of the input matrix to zero. When the approximant is substituted for the original matrix in computations, its sparsity allows one to employ faster sparsity-exploiting algorithms. This thesis contributes bounds on the approximation error of nonuniform randomized sparsification schemes, measured in the spectral norm and two NP-hard norms that are of interest in computational graph theory and subset selection applications.</p> <p> Low-rank approximations based on randomized unitary transformations have several desirable properties: they have low communication costs, are amenable to parallel implementation, and exploit the existence of fast transform algorithms. This thesis investigates the tradeoff between the accuracy and cost of generating such approximations. State-of-the-art spectral and Frobenius-norm error bounds are provided. </p> <p> The last class of algorithms considered are SPSD "sketching" algorithms. Such sketches can be computed faster than approximations based on projecting onto mixtures of the columns of the matrix. The performance of several such sketching schemes is empirically evaluated using a suite of canonical matrices drawn from machine learning and data analysis applications, and a framework is developed for establishing theoretical error bounds. </p> <p> In addition to studying these algorithms, this thesis extends the Matrix Laplace Transform framework to derive Chernoff and Bernstein inequalities that apply to all the eigenvalues of certain classes of random matrices. These inequalities are used to investigate the behavior of the singular values of a matrix under random sampling, and to derive convergence rates for each individual eigenvalue of a sample covariance matrix.</p>

Magnetohydrodynamic turbulence

<p>We simulate incompressible, MHD turbulence using a pseudo-spectral code. Our major conclusions are as follows.</p> <p>1) MHD turbulence is most conveniently described in terms of counter propagating shear Alfv��n and slow waves. Shear Alfv��n waves control the cascade dynamics. Slow waves play a passive role and adopt the spectrum set by the shear Alfv��n waves. Cascades composed entirely of shear Alfv��n waves do not generate a significant measure of slow waves.</p> <p>2) MHD turbulence is anisotropic with energy cascading more rapidly along k_��� than along k_���, where k_��� and k_��� refer to wavevector components perpendicular and parallel to the local magnetic field. Anisotropy increases with increasing k_��� such that excited modes are confined inside a cone bounded by k_��� ��� k^��_��� where �� less than 1. The opening angle of the cone, ��(k_���) ��� k^-(1-��)_���, defines the scale dependent anisotropy.</p> <p>3) MHD turbulence is generically strong in the sense that the waves which comprise it suffer order unity distortions on timescales comparable to their periods. Nevertheless, turbulent fluctuations are small deep inside the inertial range. Their energy density is less than that of the background field by a factor ��² (k_���)���1.</p> <p>4) MHD cascades are best understood geometrically. Wave packets suffer distortions as they move along magnetic field lines perturbed by counter propagating waves. Field lines perturbed by unidirectional waves map planes perpendicular to the local field into each other. Shear Alfv��n waves are responsible for the mapping's shear and slow waves for its dilatation. The amplitude of the former exceeds that of the latter by 1/��(k_���) which accounts for dominance of the shear Alfv��n waves in controlling the cascade dynamics.</p> <p>5) Passive scalars mixed by MHD turbulence adopt the same power spectrum as the velocity and magnetic field perturbations.</p> <p>6) Decaying MHD turbulence is unstable to an increase of the imbalance between the flux of waves propagating in opposite directions along the magnetic field. Forced MHD turbulence displays order unity fluctuations with respect to the balanced state if excited at low k by ��(t) correlated forcing. It appears to be statistically stable to the unlimited growth of imbalance.</p> <p>7) Gradients of the dynamic variables are focused into sheets aligned with the magnetic field whose thickness is comparable to the dissipation scale. Sheets formed by oppositely directed waves are uncorrelated. We suspect that these are vortex sheets which the mean magnetic field prevents from rolling up.</p> <p>8) Items (1)-(5) lend support to the model of strong MHD turbulence put forth by Goldreich and Sridhar (1995, 1997). Results from our simulations are also consistent with the GS prediction �� = 2/3. The sole not able discrepancy is that the 1D power law spectra, E(k_���) ��� k^-���_���, determined from our simulations exhibit ��� ��� 3/2, whereas the GS model predicts ��� = 5/3.</p>

Brf1 post-transcriptionally regulates pluripotency and differentiation responses downstream of Erk MAP Kinase

FGF/Erk MAP Kinase Signaling is a central regulator of mouse embryonic stem cell (mESC) self-renewal, pluripotency and differentiation. However, the mechanistic connection between this signaling pathway activity and the gene circuits stabilizing mESCs in vitro remain unclear. Here we show that FGF signaling post-transcriptionally regulates the mESC transcription factor network by controlling the expression of Brf1 (zfp36l1), an AU-rich element mRNA binding protein. Changes in Brf1 level disrupts the expression of core pluripotency-associated genes and attenuates mESC self-renewal without inducing differentiation. These regulatory effects are mediated by rapid and direct destabilization of Brf1 targets, such as Nanog mRNA. Interestingly, enhancing Brf1 expression does not compromise mESC pluripotency, but does preferentially regulate differentiation to mesendoderm by accelerating the expression of primitive streak markers. Together, these studies demonstrate that FGF signals utilize targeted mRNA degradation by Brf1 to enable rapid post-transcriptional control of gene expression.

Sequence-function relationships in E. coli transcriptional regulation

<p>Understanding how transcriptional regulatory sequence maps to regulatory function remains a difficult problem in regulatory biology. Given a particular DNA sequence for a bacterial promoter region, we would like to be able to say which transcription factors bind there, how strongly they bind, and whether they interact with each other and/or RNA polymerase, with the ultimate objective of integrating knowledge of these parameters into a prediction of gene expression levels. The theoretical framework of statistical thermodynamics provides a useful framework for doing so, enabling us to predict how gene expression levels depend on transcription factor binding energies and concentrations. We used thermodynamic models, coupled with models of the sequence-dependent binding energies of transcription factors and RNAP, to construct a genotype to phenotype map for the level of repression exhibited by the lac promoter, and tested it experimentally using a set of promoter variants from E. coli strains isolated from different natural environments. For this work, we sought to ``reverse engineer'' naturally occurring promoter sequences to understand how variations in promoter sequence affects gene expression. The natural inverse of this approach is to ``forward engineer'' promoter sequences to obtain targeted levels of gene expression. We used a high precision model of RNAP-DNA sequence dependent binding energy, coupled with a thermodynamic model relating binding energy to gene expression, to predictively design and verify a suite of synthetic E. coli promoters whose expression varied over nearly three orders of magnitude.</p> <p>However, although thermodynamic models enable predictions of mean levels of gene expression, it has become evident that cell-to-cell variability or ``noise'' in gene expression can also play a biologically important role. In order to address this aspect of gene regulation, we developed models based on the chemical master equation framework and used them to explore the noise properties of a number of common E. coli regulatory motifs; these properties included the dependence of the noise on parameters such as transcription factor binding strength and copy number. We then performed experiments in which these parameters were systematically varied and measured the level of variability using mRNA FISH. The results showed a clear dependence of the noise on these parameters, in accord with model predictions.</p> <p>Finally, one shortcoming of the preceding modeling frameworks is that their applicability is largely limited to systems that are already well-characterized, such as the lac promoter. Motivated by this fact, we used a high throughput promoter mutagenesis assay called Sort-Seq to explore the completely uncharacterized transcriptional regulatory DNA of the E. coli mechanosensitive channel of large conductance (MscL). We identified several candidate transcription factor binding sites, and work is continuing to identify the associated proteins.</p>

Structure Prediction of G-Protein Coupled Receptors

<p>G-protein coupled receptors (GPCRs) form a large family of proteins and are very important drug targets. They are membrane proteins, which makes computational prediction of their structure challenging. Homology modeling is further complicated by low sequence similarly of the GPCR superfamily.</p> <p>In this dissertation, we analyze the conserved inter-helical contacts of recently solved crystal structures, and we develop a unified sequence-structural alignment of the GPCR superfamily. We use this method to align 817 human GPCRs, 399 of which are nonolfactory. This alignment can be used to generate high quality homology models for the 817 GPCRs.</p> <p>To refine the provided GPCR homology models we developed the Trihelix sampling method. We use a multi-scale approach to simplify the problem by treating the transmembrane helices as rigid bodies. In contrast to Monte Carlo structure prediction methods, the Trihelix method does a complete local sampling using discretized coordinates for the transmembrane helices. We validate the method on existing structures and apply it to predict the structure of the lactate receptor, HCAR1. For this receptor, we also build extracellular loops by taking into account constraints from three disulfide bonds. Docking of lactate and 3,5-dihydroxybenzoic acid shows likely involvement of three Arg residues on different transmembrane helices in binding a single ligand molecule.</p> <p>Protein structure prediction relies on accurate force fields. We next present an effort to improve the quality of charge assignment for large atomic models. In particular, we introduce the formalism of the polarizable charge equilibration scheme (PQEQ) and we describe its implementation in the molecular simulation package Lammps. PQEQ allows fast on the fly charge assignment even for reactive force fields.</p>