@article{954, abstract = {Understanding the relation between genotype and phenotype remains a major challenge. The difficulty of predicting individual mutation effects, and particularly the interactions between them, has prevented the development of a comprehensive theory that links genotypic changes to their phenotypic effects. We show that a general thermodynamic framework for gene regulation, based on a biophysical understanding of protein-DNA binding, accurately predicts the sign of epistasis in a canonical cis-regulatory element consisting of overlapping RNA polymerase and repressor binding sites. Sign and magnitude of individual mutation effects are sufficient to predict the sign of epistasis and its environmental dependence. Thus, the thermodynamic model offers the correct null prediction for epistasis between mutations across DNA-binding sites. Our results indicate that a predictive theory for the effects of cis-regulatory mutations is possible from first principles, as long as the essential molecular mechanisms and the constraints these impose on a biological system are accounted for.}, author = {Lagator, Mato and Paixao, Tiago and Barton, Nicholas H and Bollback, Jonathan P and Guet, Calin C}, issn = {2050-084X}, journal = {eLife}, publisher = {eLife Sciences Publications}, title = {{On the mechanistic nature of epistasis in a canonical cis-regulatory element}}, doi = {10.7554/eLife.25192}, volume = {6}, year = {2017}, } @article{955, abstract = {Gene expression is controlled by networks of regulatory proteins that interact specifically with external signals and DNA regulatory sequences. These interactions force the network components to co-evolve so as to continually maintain function. Yet, existing models of evolution mostly focus on isolated genetic elements. In contrast, we study the essential process by which regulatory networks grow: the duplication and subsequent specialization of network components. We synthesize a biophysical model of molecular interactions with the evolutionary framework to find the conditions and pathways by which new regulatory functions emerge. We show that specialization of new network components is usually slow, but can be drastically accelerated in the presence of regulatory crosstalk and mutations that promote promiscuous interactions between network components.}, author = {Friedlander, Tamar and Prizak, Roshan and Barton, Nicholas H and Tkacik, Gasper}, issn = {2041-1723}, journal = {Nature Communications}, number = {1}, publisher = {Nature Publishing Group}, title = {{Evolution of new regulatory functions on biophysically realistic fitness landscapes}}, doi = {10.1038/s41467-017-00238-8}, volume = {8}, year = {2017}, } @article{956, abstract = {We study a class of ergodic quantum Markov semigroups on finite-dimensional unital C⁎-algebras. These semigroups have a unique stationary state σ, and we are concerned with those that satisfy a quantum detailed balance condition with respect to σ. We show that the evolution on the set of states that is given by such a quantum Markov semigroup is gradient flow for the relative entropy with respect to σ in a particular Riemannian metric on the set of states. This metric is a non-commutative analog of the 2-Wasserstein metric, and in several interesting cases we are able to show, in analogy with work of Otto on gradient flows with respect to the classical 2-Wasserstein metric, that the relative entropy is strictly and uniformly convex with respect to the Riemannian metric introduced here. As a consequence, we obtain a number of new inequalities for the decay of relative entropy for ergodic quantum Markov semigroups with detailed balance.}, author = {Carlen, Eric and Maas, Jan}, issn = {0022-1236}, journal = {Journal of Functional Analysis}, number = {5}, pages = {1810 -- 1869}, publisher = {Academic Press}, title = {{Gradient flow and entropy inequalities for quantum Markov semigroups with detailed balance}}, doi = {10.1016/j.jfa.2017.05.003}, volume = {273}, year = {2017}, } @inbook{957, abstract = {Small molecule biosensors based on Forster resonance energy transfer (FRET) enable small molecule signaling to be monitored with high spatial and temporal resolution in complex cellular environments. FRET sensors can be constructed by fusing a pair of fluorescent proteins to a suitable recognition domain, such as a member of the solute-binding protein (SBP) superfamily. However, naturally occurring SBPs may be unsuitable for incorporation into FRET sensors due to their low thermostability, which may preclude imaging under physiological conditions, or because the positions of their N- and C-termini may be suboptimal for fusion of fluorescent proteins, which may limit the dynamic range of the resulting sensors. Here, we show how these problems can be overcome using ancestral protein reconstruction and circular permutation. Ancestral protein reconstruction, used as a protein engineering strategy, leverages phylogenetic information to improve the thermostability of proteins, while circular permutation enables the termini of an SBP to be repositioned to maximize the dynamic range of the resulting FRET sensor. We also provide a protocol for cloning the engineered SBPs into FRET sensor constructs using Golden Gate assembly and discuss considerations for in situ characterization of the FRET sensors.}, author = {Clifton, Ben and Whitfield, Jason and Sanchez Romero, Inmaculada and Herde, Michel and Henneberger, Christian and Janovjak, Harald L and Jackson, Colin}, booktitle = {Synthetic Protein Switches}, editor = {Stein, Viktor}, issn = {1064-3745}, pages = {71 -- 87}, publisher = {Springer}, title = {{Ancestral protein reconstruction and circular permutation for improving the stability and dynamic range of FRET sensors}}, doi = {10.1007/978-1-4939-6940-1_5}, volume = {1596}, year = {2017}, } @article{9574, abstract = {Consider the sum X(ξ)=∑ni=1aiξi, where a=(ai)ni=1 is a sequence of non-zero reals and ξ=(ξi)ni=1 is a sequence of i.i.d. Rademacher random variables (that is, Pr[ξi=1]=Pr[ξi=−1]=1/2). The classical Littlewood-Offord problem asks for the best possible upper bound on the concentration probabilities Pr[X=x]. In this paper we study a resilience version of the Littlewood-Offord problem: how many of the ξi is an adversary typically allowed to change without being able to force concentration on a particular value? We solve this problem asymptotically, and present a few interesting open problems.}, author = {Bandeira, Afonso S. and Ferber, Asaf and Kwan, Matthew Alan}, issn = {1571-0653}, journal = {Electronic Notes in Discrete Mathematics}, pages = {93--99}, publisher = {Elsevier}, title = {{Resilience for the Littlewood-Offord problem}}, doi = {10.1016/j.endm.2017.06.025}, volume = {61}, year = {2017}, } @inbook{958, abstract = {Biosensors that exploit Forster resonance energy transfer (FRET) can be used to visualize biological and physiological processes and are capable of providing detailed information in both spatial and temporal dimensions. In a FRET-based biosensor, substrate binding is associated with a change in the relative positions of two fluorophores, leading to a change in FRET efficiency that may be observed in the fluorescence spectrum. As a result, their design requires a ligand-binding protein that exhibits a conformational change upon binding. However, not all ligand-binding proteins produce responsive sensors upon conjugation to fluorescent proteins or dyes, and identifying the optimum locations for the fluorophores often involves labor-intensive iterative design or high-throughput screening. Combining the genetic fusion of a fluorescent protein to the ligand-binding protein with site-specific covalent attachment of a fluorescent dye can allow fine control over the positions of the two fluorophores, allowing the construction of very sensitive sensors. This relies upon the accurate prediction of the locations of the two fluorophores in bound and unbound states. In this chapter, we describe a method for computational identification of dye-attachment sites that allows the use of cysteine modification to attach synthetic dyes that can be paired with a fluorescent protein for the purposes of creating FRET sensors.}, author = {Mitchell, Joshua and Zhang, William and Herde, Michel and Henneberger, Christian and Janovjak, Harald L and O'Mara, Megan and Jackson, Colin}, booktitle = {Synthetic Protein Switches}, editor = {Stein, Viktor}, issn = {1064-3745}, pages = {89 -- 99}, publisher = {Springer}, title = {{Method for developing optical sensors using a synthetic dye fluorescent protein FRET pair and computational modeling and assessment}}, doi = {10.1007/978-1-4939-6940-1_6}, volume = {1596}, year = {2017}, } @article{9588, abstract = {Consider the sum X(ξ)=∑ni=1aiξi , where a=(ai)ni=1 is a sequence of non-zero reals and ξ=(ξi)ni=1 is a sequence of i.i.d. Rademacher random variables (that is, Pr[ξi=1]=Pr[ξi=−1]=1/2 ). The classical Littlewood-Offord problem asks for the best possible upper bound on the concentration probabilities Pr[X=x] . In this paper we study a resilience version of the Littlewood-Offord problem: how many of the ξi is an adversary typically allowed to change without being able to force concentration on a particular value? We solve this problem asymptotically, and present a few interesting open problems.}, author = {Bandeira, Afonso S. and Ferber, Asaf and Kwan, Matthew Alan}, issn = {0001-8708}, journal = {Advances in Mathematics}, pages = {292--312}, publisher = {Elsevier}, title = {{Resilience for the Littlewood–Offord problem}}, doi = {10.1016/j.aim.2017.08.031}, volume = {319}, year = {2017}, } @article{9589, abstract = {We give an asymptotic expression for the expected number of spanning trees in a random graph with a given degree sequence , provided that the number of edges is at least , where is the maximum degree. A key part of our argument involves establishing a concentration result for a certain family of functions over random trees with given degrees, using Prüfer codes.}, author = {Greenhill, Catherine and Isaev, Mikhail and Kwan, Matthew Alan and McKay, Brendan D.}, issn = {0195-6698}, journal = {European Journal of Combinatorics}, pages = {6--25}, publisher = {Elsevier}, title = {{The average number of spanning trees in sparse graphs with given degrees}}, doi = {10.1016/j.ejc.2017.02.003}, volume = {63}, year = {2017}, } @article{9590, abstract = {We show that for any fixed dense graph G and bounded-degree tree T on the same number of vertices, a modest random perturbation of G will typically contain a copy of T . This combines the viewpoints of the well-studied problems of embedding trees into fixed dense graphs and into random graphs, and extends a sizeable body of existing research on randomly perturbed graphs. Specifically, we show that there is c=c(α,Δ) such that if G is an n-vertex graph with minimum degree at least αn, and T is an n-vertex tree with maximum degree at most Δ , then if we add cn uniformly random edges to G, the resulting graph will contain T asymptotically almost surely (as n→∞ ). Our proof uses a lemma concerning the decomposition of a dense graph into super-regular pairs of comparable sizes, which may be of independent interest.}, author = {Krivelevich, Michael and Kwan, Matthew Alan and Sudakov, Benny}, issn = {1095-7146}, journal = {SIAM Journal on Discrete Mathematics}, number = {1}, pages = {155--171}, publisher = {Society for Industrial & Applied Mathematics}, title = {{Bounded-degree spanning trees in randomly perturbed graphs}}, doi = {10.1137/15m1032910}, volume = {31}, year = {2017}, } @phdthesis{961, abstract = {Cell-cell contact formation constitutes the first step in the emergence of multicellularity in evolution, thereby allowing the differentiation of specialized cell types. In metazoan development, cell-cell contact formation is thought to influence cell fate specification, and cell fate specification has been implicated in cell-cell contact formation. However, remarkably little is yet known about whether and how the interaction and feedback between cell-cell contact formation and cell fate specification affect development. Here we identify a positive feedback loop between cell-cell contact duration, morphogen signaling and mesendoderm cell fate specification during zebrafish gastrulation. We show that long lasting cell-cell contacts enhance the competence of prechordal plate (ppl) progenitor cells to respond to Nodal signaling, required for proper ppl cell fate specification. We further show that Nodal signalling romotes ppl cell-cell contact duration, thereby generating an effective positive feedback loop between ppl cell-cell contact duration and cell fate specification. Finally, by using a combination of theoretical modeling and experimentation, we show that this feedback loop determines whether anterior axial mesendoderm cells become ppl progenitors or, instead, turn into endoderm progenitors. Our findings reveal that the gene regulatory networks leading to cell fate diversification within the developing embryo are controlled by the interdependent activities of cell-cell signaling and contact formation.}, author = {Barone, Vanessa}, issn = {2663-337X}, pages = {109}, publisher = {Institute of Science and Technology Austria}, title = {{Cell adhesion and cell fate: An effective feedback loop during zebrafish gastrulation}}, doi = {10.15479/AT:ISTA:th_825}, year = {2017}, } @inproceedings{962, abstract = {We present a new algorithm for model counting of a class of string constraints. In addition to the classic operation of concatenation, our class includes some recursively defined operations such as Kleene closure, and replacement of substrings. Additionally, our class also includes length constraints on the string expressions, which means, by requiring reasoning about numbers, that we face a multi-sorted logic. In the end, our string constraints are motivated by their use in programming for web applications. Our algorithm comprises two novel features: the ability to use a technique of (1) partial derivatives for constraints that are already in a solved form, i.e. a form where its (string) satisfiability is clearly displayed, and (2) non-progression, where cyclic reasoning in the reduction process may be terminated (thus allowing for the algorithm to look elsewhere). Finally, we experimentally compare our model counter with two recent works on model counting of similar constraints, SMC [18] and ABC [5], to demonstrate its superior performance.}, author = {Trinh, Minh and Chu, Duc Hiep and Jaffar, Joxan}, editor = {Majumdar, Rupak and Kunčak, Viktor}, issn = {0302-9743}, location = {Heidelberg, Germany}, pages = {399 -- 418}, publisher = {Springer}, title = {{Model counting for recursively-defined strings}}, doi = {10.1007/978-3-319-63390-9_21}, volume = {10427}, year = {2017}, } @inproceedings{963, abstract = {Network games are widely used as a model for selfish resource-allocation problems. In the classical model, each player selects a path connecting her source and target vertex. The cost of traversing an edge depends on the number of players that traverse it. Thus, it abstracts the fact that different users may use a resource at different times and for different durations, which plays an important role in defining the costs of the users in reality. For example, when transmitting packets in a communication network, routing traffic in a road network, or processing a task in a production system, the traversal of the network involves an inherent delay, and so sharing and congestion of resources crucially depends on time. We study timed network games , which add a time component to network games. Each vertex v in the network is associated with a cost function, mapping the load on v to the price that a player pays for staying in v for one time unit with this load. In addition, each edge has a guard, describing time intervals in which the edge can be traversed, forcing the players to spend time on vertices. Unlike earlier work that add a time component to network games, the time in our model is continuous and cannot be discretized. In particular, players have uncountably many strategies, and a game may have uncountably many pure Nash equilibria. We study properties of timed network games with cost-sharing or congestion cost functions: their stability, equilibrium inefficiency, and complexity. In particular, we show that the answer to the question whether we can restrict attention to boundary strategies, namely ones in which edges are traversed only at the boundaries of guards, is mixed. }, author = {Avni, Guy and Guha, Shibashis and Kupferman, Orna}, issn = {1868-8969}, location = {Aalborg, Denmark}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Timed network games with clocks}}, doi = {10.4230/LIPIcs.MFCS.2017.37}, volume = {83}, year = {2017}, } @article{9660, abstract = {In this paper we discuss how the information contained in atomistic simulations of homogeneous nucleation should be used when fitting the parameters in macroscopic nucleation models. We show how the number of solid and liquid atoms in such simulations can be determined unambiguously by using a Gibbs dividing surface and how the free energy as a function of the number of solid atoms in the nucleus can thus be extracted. We then show that the parameters (the chemical potential, the interfacial free energy, and a Tolman correction) of a model based on classical nucleation theory can be fitted using the information contained in these free-energy profiles but that the parameters in such models are highly correlated. This correlation is unfortunate as it ensures that small errors in the computed free energy surface can give rise to large errors in the extrapolated properties of the fitted model. To resolve this problem we thus propose a method for fitting macroscopic nucleation models that uses simulations of planar interfaces and simulations of three-dimensional nuclei in tandem. We show that when the chemical potentials and the interface energy are pinned to their planar-interface values, more precise estimates for the Tolman length are obtained. Extrapolating the free energy profile obtained from small simulation boxes to larger nuclei is thus more reliable.}, author = {Cheng, Bingqing and Tribello, Gareth A. and Ceriotti, Michele}, issn = {1089-7690}, journal = {The Journal of Chemical Physics}, number = {10}, publisher = {AIP Publishing}, title = {{The Gibbs free energy of homogeneous nucleation: From atomistic nuclei to the planar limit}}, doi = {10.1063/1.4997180}, volume = {147}, year = {2017}, } @article{9661, abstract = {Macroscopic theories of nucleation such as classical nucleation theory envision that clusters of the bulk stable phase form inside the bulk metastable phase. Molecular dynamics simulations are often used to elucidate nucleation mechanisms, by capturing the microscopic configurations of all the atoms. In this paper, we introduce a thermodynamic model that links macroscopic theories and atomic-scale simulations and thus provide a simple and elegant framework for testing the limits of classical nucleation theory.}, author = {Cheng, Bingqing and Ceriotti, Michele}, issn = {1089-7690}, journal = {The Journal of Chemical Physics}, number = {3}, publisher = {AIP Publishing}, title = {{Bridging the gap between atomistic and macroscopic models of homogeneous nucleation}}, doi = {10.1063/1.4973883}, volume = {146}, year = {2017}, } @misc{9707, abstract = {Branching morphogenesis of the epithelial ureteric bud forms the renal collecting duct system and is critical for normal nephron number, while low nephron number is implicated in hypertension and renal disease. Ureteric bud growth and branching requires GDNF signaling from the surrounding mesenchyme to cells at the ureteric bud tips, via the Ret receptor tyrosine kinase and coreceptor Gfrα1; Ret signaling up-regulates transcription factors Etv4 and Etv5, which are also critical for branching. Despite extensive knowledge of the genetic control of these events, it is not understood, at the cellular level, how renal branching morphogenesis is achieved or how Ret signaling influences epithelial cell behaviors to promote this process. Analysis of chimeric embryos previously suggested a role for Ret signaling in promoting cell rearrangements in the nephric duct, but this method was unsuited to study individual cell behaviors during ureteric bud branching. Here, we use Mosaic Analysis with Double Markers (MADM), combined with organ culture and time-lapse imaging, to trace the movements and divisions of individual ureteric bud tip cells. We first examine wild-type clones and then Ret or Etv4 mutant/wild-type clones in which the mutant and wild-type sister cells are differentially and heritably marked by green and red fluorescent proteins. We find that, in normal kidneys, most individual tip cells behave as self-renewing progenitors, some of whose progeny remain at the tips while others populate the growing UB trunks. In Ret or Etv4 MADM clones, the wild-type cells generated at a UB tip are much more likely to remain at, or move to, the new tips during branching and elongation, while their Ret−/− or Etv4−/− sister cells tend to lag behind and contribute only to the trunks. By tracking successive mitoses in a cell lineage, we find that Ret signaling has little effect on proliferation, in contrast to its effects on cell movement. Our results show that Ret/Etv4 signaling promotes directed cell movements in the ureteric bud tips, and suggest a model in which these cell movements mediate branching morphogenesis.}, author = {Riccio, Paul and Cebrián, Christina and Zong, Hui and Hippenmeyer, Simon and Costantini, Frank}, publisher = {Dryad}, title = {{Data from: Ret and Etv4 promote directed movements of progenitor cells during renal branching morphogenesis}}, doi = {10.5061/dryad.pk16b}, year = {2017}, } @misc{9709, abstract = {Across the nervous system, certain population spiking patterns are observed far more frequently than others. A hypothesis about this structure is that these collective activity patterns function as population codewords–collective modes–carrying information distinct from that of any single cell. We investigate this phenomenon in recordings of ∼150 retinal ganglion cells, the retina’s output. We develop a novel statistical model that decomposes the population response into modes; it predicts the distribution of spiking activity in the ganglion cell population with high accuracy. We found that the modes represent localized features of the visual stimulus that are distinct from the features represented by single neurons. Modes form clusters of activity states that are readily discriminated from one another. When we repeated the same visual stimulus, we found that the same mode was robustly elicited. These results suggest that retinal ganglion cells’ collective signaling is endowed with a form of error-correcting code–a principle that may hold in brain areas beyond retina.}, author = {Prentice, Jason and Marre, Olivier and Ioffe, Mark and Loback, Adrianna and Tkačik, Gašper and Berry, Michael}, publisher = {Dryad}, title = {{Data from: Error-robust modes of the retinal population code}}, doi = {10.5061/dryad.1f1rc}, year = {2017}, } @misc{9842, abstract = {Mathematica notebooks used to generate figures.}, author = {Etheridge, Alison and Barton, Nicholas H}, publisher = {Mendeley Data}, title = {{Data for: Establishment in a new habitat by polygenic adaptation}}, doi = {10.17632/nw68fxzjpm.1}, year = {2017}, } @article{642, abstract = {Cauchy problems with SPDEs on the whole space are localized to Cauchy problems on a ball of radius R. This localization reduces various kinds of spatial approximation schemes to finite dimensional problems. The error is shown to be exponentially small. As an application, a numerical scheme is presented which combines the localization and the space and time discretization, and thus is fully implementable.}, author = {Gerencser, Mate and Gyöngy, István}, issn = {0025-5718}, journal = {Mathematics of Computation}, number = {307}, pages = {2373 -- 2397}, publisher = {American Mathematical Society}, title = {{Localization errors in solving stochastic partial differential equations in the whole space}}, doi = {10.1090/mcom/3201}, volume = {86}, year = {2017}, } @misc{6426, abstract = {Synchronous programs are easy to specify because the side effects of an operation are finished by the time the invocation of the operation returns to the caller. Asynchronous programs, on the other hand, are difficult to specify because there are side effects due to pending computation scheduled as a result of the invocation of an operation. They are also difficult to verify because of the large number of possible interleavings of concurrent asynchronous computation threads. We show that specifications and correctness proofs for asynchronous programs can be structured by introducing the fiction, for proof purposes, that intermediate, non-quiescent states of asynchronous operations can be ignored. Then, the task of specification becomes relatively simple and the task of verification can be naturally decomposed into smaller sub-tasks. The sub-tasks iteratively summarize, guided by the structure of an asynchronous program, the atomic effect of non-atomic operations and the synchronous effect of asynchronous operations. This structuring of specifications and proofs corresponds to the introduction of multiple layers of stepwise refinement for asynchronous programs. We present the first proof rule, called synchronization, to reduce asynchronous invocations on a lower layer to synchronous invocations on a higher layer. We implemented our proof method in CIVL and evaluated it on a collection of benchmark programs.}, author = {Henzinger, Thomas A and Kragl, Bernhard and Qadeer, Shaz}, issn = {2664-1690}, pages = {28}, publisher = {IST Austria}, title = {{Synchronizing the asynchronous}}, doi = {10.15479/AT:IST-2018-853-v2-2}, year = {2017}, } @article{643, abstract = {It has been reported that nicotinamide-overload induces oxidative stress associated with insulin resistance, the key feature of type 2 diabetes mellitus (T2DM). This study aimed to investigate the effects of B vitamins in T2DM. Glucose tolerance tests (GTT) were carried out in adult Sprague-Dawley rats treated with or without cumulative doses of B vitamins. More specifically, insulin tolerance tests (ITT) were also carried out in adult Sprague-Dawley rats treated with or without cumulative doses of Vitamin B3. We found that cumulative Vitamin B1 and Vitamin B3 administration significantly increased the plasma H2O2 levels associated with high insulin levels. Only Vitamin B3 reduced muscular and hepatic glycogen contents. Cumulative administration of nicotinic acid, another form of Vitamin B3, also significantly increased plasma insulin level and H2O2 generation. Moreover, cumulative administration of nicotinic acid or nicotinamide impaired glucose metabolism. This study suggested that excess Vitamin B1 and Vitamin B3 caused oxidative stress and insulin resistance.}, author = {Sun, Wuping and Zhai, Ming-Zhu and Zhou, Qian and Qian, Chengrui and Jiang, Changyu}, issn = {0304-4920}, journal = {Chinese Journal of Physiology}, number = {4}, pages = {207 -- 214}, publisher = {Chinese Physiological Society}, title = {{Effects of B vitamins overload on plasma insulin level and hydrogen peroxide generation in rats}}, doi = {10.4077/CJP.2017.BAF469}, volume = {60}, year = {2017}, }