TY - CONF
AB - We study the problem of predicting the future, though only in the probabilistic sense of estimating a future state of a time-varying probability distribution. This is not only an interesting academic problem, but solving this extrapolation problem also has many practical application, e.g. for training classifiers that have to operate under time-varying conditions. Our main contribution is a method for predicting the next step of the time-varying distribution from a given sequence of sample sets from earlier time steps. For this we rely on two recent machine learning techniques: embedding probability distributions into a reproducing kernel Hilbert space, and learning operators by vector-valued regression. We illustrate the working principles and the practical usefulness of our method by experiments on synthetic and real data. We also highlight an exemplary application: training a classifier in a domain adaptation setting without having access to examples from the test time distribution at training time.
AU - Lampert, Christoph
ID - 1858
TI - Predicting the future behavior of a time-varying probability distribution
ER -
TY - CONF
AB - Structural support vector machines (SSVMs) are amongst the best performing models for structured computer vision tasks, such as semantic image segmentation or human pose estimation. Training SSVMs, however, is computationally costly, because it requires repeated calls to a structured prediction subroutine (called \emph{max-oracle}), which has to solve an optimization problem itself, e.g. a graph cut.
In this work, we introduce a new algorithm for SSVM training that is more efficient than earlier techniques when the max-oracle is computationally expensive, as it is frequently the case in computer vision tasks. The main idea is to (i) combine the recent stochastic Block-Coordinate Frank-Wolfe algorithm with efficient hyperplane caching, and (ii) use an automatic selection rule for deciding whether to call the exact max-oracle or to rely on an approximate one based on the cached hyperplanes.
We show experimentally that this strategy leads to faster convergence to the optimum with respect to the number of requires oracle calls, and that this translates into faster convergence with respect to the total runtime when the max-oracle is slow compared to the other steps of the algorithm.
AU - Shah, Neel
AU - Kolmogorov, Vladimir
AU - Lampert, Christoph
ID - 1859
TI - A multi-plane block-coordinate Frank-Wolfe algorithm for training structural SVMs with a costly max-oracle
ER -
TY - CONF
AB - Classifiers for object categorization are usually evaluated by their accuracy on a set of i.i.d. test examples. This provides us with an estimate of the expected error when applying the classifiers to a single new image. In real application, however, classifiers are rarely only used for a single image and then discarded. Instead, they are applied sequentially to many images, and these are typically not i.i.d. samples from a fixed data distribution, but they carry dependencies and their class distribution varies over time. In this work, we argue that the phenomenon of correlated data at prediction time is not a nuisance, but a blessing in disguise. We describe a probabilistic method for adapting classifiers at prediction time without having to retrain them. We also introduce a framework for creating realistically distributed image sequences, which offers a way to benchmark classifier adaptation methods, such as the one we propose. Experiments on the ILSVRC2010 and ILSVRC2012 datasets show that adapting object classification systems at prediction time can significantly reduce their error rate, even with no additional human feedback.
AU - Royer, Amélie
AU - Lampert, Christoph
ID - 1860
TI - Classifier adaptation at prediction time
ER -
TY - JOUR
AB - Continuous-time Markov chains are commonly used in practice for modeling biochemical reaction networks in which the inherent randomness of themolecular interactions cannot be ignored. This has motivated recent research effort into methods for parameter inference and experiment design for such models. The major difficulty is that such methods usually require one to iteratively solve the chemical master equation that governs the time evolution of the probability distribution of the system. This, however, is rarely possible, and even approximation techniques remain limited to relatively small and simple systems. An alternative explored in this article is to base methods on only some low-order moments of the entire probability distribution. We summarize the theory behind such moment-based methods for parameter inference and experiment design and provide new case studies where we investigate their performance.
AU - Ruess, Jakob
AU - Lygeros, John
ID - 1861
IS - 2
JF - ACM Transactions on Modeling and Computer Simulation
TI - Moment-based methods for parameter inference and experiment design for stochastic biochemical reaction networks
VL - 25
ER -
TY - JOUR
AB - The Altshuler–Shklovskii formulas (Altshuler and Shklovskii, BZh Eksp Teor Fiz 91:200, 1986) predict, for any disordered quantum system in the diffusive regime, a universal power law behaviour for the correlation functions of the mesoscopic eigenvalue density. In this paper and its companion (Erdős and Knowles, The Altshuler–Shklovskii formulas for random band matrices I: the unimodular case, 2013), we prove these formulas for random band matrices. In (Erdős and Knowles, The Altshuler–Shklovskii formulas for random band matrices I: the unimodular case, 2013) we introduced a diagrammatic approach and presented robust estimates on general diagrams under certain simplifying assumptions. In this paper, we remove these assumptions by giving a general estimate of the subleading diagrams. We also give a precise analysis of the leading diagrams which give rise to the Altschuler–Shklovskii power laws. Moreover, we introduce a family of general random band matrices which interpolates between real symmetric (β = 1) and complex Hermitian (β = 2) models, and track the transition for the mesoscopic density–density correlation. Finally, we address the higher-order correlation functions by proving that they behave asymptotically according to a Gaussian process whose covariance is given by the Altshuler–Shklovskii formulas.
AU - Erdös, László
AU - Knowles, Antti
ID - 1864
IS - 3
JF - Annales Henri Poincare
TI - The Altshuler–Shklovskii formulas for random band matrices II: The general case
VL - 16
ER -
TY - JOUR
AB - The plant hormone auxin and its directional transport are known to play a crucial role in defining the embryonic axis and subsequent development of the body plan. Although the role of PIN auxin efflux transporters has been clearly assigned during embryonic shoot and root specification, the role of the auxin influx carriers AUX1 and LIKE-AUX1 (LAX) proteins is not well established. Here, we used chemical and genetic tools on Brassica napus microspore-derived embryos and Arabidopsis thaliana zygotic embryos, and demonstrate that AUX1, LAX1 and LAX2 are required for both shoot and root pole formation, in concert with PIN efflux carriers. Furthermore, we uncovered a positive-feedback loop betweenMONOPTEROS(ARF5)-dependent auxin signalling and auxin transport. ThisMONOPTEROSdependent transcriptional regulation of auxin influx (AUX1, LAX1 and LAX2) and auxin efflux (PIN1 and PIN4) carriers by MONOPTEROS helps to maintain proper auxin transport to the root tip. These results indicate that auxin-dependent cell specification during embryo development requires balanced auxin transport involving both influx and efflux mechanisms, and that this transport is maintained by a positive transcriptional feedback on auxin signalling.
AU - Robert, Hélène
AU - Grunewald, Wim
AU - Sauer, Michael
AU - Cannoot, Bernard
AU - Soriano, Mercedes
AU - Swarup, Ranjan
AU - Weijers, Dolf
AU - Bennett, Malcolm
AU - Boutilier, Kim
AU - Friml, Jirí
ID - 1865
IS - 4
JF - Development
TI - Plant embryogenesis requires AUX/LAX-mediated auxin influx
VL - 142
ER -
TY - JOUR
AU - Henzinger, Thomas A
AU - Raskin, Jean
ID - 1866
IS - 2
JF - Communications of the ACM
TI - The equivalence problem for finite automata: Technical perspective
VL - 58
ER -
TY - JOUR
AB - Cultured mammalian cells essential are model systems in basic biology research, production platforms of proteins for medical use, and testbeds in synthetic biology. Flavin cofactors, in particular flavin mononucleotide (FMN) and flavin adenine dinucleotide (FAD), are critical for cellular redox reactions and sense light in naturally occurring photoreceptors and optogenetic tools. Here, we quantified flavin contents of commonly used mammalian cell lines. We first compared three procedures for extraction of free and noncovalently protein-bound flavins and verified extraction using fluorescence spectroscopy. For separation, two CE methods with different BGEs were established, and detection was performed by LED-induced fluorescence with limit of detections (LODs 0.5-3.8 nM). We found that riboflavin (RF), FMN, and FAD contents varied significantly between cell lines. RF (3.1-14 amol/cell) and FAD (2.2-17.0 amol/cell) were the predominant flavins, while FMN (0.46-3.4 amol/cell) was found at markedly lower levels. Observed flavin contents agree with those previously extracted from mammalian tissues, yet reduced forms of RF were detected that were not described previously. Quantification of flavins in mammalian cell lines will allow a better understanding of cellular redox reactions and optogenetic tools.
AU - Hühner, Jens
AU - Inglés Prieto, Álvaro
AU - Neusüß, Christian
AU - Lämmerhofer, Michael
AU - Janovjak, Harald L
ID - 1867
IS - 4
JF - Electrophoresis
TI - Quantification of riboflavin, flavin mononucleotide, and flavin adenine dinucleotide in mammalian model cells by CE with LED-induced fluorescence detection
VL - 36
ER -
TY - JOUR
AB - We investigate high-dimensional nonlinear dynamical systems exhibiting multiple resonances under adiabatic parameter variations. Our motivations come from experimental considerations where time-dependent sweeping of parameters is a practical approach to probing and characterizing the bifurcations of the system. The question is whether bifurcations so detected are faithful representations of the bifurcations intrinsic to the original stationary system. Utilizing a harmonically forced, closed fluid flow system that possesses multiple resonances and solving the Navier-Stokes equation under proper boundary conditions, we uncover the phenomenon of the early effect. Specifically, as a control parameter, e.g., the driving frequency, is adiabatically increased from an initial value, resonances emerge at frequency values that are lower than those in the corresponding stationary system. The phenomenon is established by numerical characterization of physical quantities through the resonances, which include the kinetic energy and the vorticity field, and a heuristic analysis based on the concept of instantaneous frequency. A simple formula is obtained which relates the resonance points in the time-dependent and time-independent systems. Our findings suggest that, in general, any true bifurcation of a nonlinear dynamical system can be unequivocally uncovered through adiabatic parameter sweeping, in spite of a shift in the bifurcation point, which is of value to experimental studies of nonlinear dynamical systems.
AU - Park, Youngyong
AU - Do, Younghae
AU - Altmeyer, Sebastian
AU - Lai, Yingcheng
AU - Lee, Gyuwon
ID - 1868
IS - 2
JF - Physical Review E
SN - 1539-3755
TI - Early effect in time-dependent, high-dimensional nonlinear dynamical systems with multiple resonances
VL - 91
ER -
TY - JOUR
AB - The plant hormone auxin is a key regulator of plant growth and development. Differences in auxin distribution within tissues are mediated by the polar auxin transport machinery, and cellular auxin responses occur depending on changes in cellular auxin levels. Multiple receptor systems at the cell surface and in the interior operate to sense and interpret fluctuations in auxin distribution that occur during plant development. Until now, three proteins or protein complexes that can bind auxin have been identified. SCFTIR1 [a SKP1-cullin-1-F-box complex that contains transport inhibitor response 1 (TIR1) as the F-box protein] and S-phase-kinaseassociated protein 2 (SKP2) localize to the nucleus, whereas auxinbinding protein 1 (ABP1), predominantly associates with the endoplasmic reticulum and cell surface. In this Cell Science at a Glance article, we summarize recent discoveries in the field of auxin transport and signaling that have led to the identification of new components of these pathways, as well as their mutual interaction.
AU - Grones, Peter
AU - Friml, Jirí
ID - 1871
IS - 1
JF - Journal of Cell Science
TI - Auxin transporters and binding proteins at a glance
VL - 128
ER -
TY - JOUR
AB - We consider partially observable Markov decision processes (POMDPs) with limit-average payoff, where a reward value in the interval [0,1] is associated with every transition, and the payoff of an infinite path is the long-run average of the rewards. We consider two types of path constraints: (i) a quantitative constraint defines the set of paths where the payoff is at least a given threshold λ1ε(0,1]; and (ii) a qualitative constraint which is a special case of the quantitative constraint with λ1=1. We consider the computation of the almost-sure winning set, where the controller needs to ensure that the path constraint is satisfied with probability 1. Our main results for qualitative path constraints are as follows: (i) the problem of deciding the existence of a finite-memory controller is EXPTIME-complete; and (ii) the problem of deciding the existence of an infinite-memory controller is undecidable. For quantitative path constraints we show that the problem of deciding the existence of a finite-memory controller is undecidable. We also present a prototype implementation of our EXPTIME algorithm and experimental results on several examples.
AU - Chatterjee, Krishnendu
AU - Chmelik, Martin
ID - 1873
JF - Artificial Intelligence
TI - POMDPs under probabilistic semantics
VL - 221
ER -
TY - JOUR
AB - The hippocampal region, comprising the hippocampal formation and the parahippocampal region, has been one of the most intensively studied parts of the brain for decades. Better understanding of its functional diversity and complexity has led to an increased demand for specificity in experimental procedures and manipulations. In view of the complex 3D structure of the hippocampal region, precisely positioned experimental approaches require a fine-grained architectural description that is available and readable to experimentalists lacking detailed anatomical experience. In this paper, we provide the first cyto- and chemoarchitectural description of the hippocampal formation and parahippocampal region in the rat at high resolution and in the three standard sectional planes: coronal, horizontal and sagittal. The atlas uses a series of adjacent sections stained for neurons and for a number of chemical marker substances, particularly parvalbumin and calbindin. All the borders defined in one plane have been cross-checked against their counterparts in the other two planes. The entire dataset will be made available as a web-based interactive application through the Rodent Brain WorkBench (http://www.rbwb.org) which, together with this paper, provides a unique atlas resource.
AU - Boccara, Charlotte
AU - Kjønigsen, Lisa
AU - Hammer, Ingvild
AU - Bjaalie, Jan
AU - Leergaard, Trygve
AU - Witter, Menno
ID - 1874
IS - 7
JF - Hippocampus
TI - A three-plane architectonic atlas of the rat hippocampal region
VL - 25
ER -
TY - JOUR
AB - Petrocoptis is a small genus of chasmophytic plants endemic to the Iberian Peninsula, with some localized populations in the French Pyrenees. Within the genus, a dozen species have been recognized based on morphological diversity, most of them with limited distribution area, in small populations and frequently with potential threats to their survival. To date, however, a molecular evaluation of the current systematic treatments has not been carried out. The aim of the present study is to infer phylogenetic relationships among its subordinate taxa by using plastidial rps16 intron and nuclear internal transcribed spacer (ITS) DNA sequences; and evaluate the phylogenetic placement of the genus Petrocoptis within the family Caryophyllaceae. The monophyly of Petrocoptis is supported by both ITS and rps16 intron sequence analyses. Furthermore, time estimates using BEAST analyses indicate a Middle to Late Miocene diversification (10.59 Myr, 6.44–15.26 Myr highest posterior densities [HPD], for ITS; 14.30 Myr, 8.61–21.00 Myr HPD, for rps16 intron).
AU - Cires Rodriguez, Eduardo
AU - Prieto, José
ID - 1878
IS - 2
JF - Journal of Plant Research
TI - Phylogenetic relationships of Petrocoptis A. Braun ex Endl. (Caryophyllaceae), a discussed genus from the Iberian Peninsula
VL - 128
ER -
TY - JOUR
AB - When electron microscopy (EM) was introduced in the 1930s it gave scientists their first look into the nanoworld of cells. Over the last 80 years EM has vastly increased our understanding of the complex cellular structures that underlie the diverse functions that cells need to maintain life. One drawback that has been difficult to overcome was the inherent lack of volume information, mainly due to the limit on the thickness of sections that could be viewed in a transmission electron microscope (TEM). For many years scientists struggled to achieve three-dimensional (3D) EM using serial section reconstructions, TEM tomography, and scanning EM (SEM) techniques such as freeze-fracture. Although each technique yielded some special information, they required a significant amount of time and specialist expertise to obtain even a very small 3D EM dataset. Almost 20 years ago scientists began to exploit SEMs to image blocks of embedded tissues and perform serial sectioning of these tissues inside the SEM chamber. Using first focused ion beams (FIB) and subsequently robotic ultramicrotomes (serial block-face, SBF-SEM) microscopists were able to collect large volumes of 3D EM information at resolutions that could address many important biological questions, and do so in an efficient manner. We present here some examples of 3D EM taken from the many diverse specimens that have been imaged in our core facility. We propose that the next major step forward will be to efficiently correlate functional information obtained using light microscopy (LM) with 3D EM datasets to more completely investigate the important links between cell structures and their functions.
AU - Kremer, A
AU - Lippens, Stefaan
AU - Bartunkova, Sonia
AU - Asselbergh, Bob
AU - Blanpain, Cendric
AU - Fendrych, Matyas
AU - Goossens, A
AU - Holt, Matthew
AU - Janssens, Sophie
AU - Krols, Michiel
AU - Larsimont, Jean
AU - Mc Guire, Conor
AU - Nowack, Moritz
AU - Saelens, Xavier
AU - Schertel, Andreas
AU - Schepens, B
AU - Slezak, M
AU - Timmerman, Vincent
AU - Theunis, Clara
AU - Van Brempt, Ronald
AU - Visser, Y
AU - Guérin, Christophe
ID - 1879
IS - 2
JF - Journal of Microscopy
TI - Developing 3D SEM in a broad biological context
VL - 259
ER -
TY - JOUR
AB - We investigate the relation between Bose-Einstein condensation (BEC) and superfluidity in the ground state of a one-dimensional model of interacting bosons in a strong random potential. We prove rigorously that in a certain parameter regime the superfluid fraction can be arbitrarily small while complete BEC prevails. In another regime there is both complete BEC and complete superfluidity, despite the strong disorder
AU - Könenberg, Martin
AU - Moser, Thomas
AU - Seiringer, Robert
AU - Yngvason, Jakob
ID - 1880
JF - New Journal of Physics
TI - Superfluid behavior of a Bose-Einstein condensate in a random potential
VL - 17
ER -
TY - CONF
AB - We provide a framework for compositional and iterative design and verification of systems with quantitative information, such as rewards, time or energy. It is based on disjunctive modal transition systems where we allow actions to bear various types of quantitative information. Throughout the design process the actions can be further refined and the information made more precise. We show how to compute the results of standard operations on the systems, including the quotient (residual), which has not been previously considered for quantitative non-deterministic systems. Our quantitative framework has close connections to the modal nu-calculus and is compositional with respect to general notions of distances between systems and the standard operations.
AU - Fahrenberg, Uli
AU - Kretinsky, Jan
AU - Legay, Axel
AU - Traonouez, Louis
ID - 1882
TI - Compositionality for quantitative specifications
VL - 8997
ER -
TY - JOUR
AB - We introduce a one-parametric family of tree growth models, in which branching probabilities decrease with branch age τ as τ-α. Depending on the exponent α, the scaling of tree depth with tree size n displays a transition between the logarithmic scaling of random trees and an algebraic growth. At the transition (α=1) tree depth grows as (logn)2. This anomalous scaling is in good agreement with the trend observed in evolution of biological species, thus providing a theoretical support for age-dependent speciation and associating it to the occurrence of a critical point.
AU - Keller-Schmidt, Stephanie
AU - Tugrul, Murat
AU - Eguíluz, Víctor
AU - Hernandez Garcia, Emilio
AU - Klemm, Konstantin
ID - 1883
IS - 2
JF - Physical Review E Statistical Nonlinear and Soft Matter Physics
TI - Anomalous scaling in an age-dependent branching model
VL - 91
ER -
TY - JOUR
AB - The concept of positional information is central to our understanding of how cells determine their location in a multicellular structure and thereby their developmental fates. Nevertheless, positional information has neither been defined mathematically nor quantified in a principled way. Here we provide an information-theoretic definition in the context of developmental gene expression patterns and examine the features of expression patterns that affect positional information quantitatively. We connect positional information with the concept of positional error and develop tools to directly measure information and error from experimental data. We illustrate our framework for the case of gap gene expression patterns in the early Drosophila embryo and show how information that is distributed among only four genes is sufficient to determine developmental fates with nearly single-cell resolution. Our approach can be generalized to a variety of different model systems; procedures and examples are discussed in detail.
AU - Tkacik, Gasper
AU - Dubuis, Julien
AU - Petkova, Mariela
AU - Gregor, Thomas
ID - 1885
IS - 1
JF - Genetics
TI - Positional information, positional error, and readout precision in morphogenesis: A mathematical framework
VL - 199
ER -
TY - JOUR
AB - We numerically investigate the distribution of extrema of 'chaotic' Laplacian eigenfunctions on two-dimensional manifolds. Our contribution is two-fold: (a) we count extrema on grid graphs with a small number of randomly added edges and show the behavior to coincide with the 1957 prediction of Longuet-Higgins for the continuous case and (b) we compute the regularity of their spatial distribution using discrepancy, which is a classical measure from the theory of Monte Carlo integration. The first part suggests that grid graphs with randomly added edges should behave like two-dimensional surfaces with ergodic geodesic flow; in the second part we show that the extrema are more regularly distributed in space than the grid Z2.
AU - Pausinger, Florian
AU - Steinerberger, Stefan
ID - 1938
IS - 6
JF - Physics Letters, Section A
TI - On the distribution of local extrema in quantum chaos
VL - 379
ER -
TY - JOUR
AU - Dereziński, Jan
AU - Napiórkowski, Marcin M
ID - 1939
IS - 7
JF - Annales Henri Poincare
TI - Erratum to: Excitation spectrum of interacting bosons in the Mean-Field Infinite-Volume limit
VL - 16
ER -
TY - JOUR
AB - We typically think of cells as responding to external signals independently by regulating their gene expression levels, yet they often locally exchange information and coordinate. Can such spatial coupling be of benefit for conveying signals subject to gene regulatory noise? Here we extend our information-theoretic framework for gene regulation to spatially extended systems. As an example, we consider a lattice of nuclei responding to a concentration field of a transcriptional regulator (the "input") by expressing a single diffusible target gene. When input concentrations are low, diffusive coupling markedly improves information transmission; optimal gene activation functions also systematically change. A qualitatively new regulatory strategy emerges where individual cells respond to the input in a nearly step-like fashion that is subsequently averaged out by strong diffusion. While motivated by early patterning events in the Drosophila embryo, our framework is generically applicable to spatially coupled stochastic gene expression models.
AU - Sokolowski, Thomas R
AU - Tkacik, Gasper
ID - 1940
IS - 6
JF - Physical Review E Statistical Nonlinear and Soft Matter Physics
TI - Optimizing information flow in small genetic networks. IV. Spatial coupling
VL - 91
ER -
TY - JOUR
AU - Rakusová, Hana
AU - Fendrych, Matyas
AU - Friml, Jirí
ID - 1944
IS - 2
JF - Current Opinion in Plant Biology
TI - Intracellular trafficking and PIN-mediated cell polarity during tropic responses in plants
VL - 23
ER -
TY - CONF
AB - We present a method and a tool for generating succinct representations of sets of concurrent traces. We focus on trace sets that contain all correct or all incorrect permutations of events from a given trace. We represent trace sets as HB-Formulas that are Boolean combinations of happens-before constraints between events. To generate a representation of incorrect interleavings, our method iteratively explores interleavings that violate the specification and gathers generalizations of the discovered interleavings into an HB-Formula; its complement yields a representation of correct interleavings.
We claim that our trace set representations can drive diverse verification, fault localization, repair, and synthesis techniques for concurrent programs. We demonstrate this by using our tool in three case studies involving synchronization synthesis, bug summarization, and abstraction refinement based verification. In each case study, our initial experimental results have been promising.
In the first case study, we present an algorithm for inferring missing synchronization from an HB-Formula representing correct interleavings of a given trace. The algorithm applies rules to rewrite specific patterns in the HB-Formula into locks, barriers, and wait-notify constructs. In the second case study, we use an HB-Formula representing incorrect interleavings for bug summarization. While the HB-Formula itself is a concise counterexample summary, we present additional inference rules to help identify specific concurrency bugs such as data races, define-use order violations, and two-stage access bugs. In the final case study, we present a novel predicate learning procedure that uses HB-Formulas representing abstract counterexamples to accelerate counterexample-guided abstraction refinement (CEGAR). In each iteration of the CEGAR loop, the procedure refines the abstraction to eliminate multiple spurious abstract counterexamples drawn from the HB-Formula.
AU - Gupta, Ashutosh
AU - Henzinger, Thomas A
AU - Radhakrishna, Arjun
AU - Samanta, Roopsha
AU - Tarrach, Thorsten
ID - 1992
SN - 978-1-4503-3300-9
TI - Succinct representation of concurrent trace sets
ER -
TY - JOUR
AB - The fitness effects of symbionts on their hosts can be context-dependent, with usually benign symbionts causing detrimental effects when their hosts are stressed, or typically parasitic symbionts providing protection towards their hosts (e.g. against pathogen infection). Here, we studied the novel association between the invasive garden ant Lasius neglectus and its fungal ectosymbiont Laboulbenia formicarum for potential costs and benefits. We tested ants with different Laboulbenia levels for their survival and immunity under resource limitation and exposure to the obligate killing entomopathogen Metarhizium brunneum. While survival of L. neglectus workers under starvation was significantly decreased with increasing Laboulbenia levels, host survival under Metarhizium exposure increased with higher levels of the ectosymbiont, suggesting a symbiont-mediated anti-pathogen protection, which seems to be driven mechanistically by both improved sanitary behaviours and an upregulated immune system. Ants with high Laboulbenia levels showed significantly longer self-grooming and elevated expression of immune genes relevant for wound repair and antifungal responses (β-1,3-glucan binding protein, Prophenoloxidase), compared with ants carrying low Laboulbenia levels. This suggests that the ectosymbiont Laboulbenia formicarum weakens its ant host by either direct resource exploitation or the costs of an upregulated behavioural and immunological response, which, however, provides a prophylactic protection upon later exposure to pathogens.
AU - Konrad, Matthias
AU - Grasse, Anna V
AU - Tragust, Simon
AU - Cremer, Sylvia
ID - 1993
IS - 1799
JF - Proceedings of the Royal Society of London Series B Biological Sciences
TI - Anti-pathogen protection versus survival costs mediated by an ectosymbiont in an ant host
VL - 282
ER -
TY - JOUR
AB - We prove that the three-state toric homogeneous Markov chain model has Markov degree two. In algebraic terminology this means, that a certain class of toric ideals is generated by quadratic binomials. This was conjectured by Haws, Martin del Campo, Takemura and Yoshida, who proved that they are generated by degree six binomials.
AU - Noren, Patrik
ID - 1997
IS - May-June
JF - Journal of Symbolic Computation
TI - The three-state toric homogeneous Markov chain model has Markov degree two
VL - 68/Part 2
ER -
TY - JOUR
AB - The monotone secant conjecture posits a rich class of polynomial systems, all of whose solutions are real. These systems come from the Schubert calculus on flag manifolds, and the monotone secant conjecture is a compelling generalization of the Shapiro conjecture for Grassmannians (Theorem of Mukhin, Tarasov, and Varchenko). We present some theoretical evidence for this conjecture, as well as computational evidence obtained by 1.9 teraHertz-years of computing, and we discuss some of the phenomena we observed in our data.
AU - Hein, Nicolas
AU - Hillar, Christopher
AU - Martin Del Campo Sanchez, Abraham
AU - Sottile, Frank
AU - Teitler, Zach
ID - 2006
IS - 3
JF - Experimental Mathematics
TI - The monotone secant conjecture in the real Schubert calculus
VL - 24
ER -
TY - JOUR
AB - The paper describes a generalized iterative proportional fitting procedure that can be used for maximum likelihood estimation in a special class of the general log-linear model. The models in this class, called relational, apply to multivariate discrete sample spaces that do not necessarily have a Cartesian product structure and may not contain an overall effect. When applied to the cell probabilities, the models without the overall effect are curved exponential families and the values of the sufficient statistics are reproduced by the MLE only up to a constant of proportionality. The paper shows that Iterative Proportional Fitting, Generalized Iterative Scaling, and Improved Iterative Scaling fail to work for such models. The algorithm proposed here is based on iterated Bregman projections. As a by-product, estimates of the multiplicative parameters are also obtained. An implementation of the algorithm is available as an R-package.
AU - Klimova, Anna
AU - Rudas, Tamás
ID - 2008
IS - 3
JF - Scandinavian Journal of Statistics
TI - Iterative scaling in curved exponential families
VL - 42
ER -
TY - JOUR
AB - The concepts of faithfulness and strong-faithfulness are important for statistical learning of graphical models. Graphs are not sufficient for describing the association structure of a discrete distribution. Hypergraphs representing hierarchical log-linear models are considered instead, and the concept of parametric (strong-) faithfulness with respect to a hypergraph is introduced. Strong-faithfulness ensures the existence of uniformly consistent parameter estimators and enables building uniformly consistent procedures for a hypergraph search. The strength of association in a discrete distribution can be quantified with various measures, leading to different concepts of strong-faithfulness. Lower and upper bounds for the proportions of distributions that do not satisfy strong-faithfulness are computed for different parameterizations and measures of association.
AU - Klimova, Anna
AU - Uhler, Caroline
AU - Rudas, Tamás
ID - 2014
IS - 7
JF - Computational Statistics & Data Analysis
TI - Faithfulness and learning hypergraphs from discrete distributions
VL - 87
ER -
TY - JOUR
AB - Small GTP-binding proteins of the Ras superfamily play diverse roles in intracellular trafficking. Among them, the Rab, Arf, and Rho families function in successive steps of vesicle transport, in forming vesicles from donor membranes, directing vesicle trafficking toward target membranes and docking vesicles onto target membranes. These proteins act as molecular switches that are controlled by a cycle of GTP binding and hydrolysis regulated by guanine nucleotide exchange factors (GEFs) and GTPase-activating proteins (GAPs). In this study we explored the role of GAPs in the regulation of the endocytic pathway using fluorescently labeled yeast mating pheromone α-factor. Among 25 non-essential GAP mutants, we found that deletion of the GLO3 gene, encoding Arf-GAP protein, caused defective internalization of fluorescently labeled α-factor. Quantitative analysis revealed that glo3Δ cells show defective α-factor binding to the cell surface. Interestingly, Ste2p, the α-factor receptor, was mis-localized from the plasma membrane to the vacuole in glo3Δ cells. Domain deletion mutants of Glo3p revealed that a GAP-independent function, as well as the GAP activity, of Glo3p is important for both α-factor binding and Ste2p localization at the cell surface. Additionally, we found that deletion of the GLO3 gene affects the size and number of Arf1p-residing Golgi compartments and causes a defect in transport from the TGN to the plasma membrane. Furthermore, we demonstrated that glo3Δ cells were defective in the late endosome-to-TGN transport pathway, but not in the early endosome-to-TGN transport pathway. These findings suggest novel roles for Arf-GAP Glo3p in endocytic recycling of cell surface proteins.
AU - Kawada, Daiki
AU - Kobayashi, Hiromu
AU - Tomita, Tsuyoshi
AU - Nakata, Eisuke
AU - Nagano, Makoto
AU - Siekhaus, Daria E
AU - Toshima, Junko
AU - Toshimaa, Jiro
ID - 2025
IS - 1
JF - Biochimica et Biophysica Acta - Molecular Cell Research
TI - The yeast Arf-GAP Glo3p is required for the endocytic recycling of cell surface proteins
VL - 1853
ER -
TY - JOUR
AB - A hybrid-parallel direct-numerical-simulation method with application to turbulent Taylor-Couette flow is presented. The Navier-Stokes equations are discretized in cylindrical coordinates with the spectral Fourier-Galerkin method in the axial and azimuthal directions, and high-order finite differences in the radial direction. Time is advanced by a second-order, semi-implicit projection scheme, which requires the solution of five Helmholtz/Poisson equations, avoids staggered grids and renders very small slip velocities. Nonlinear terms are evaluated with the pseudospectral method. The code is parallelized using a hybrid MPI-OpenMP strategy, which, compared with a flat MPI parallelization, is simpler to implement, allows to reduce inter-node communications and MPI overhead that become relevant at high processor-core counts, and helps to contain the memory footprint. A strong scaling study shows that the hybrid code maintains scalability up to more than 20,000 processor cores and thus allows to perform simulations at higher resolutions than previously feasible. In particular, it opens up the possibility to simulate turbulent Taylor-Couette flows at Reynolds numbers up to O(105). This enables to probe hydrodynamic turbulence in Keplerian flows in experimentally relevant regimes.
AU - Shi, Liang
AU - Rampp, Markus
AU - Hof, Björn
AU - Avila, Marc
ID - 2030
IS - 1
JF - Computers and Fluids
TI - A hybrid MPI-OpenMP parallel implementation for pseudospectral simulations with application to Taylor-Couette flow
VL - 106
ER -
TY - JOUR
AB - Opacity is a generic security property, that has been defined on (non-probabilistic) transition systems and later on Markov chains with labels. For a secret predicate, given as a subset of runs, and a function describing the view of an external observer, the value of interest for opacity is a measure of the set of runs disclosing the secret. We extend this definition to the richer framework of Markov decision processes, where non-deterministicchoice is combined with probabilistic transitions, and we study related decidability problems with partial or complete observation hypotheses for the schedulers. We prove that all questions are decidable with complete observation and ω-regular secrets. With partial observation, we prove that all quantitative questions are undecidable but the question whether a system is almost surely non-opaquebecomes decidable for a restricted class of ω-regular secrets, as well as for all ω-regular secrets under finite-memory schedulers.
AU - Bérard, Béatrice
AU - Chatterjee, Krishnendu
AU - Sznajder, Nathalie
ID - 2034
IS - 1
JF - Information Processing Letters
TI - Probabilistic opacity for Markov decision processes
VL - 115
ER -
TY - JOUR
AB - Considering a continuous self-map and the induced endomorphism on homology, we study the eigenvalues and eigenspaces of the latter. Taking a filtration of representations, we define the persistence of the eigenspaces, effectively introducing a hierarchical organization of the map. The algorithm that computes this information for a finite sample is proved to be stable, and to give the correct answer for a sufficiently dense sample. Results computed with an implementation of the algorithm provide evidence of its practical utility.
AU - Edelsbrunner, Herbert
AU - Jablonski, Grzegorz
AU - Mrozek, Marian
ID - 2035
IS - 5
JF - Foundations of Computational Mathematics
TI - The persistent homology of a self-map
VL - 15
ER -
TY - JOUR
AB - We study the spectrum of a large system of N identical bosons interacting via a two-body potential with strength 1/N. In this mean-field regime, Bogoliubov's theory predicts that the spectrum of the N-particle Hamiltonian can be approximated by that of an effective quadratic Hamiltonian acting on Fock space, which describes the fluctuations around a condensed state. Recently, Bogoliubov's theory has been justified rigorously in the case that the low-energy eigenvectors of the N-particle Hamiltonian display complete condensation in the unique minimizer of the corresponding Hartree functional. In this paper, we shall justify Bogoliubov's theory for the high-energy part of the spectrum of the N-particle Hamiltonian corresponding to (non-linear) excited states of the Hartree functional. Moreover, we shall extend the existing results on the excitation spectrum to the case of non-uniqueness and/or degeneracy of the Hartree minimizer. In particular, the latter covers the case of rotating Bose gases, when the rotation speed is large enough to break the symmetry and to produce multiple quantized vortices in the Hartree minimizer.
AU - Nam, Phan
AU - Seiringer, Robert
ID - 2085
IS - 2
JF - Archive for Rational Mechanics and Analysis
TI - Collective excitations of Bose gases in the mean-field regime
VL - 215
ER -
TY - JOUR
AB - We consider the spectral statistics of large random band matrices on mesoscopic energy scales. We show that the correlation function of the local eigenvalue density exhibits a universal power law behaviour that differs from the Wigner-Dyson- Mehta statistics. This law had been predicted in the physics literature by Altshuler and Shklovskii in (Zh Eksp Teor Fiz (Sov Phys JETP) 91(64):220(127), 1986); it describes the correlations of the eigenvalue density in general metallic sampleswith weak disorder. Our result rigorously establishes the Altshuler-Shklovskii formulas for band matrices. In two dimensions, where the leading term vanishes owing to an algebraic cancellation, we identify the first non-vanishing term and show that it differs substantially from the prediction of Kravtsov and Lerner in (Phys Rev Lett 74:2563-2566, 1995). The proof is given in the current paper and its companion (Ann. H. Poincaré. arXiv:1309.5107, 2014).
AU - Erdös, László
AU - Knowles, Antti
ID - 2166
IS - 3
JF - Communications in Mathematical Physics
TI - The Altshuler-Shklovskii formulas for random band matrices I: the unimodular case
VL - 333
ER -
TY - JOUR
AB - We prove that nonlinear Gibbs measures can be obtained from the corresponding many-body, grand-canonical, quantum Gibbs states, in a mean-field limit where the temperature T diverges and the interaction strength behaves as 1/T. We proceed by characterizing the interacting Gibbs state as minimizing a functional counting the free-energy relatively to the non-interacting case. We then perform an infinite-dimensional analogue of phase-space semiclassical analysis, using fine properties of the quantum relative entropy, the link between quantum de Finetti measures and upper/lower symbols in a coherent state basis, as well as Berezin-Lieb type inequalities. Our results cover the measure built on the defocusing nonlinear Schrödinger functional on a finite interval, as well as smoother interactions in dimensions d 2.
AU - Lewin, Mathieu
AU - Phan Thanh, Nam
AU - Rougerie, Nicolas
ID - 473
JF - Journal de l'Ecole Polytechnique - Mathematiques
TI - Derivation of nonlinear gibbs measures from many-body quantum mechanics
VL - 2
ER -
TY - JOUR
AB - Dendritic cells are potent antigen-presenting cells endowed with the unique ability to initiate adaptive immune responses upon inflammation. Inflammatory processes are often associated with an increased production of serotonin, which operates by activating specific receptors. However, the functional role of serotonin receptors in regulation of dendritic cell functions is poorly understood. Here, we demonstrate that expression of serotonin receptor 5-HT7 (5-HT7TR) as well as its downstream effector Cdc42 is upregulated in dendritic cells upon maturation. Although dendritic cell maturation was independent of 5-HT7TR, receptor stimulation affected dendritic cell morphology through Cdc42-mediated signaling. In addition, basal activity of 5-HT7TR was required for the proper expression of the chemokine receptor CCR7, which is a key factor that controls dendritic cell migration. Consistent with this, we observed that 5-HT7TR enhances chemotactic motility of dendritic cells in vitro by modulating their directionality and migration velocity. Accordingly, migration of dendritic cells in murine colon explants was abolished after pharmacological receptor inhibition. Our results indicate that there is a crucial role for 5-HT7TR-Cdc42-mediated signaling in the regulation of dendritic cell morphology and motility, suggesting that 5-HT7TR could be a new target for treatment of a variety of inflammatory and immune disorders.
AU - Holst, Katrin
AU - Guseva, Daria
AU - Schindler, Susann
AU - Sixt, Michael K
AU - Braun, Armin
AU - Chopra, Himpriya
AU - Pabst, Oliver
AU - Ponimaskin, Evgeni
ID - 477
IS - 15
JF - Journal of Cell Science
TI - The serotonin receptor 5-HT7R regulates the morphology and migratory properties of dendritic cells
VL - 128
ER -
TY - JOUR
AB - We consider two-player games played on weighted directed graphs with mean-payoff and total-payoff objectives, two classical quantitative objectives. While for single-dimensional games the complexity and memory bounds for both objectives coincide, we show that in contrast to multi-dimensional mean-payoff games that are known to be coNP-complete, multi-dimensional total-payoff games are undecidable. We introduce conservative approximations of these objectives, where the payoff is considered over a local finite window sliding along a play, instead of the whole play. For single dimension, we show that (i) if the window size is polynomial, deciding the winner takes polynomial time, and (ii) the existence of a bounded window can be decided in NP ∩ coNP, and is at least as hard as solving mean-payoff games. For multiple dimensions, we show that (i) the problem with fixed window size is EXPTIME-complete, and (ii) there is no primitive-recursive algorithm to decide the existence of a bounded window.
AU - Chatterjee, Krishnendu
AU - Doyen, Laurent
AU - Randour, Mickael
AU - Raskin, Jean
ID - 523
IS - 6
JF - Information and Computation
TI - Looking at mean-payoff and total-payoff through windows
VL - 242
ER -
TY - JOUR
AB - We consider concurrent games played by two players on a finite-state graph, where in every round the players simultaneously choose a move, and the current state along with the joint moves determine the successor state. We study the most fundamental objective for concurrent games, namely, mean-payoff or limit-average objective, where a reward is associated to each transition, and the goal of player 1 is to maximize the long-run average of the rewards, and the objective of player 2 is strictly the opposite (i.e., the games are zero-sum). The path constraint for player 1 could be qualitative, i.e., the mean-payoff is the maximal reward, or arbitrarily close to it; or quantitative, i.e., a given threshold between the minimal and maximal reward. We consider the computation of the almost-sure (resp. positive) winning sets, where player 1 can ensure that the path constraint is satisfied with probability 1 (resp. positive probability). Almost-sure winning with qualitative constraint exactly corresponds to the question of whether there exists a strategy to ensure that the payoff is the maximal reward of the game. Our main results for qualitative path constraints are as follows: (1) we establish qualitative determinacy results that show that for every state either player 1 has a strategy to ensure almost-sure (resp. positive) winning against all player-2 strategies, or player 2 has a spoiling strategy to falsify almost-sure (resp. positive) winning against all player-1 strategies; (2) we present optimal strategy complexity results that precisely characterize the classes of strategies required for almost-sure and positive winning for both players; and (3) we present quadratic time algorithms to compute the almost-sure and the positive winning sets, matching the best known bound of the algorithms for much simpler problems (such as reachability objectives). For quantitative constraints we show that a polynomial time solution for the almost-sure or the positive winning set would imply a solution to a long-standing open problem (of solving the value problem of turn-based deterministic mean-payoff games) that is not known to be solvable in polynomial time.
AU - Chatterjee, Krishnendu
AU - Ibsen-Jensen, Rasmus
ID - 524
IS - 6
JF - Information and Computation
TI - Qualitative analysis of concurrent mean payoff games
VL - 242
ER -
TY - JOUR
AB - Ethylene is a gaseous phytohormone that plays vital roles in plant growth and development. Previous studies uncovered EIN2 as an essential signal transducer linking ethylene perception on ER to transcriptional regulation in the nucleus through a “cleave and shuttle” model. In this study, we report another mechanism of EIN2-mediated ethylene signaling, whereby EIN2 imposes the translational repression of EBF1 and EBF2 mRNA. We find that the EBF1/2 3′ UTRs mediate EIN2-directed translational repression and identify multiple poly-uridylates (PolyU) motifs as functional cis elements of 3′ UTRs. Furthermore, we demonstrate that ethylene induces EIN2 to associate with 3′ UTRs and target EBF1/2 mRNA to cytoplasmic processing-body (P-body) through interacting with multiple P-body factors, including EIN5 and PABs. Our study illustrates translational regulation as a key step in ethylene signaling and presents mRNA 3′ UTR functioning as a “signal transducer” to sense and relay cellular signaling in plants.
AU - Li, Wenyang
AU - Ma, Mengdi
AU - Feng, Ying
AU - Li, Hongjiang
AU - Wang, Yichuan
AU - Ma, Yutong
AU - Li, Mingzhe
AU - An, Fengying
AU - Guo, Hongwei
ID - 532
IS - 3
JF - Cell
TI - EIN2-directed translational regulation of ethylene signaling in arabidopsis
VL - 163
ER -
TY - GEN
AB - We consider Markov decision processes (MDPs) with multiple limit-average (or mean-payoff) objectives.
There have been two different views: (i) the expectation semantics, where the goal is to optimize the expected mean-payoff objective, and (ii) the satisfaction semantics, where the goal is to maximize the probability of runs such that the mean-payoff value stays above a given vector.
We consider the problem where the goal is to optimize the expectation under the constraint that the satisfaction semantics is ensured, and thus consider a generalization that unifies the existing semantics.
Our problem captures the notion of optimization with respect to strategies that are risk-averse (i.e., ensures certain probabilistic guarantee).
Our main results are algorithms for the decision problem which are always polynomial in the size of the MDP. We also show that an approximation of the Pareto-curve can be computed in time polynomial in the size of the MDP, and the approximation factor, but exponential in the number of dimensions.
Finally, we present a complete characterization of the strategy complexity (in terms of memory bounds and randomization) required to solve our problem.
AU - Chatterjee, Krishnendu
AU - Komarkova, Zuzana
AU - Kretinsky, Jan
ID - 5429
SN - 2664-1690
TI - Unifying two views on multiple mean-payoff objectives in Markov decision processes
ER -
TY - GEN
AB - We consider the core algorithmic problems related to verification of systems with respect to three classical quantitative properties, namely, the mean- payoff property, the ratio property, and the minimum initial credit for energy property. The algorithmic problem given a graph and a quantitative property asks to compute the optimal value (the infimum value over all traces) from every node of the graph. We consider graphs with constant treewidth, and it is well-known that the control-flow graphs of most programs have constant treewidth. Let n denote the number of nodes of a graph, m the number of edges (for constant treewidth graphs m = O ( n ) ) and W the largest absolute value of the weights. Our main theoretical results are as follows. First, for constant treewidth graphs we present an algorithm that approximates the mean-payoff value within a mul- tiplicative factor of ∊ in time O ( n · log( n/∊ )) and linear space, as compared to the classical algorithms that require quadratic time. Second, for the ratio property we present an algorithm that for constant treewidth graphs works in time O ( n · log( | a · b · n | )) = O ( n · log( n · W )) , when the output is a b , as compared to the previously best known algorithm with running time O ( n 2 · log( n · W )) . Third, for the minimum initial credit problem we show that (i) for general graphs the problem can be solved in O ( n 2 · m ) time and the associated decision problem can be solved in O ( n · m ) time, improving the previous known O ( n 3 · m · log( n · W )) and O ( n 2 · m ) bounds, respectively; and (ii) for constant treewidth graphs we present an algorithm that requires O ( n · log n ) time, improving the previous known O ( n 4 · log( n · W )) bound. We have implemented some of our algorithms and show that they present a significant speedup on standard benchmarks.
AU - Chatterjee, Krishnendu
AU - Ibsen-Jensen, Rasmus
AU - Pavlogiannis, Andreas
ID - 5430
SN - 2664-1690
TI - Faster algorithms for quantitative verification in constant treewidth graphs
ER -
TY - GEN
AB - We consider finite-state concurrent stochastic games, played by k>=2 players for an infinite number of rounds, where in every round, each player simultaneously and independently of the other players chooses an action, whereafter the successor state is determined by a probability distribution given by the current state and the chosen actions. We consider reachability objectives that given a target set of states require that some state in the target set is visited, and the dual safety objectives that given a target set require that only states in the target set are visited. We are interested in the complexity of stationary strategies measured by their patience, which is defined as the inverse of the smallest non-zero probability employed.
Our main results are as follows: We show that in two-player zero-sum concurrent stochastic games (with reachability objective for one player and the complementary safety objective for the other player): (i) the optimal bound on the patience of optimal and epsilon-optimal strategies, for both players is doubly exponential; and (ii) even in games with a single non-absorbing state exponential (in the number of actions) patience is necessary. In general we study the class of non-zero-sum games admitting epsilon-Nash equilibria. We show that if there is at least one player with reachability objective, then doubly-exponential patience is needed in general for epsilon-Nash equilibrium strategies, whereas in contrast if all players have safety objectives, then the optimal bound on patience for epsilon-Nash equilibrium strategies is only exponential.
AU - Chatterjee, Krishnendu
AU - Ibsen-Jensen, Rasmus
AU - Hansen, Kristoffer
ID - 5431
SN - 2664-1690
TI - The patience of concurrent stochastic games with safety and reachability objectives
ER -
TY - GEN
AB - Evolution occurs in populations of reproducing individuals. The structure of the population affects the outcome of the evolutionary process. Evolutionary graph theory is a powerful approach to study this phenomenon. There are two graphs. The interaction graph specifies who interacts with whom in the context of evolution.The replacement graph specifies who competes with whom for reproduction.
The vertices of the two graphs are the same, and each vertex corresponds to an individual of the population. A key quantity is the fixation probability of a new mutant. It is defined as the probability that a newly introduced mutant (on a single vertex) generates a lineage of offspring which eventually takes over the entire population of resident individuals. The basic computational questions are as follows: (i) the qualitative question asks whether the fixation probability is positive; and (ii) the quantitative approximation question asks for an approximation of the fixation probability.
Our main results are:
(1) We show that the qualitative question is NP-complete and the quantitative approximation question is #P-hard in the special case when the interaction and the replacement graphs coincide and even with the restriction that the resident individuals do not reproduce (which corresponds to an invading population taking over an empty structure).
(2) We show that in general the qualitative question is PSPACE-complete and the quantitative approximation question is PSPACE-hard and can be solved in exponential time.
AU - Chatterjee, Krishnendu
AU - Ibsen-Jensen, Rasmus
AU - Nowak, Martin
ID - 5432
SN - 2664-1690
TI - The complexity of evolutionary games on graphs
ER -
TY - GEN
AB - DEC-POMDPs extend POMDPs to a multi-agent setting, where several agents operate in an uncertain environment independently to achieve a joint objective. DEC-POMDPs have been studied with finite-horizon and infinite-horizon discounted-sum objectives, and there exist solvers both for exact and approximate solutions. In this work we consider Goal-DEC-POMDPs, where given a set of target states, the objective is to ensure that the target set is reached with minimal cost. We consider the indefinite-horizon (infinite-horizon with either discounted-sum, or undiscounted-sum, where absorbing goal states have zero-cost) problem. We present a new method to solve the problem that extends methods for finite-horizon DEC- POMDPs and the RTDP-Bel approach for POMDPs. We present experimental results on several examples, and show our approach presents promising results.
AU - Anonymous, 1
AU - Anonymous, 2
ID - 5434
SN - 2664-1690
TI - Optimal cost indefinite-horizon reachability in goal DEC-POMDPs
ER -
TY - GEN
AB - We consider Markov decision processes (MDPs) with multiple limit-average (or mean-payoff) objectives.
There have been two different views: (i) the expectation semantics, where the goal is to optimize the expected mean-payoff objective, and (ii) the satisfaction semantics, where the goal is to maximize the probability of runs such that the mean-payoff value stays above a given vector.
We consider the problem where the goal is to optimize the expectation under the constraint that the satisfaction semantics is ensured, and thus consider a generalization that unifies the existing semantics. Our problem captures the notion of optimization with respect to strategies that are risk-averse (i.e., ensures certain probabilistic guarantee).
Our main results are algorithms for the decision problem which are always polynomial in the size of the MDP.
We also show that an approximation of the Pareto-curve can be computed in time polynomial in the size of the MDP, and the approximation factor, but exponential in the number of dimensions. Finally, we present a complete characterization of the strategy complexity (in terms of memory bounds and randomization) required to solve our problem.
AU - Chatterjee, Krishnendu
AU - Komarkova, Zuzana
AU - Kretinsky, Jan
ID - 5435
SN - 2664-1690
TI - Unifying two views on multiple mean-payoff objectives in Markov decision processes
ER -
TY - GEN
AB - Recently there has been a significant effort to handle quantitative properties in formal verification and synthesis. While weighted automata over finite and infinite words provide a natural and flexible framework to express quantitative properties, perhaps surprisingly, some basic system properties such as average response time cannot be expressed using weighted automata, nor in any other know decidable formalism. In this work, we introduce nested weighted automata as a natural extension of weighted automata which makes it possible to express important quantitative properties such as average response time.
In nested weighted automata, a master automaton spins off and collects results from weighted slave automata, each of which computes a quantity along a finite portion of an infinite word. Nested weighted automata can be viewed as the quantitative analogue of monitor automata, which are used in run-time verification. We establish an almost complete decidability picture for the basic decision problems about nested weighted automata, and illustrate their applicability in several domains. In particular, nested weighted automata can be used to decide average response time properties.
AU - Chatterjee, Krishnendu
AU - Henzinger, Thomas A
AU - Otop, Jan
ID - 5436
SN - 2664-1690
TI - Nested weighted automata
ER -
TY - GEN
AB - We consider the core algorithmic problems related to verification of systems with respect to three classical quantitative properties, namely, the mean-payoff property, the ratio property, and the minimum initial credit for energy property.
The algorithmic problem given a graph and a quantitative property asks to compute the optimal value (the infimum value over all traces) from every node of the graph. We consider graphs with constant treewidth, and it is well-known that the control-flow graphs of most programs have constant treewidth. Let $n$ denote the number of nodes of a graph, $m$ the number of edges (for constant treewidth graphs $m=O(n)$) and $W$ the largest absolute value of the weights.
Our main theoretical results are as follows.
First, for constant treewidth graphs we present an algorithm that approximates the mean-payoff value within a multiplicative factor of $\epsilon$ in time $O(n \cdot \log (n/\epsilon))$ and linear space, as compared to the classical algorithms that require quadratic time. Second, for the ratio property we present an algorithm that for constant treewidth graphs works in time $O(n \cdot \log (|a\cdot b|))=O(n\cdot\log (n\cdot W))$, when the output is $\frac{a}{b}$, as compared to the previously best known algorithm with running time $O(n^2 \cdot \log (n\cdot W))$. Third, for the minimum initial credit problem we show that (i)~for general graphs the problem can be solved in $O(n^2\cdot m)$ time and the associated decision problem can be solved in $O(n\cdot m)$ time, improving the previous known $O(n^3\cdot m\cdot \log (n\cdot W))$ and $O(n^2 \cdot m)$ bounds, respectively; and (ii)~for constant treewidth graphs we present an algorithm that requires $O(n\cdot \log n)$ time, improving the previous known $O(n^4 \cdot \log (n \cdot W))$ bound.
We have implemented some of our algorithms and show that they present a significant speedup on standard benchmarks.
AU - Chatterjee, Krishnendu
AU - Ibsen-Jensen, Rasmus
AU - Pavlogiannis, Andreas
ID - 5437
SN - 2664-1690
TI - Faster algorithms for quantitative verification in constant treewidth graphs
ER -
TY - GEN
AB - The edit distance between two words w1, w2 is the minimal number of word operations (letter insertions, deletions, and substitutions) necessary to transform w1 to w2. The edit distance generalizes to languages L1, L2, where the edit distance is the minimal number k such that for every word from L1 there exists a word in L2 with edit distance at most k. We study the edit distance computation problem between pushdown automata and their subclasses.
The problem of computing edit distance to a pushdown automaton is undecidable, and in practice, the interesting question is to compute the edit distance from a pushdown automaton (the implementation, a standard model for programs with recursion) to a regular language (the specification). In this work, we present a complete picture of decidability and complexity for deciding whether, for a given threshold k, the edit distance from a pushdown automaton to a finite automaton is at most k.
AU - Chatterjee, Krishnendu
AU - Henzinger, Thomas A
AU - Ibsen-Jensen, Rasmus
AU - Otop, Jan
ID - 5438
SN - 2664-1690
TI - Edit distance for pushdown automata
ER -
TY - GEN
AB - The target discounted-sum problem is the following: Given a rational discount factor 0 < λ < 1 and three rational values a, b, and t, does there exist a finite or an infinite sequence w ε(a, b)∗ or w ε(a, b)w, such that Σ|w| i=0 w(i)λi equals t? The problem turns out to relate to many fields of mathematics and computer science, and its decidability question is surprisingly hard to solve. We solve the finite version of the problem, and show the hardness of the infinite version, linking it to various areas and open problems in mathematics and computer science: β-expansions, discounted-sum automata, piecewise affine maps, and generalizations of the Cantor set. We provide some partial results to the infinite version, among which are solutions to its restriction to eventually-periodic sequences and to the cases that λ λ 1/2 or λ = 1/n, for every n ε N. We use our results for solving some open problems on discounted-sum automata, among which are the exact-value problem for nondeterministic automata over finite words and the universality and inclusion problems for functional automata.
AU - Boker, Udi
AU - Henzinger, Thomas A
AU - Otop, Jan
ID - 5439
SN - 2664-1690
TI - The target discounted-sum problem
ER -
TY - GEN
AB - Evolution occurs in populations of reproducing individuals. The structure of the population affects the outcome of the evolutionary process. Evolutionary graph theory is a powerful approach to study this phenomenon. There are two graphs. The interaction graph specifies who interacts with whom for payoff in the context of evolution. The replacement graph specifies who competes with whom for reproduction. The vertices of the two graphs are the same, and each vertex corresponds to an individual of the population. The fitness (or the reproductive rate) is a non-negative number, and depends on the payoff. A key quantity is the fixation probability of a new mutant. It is defined as the probability that a newly introduced mutant (on a single vertex) generates a lineage of offspring which eventually takes over the entire population of resident individuals. The basic computational questions are as follows: (i) the qualitative question asks whether the fixation probability is positive; and (ii) the quantitative approximation question asks for an approximation of the fixation probability. Our main results are as follows: First, we consider a special case of the general problem, where the residents do not reproduce. We show that the qualitative question is NP-complete, and the quantitative approximation question is #P-complete, and the hardness results hold even in the special case where the interaction and the replacement graphs coincide. Second, we show that in general both the qualitative and the quantitative approximation questions are PSPACE-complete. The PSPACE-hardness result for quantitative approximation holds even when the fitness is always positive.
AU - Chatterjee, Krishnendu
AU - Ibsen-Jensen, Rasmus
AU - Nowak, Martin
ID - 5440
SN - 2664-1690
TI - The complexity of evolutionary games on graphs
ER -
TY - GEN
AB - We study algorithmic questions for concurrent systems where the transitions are labeled from a complete, closed semiring, and path properties are algebraic with semiring operations. The algebraic path properties can model dataflow analysis problems, the shortest path problem, and many other natural problems that arise in program analysis. We consider that each component of the concurrent system is a graph with constant treewidth, a property satisfied by the controlflow graphs of most programs. We allow for multiple possible queries, which arise naturally in demand driven dataflow analysis. The study of multiple queries allows us to consider the tradeoff between the resource usage of the one-time preprocessing and for each individual query. The traditional approach constructs the product graph of all components and applies the best-known graph algorithm on the product. In this approach, even the answer to a single query requires the transitive closure (i.e., the results of all possible queries), which provides no room for tradeoff between preprocessing and query time. Our main contributions are algorithms that significantly improve the worst-case running time of the traditional approach, and provide various tradeoffs depending on the number of queries. For example, in a concurrent system of two components, the traditional approach requires hexic time in the worst case for answering one query as well as computing the transitive closure, whereas we show that with one-time preprocessing in almost cubic time, each subsequent query can be answered in at most linear time, and even the transitive closure can be computed in almost quartic time. Furthermore, we establish conditional optimality results showing that the worst-case running time of our algorithms cannot be improved without achieving major breakthroughs in graph algorithms (i.e., improving the worst-case bound for the shortest path problem in general graphs). Preliminary experimental results show that our algorithms perform favorably on several benchmarks.
AU - Chatterjee, Krishnendu
AU - Ibsen-Jensen, Rasmus
AU - Goharshady, Amir
AU - Pavlogiannis, Andreas
ID - 5441
SN - 2664-1690
TI - Algorithms for algebraic path properties in concurrent systems of constant treewidth components
ER -
TY - GEN
AB - We study algorithmic questions for concurrent systems where the transitions are labeled from a complete, closed semiring, and path properties are algebraic with semiring operations. The algebraic path properties can model dataflow analysis problems, the shortest path problem, and many other natural properties that arise in program analysis.
We consider that each component of the concurrent system is a graph with constant treewidth, and it is known that the controlflow graphs of most programs have constant treewidth. We allow for multiple possible queries, which arise naturally in demand driven dataflow analysis problems (e.g., alias analysis). The study of multiple queries allows us to consider the tradeoff between the resource usage of the \emph{one-time} preprocessing and for \emph{each individual} query. The traditional approaches construct the product graph of all components and apply the best-known graph algorithm on the product. In the traditional approach, even the answer to a single query requires the transitive closure computation (i.e., the results of all possible queries), which provides no room for tradeoff between preprocessing and query time.
Our main contributions are algorithms that significantly improve the worst-case running time of the traditional approach, and provide various tradeoffs depending on the number of queries. For example, in a concurrent system of two components, the traditional approach requires hexic time in the worst case for answering one query as well as computing the transitive closure, whereas we show that with one-time preprocessing in almost cubic time,
each subsequent query can be answered in at most linear time, and even the transitive closure can be computed in almost quartic time. Furthermore, we establish conditional optimality results that show that the worst-case running times of our algorithms cannot be improved without achieving major breakthroughs in graph algorithms (such as improving
the worst-case bounds for the shortest path problem in general graphs whose current best-known bound has not been improved in five decades). Finally, we provide a prototype implementation of our algorithms which significantly outperforms the existing algorithmic methods on several benchmarks.
AU - Anonymous, 1
AU - Anonymous, 2
AU - Anonymous, 3
AU - Anonymous, 4
ID - 5442
SN - 2664-1690
TI - Algorithms for algebraic path properties in concurrent systems of constant treewidth components
ER -
TY - GEN
AB - POMDPs are standard models for probabilistic planning problems, where an agent interacts with an uncertain environment. We study the problem of almost-sure reachability, where given a set of target states, the question is to decide whether there is a policy to ensure that the target set is reached with probability 1 (almost-surely). While in general the problem is EXPTIME-complete, in many practical cases policies with a small amount of memory suffice. Moreover, the existing solution to the problem is explicit, which first requires to construct explicitly an exponential reduction to a belief-support MDP. In this work, we first study the existence of observation-stationary strategies, which is NP-complete, and then small-memory strategies. We present a symbolic algorithm by an efficient encoding to SAT and using a SAT solver for the problem. We report experimental results demonstrating the scalability of our symbolic (SAT-based) approach.
AU - Chatterjee, Krishnendu
AU - Chmelik, Martin
AU - Davies, Jessica
ID - 5443
SN - 2664-1690
TI - A symbolic SAT-based algorithm for almost-sure reachability with small strategies in POMDPs
ER -
TY - GEN
AB - A comprehensive understanding of the clonal evolution of cancer is critical for understanding neoplasia. Genome-wide sequencing data enables evolutionary studies at unprecedented depth. However, classical phylogenetic methods often struggle with noisy sequencing data of impure DNA samples and fail to detect subclones that have different evolutionary trajectories. We have developed a tool, called Treeomics, that allows us to reconstruct the phylogeny of a cancer with commonly available sequencing technologies. Using Bayesian inference and Integer Linear Programming, robust phylogenies consistent with the biological processes underlying cancer evolution were obtained for pancreatic, ovarian, and prostate cancers. Furthermore, Treeomics correctly identified sequencing artifacts such as those resulting from low statistical power; nearly 7% of variants were misclassified by conventional statistical methods. These artifacts can skew phylogenies by creating illusory tumor heterogeneity among distinct samples. Importantly, we show that the evolutionary trees generated with Treeomics are mathematically optimal.
AU - Reiter, Johannes
AU - Makohon-Moore, Alvin
AU - Gerold, Jeffrey
AU - Bozic, Ivana
AU - Chatterjee, Krishnendu
AU - Iacobuzio-Donahue, Christine
AU - Vogelstein, Bert
AU - Nowak, Martin
ID - 5444
SN - 2664-1690
TI - Reconstructing robust phylogenies of metastatic cancers
ER -
TY - DATA
AB - This repository contains the experimental part of the CAV 2015 publication Counterexample Explanation by Learning Small Strategies in Markov Decision Processes.
We extended the probabilistic model checker PRISM to represent strategies of Markov Decision Processes as Decision Trees.
The archive contains a java executable version of the extended tool (prism_dectree.jar) together with a few examples of the PRISM benchmark library.
To execute the program, please have a look at the README.txt, which provides instructions and further information on the archive.
The archive contains scripts that (if run often enough) reproduces the data presented in the publication.
AU - Fellner, Andreas
ID - 5549
KW - Markov Decision Process
KW - Decision Tree
KW - Probabilistic Verification
KW - Counterexample Explanation
TI - Experimental part of CAV 2015 publication: Counterexample Explanation by Learning Small Strategies in Markov Decision Processes
ER -
TY - JOUR
AB - Parasitism creates selection for resistance mechanisms in host populations and is hypothesized to promote increased host evolvability. However, the influence of these traits on host evolution when parasites are no longer present is unclear. We used experimental evolution and whole-genome sequencing of Escherichia coli to determine the effects of past and present exposure to parasitic viruses (phages) on the spread of mutator alleles, resistance, and bacterial competitive fitness. We found that mutator alleles spread rapidly during adaptation to any of four different phage species, and this pattern was even more pronounced with multiple phages present simultaneously. However, hypermutability did not detectably accelerate adaptation in the absence of phages and recovery of fitness costs associated with resistance. Several lineages evolved phage resistance through elevated mucoidy, and during subsequent evolution in phage-free conditions they rapidly reverted to nonmucoid, phage-susceptible phenotypes. Genome sequencing revealed that this phenotypic reversion was achieved by additional genetic changes rather than by genotypic reversion of the initial resistance mutations. Insertion sequence (IS) elements played a key role in both the acquisition of resistance and adaptation in the absence of parasites; unlike single nucleotide polymorphisms, IS insertions were not more frequent in mutator lineages. Our results provide a genetic explanation for rapid reversion of mucoidy, a phenotype observed in other bacterial species including human pathogens. Moreover, this demonstrates that the types of genetic change underlying adaptation to fitness costs, and consequently the impact of evolvability mechanisms such as increased point-mutation rates, depend critically on the mechanism of resistance.
AU - Wielgoss, Sébastien
AU - Bergmiller, Tobias
AU - Bischofberger, Anna M.
AU - Hall, Alex R.
ID - 5749
IS - 3
JF - Molecular Biology and Evolution
SN - 0737-4038
TI - Adaptation to Parasites and Costs of Parasite Resistance in Mutator and Nonmutator Bacteria
VL - 33
ER -
TY - JOUR
AB - In plants, vacuolar H+-ATPase (V-ATPase) activity acidifies both the trans-Golgi network/early endosome (TGN/EE) and the vacuole. This dual V-ATPase function has impeded our understanding of how the pH homeostasis within the plant TGN/EE controls exo- and endocytosis. Here, we show that the weak V-ATPase mutant deetiolated3 (det3) displayed a pH increase in the TGN/EE, but not in the vacuole, strongly impairing secretion and recycling of the brassinosteroid receptor and the cellulose synthase complexes to the plasma membrane, in contrast to mutants lacking tonoplast-localized V-ATPase activity only. The brassinosteroid insensitivity and the cellulose deficiency defects in det3 were tightly correlated with reduced Golgi and TGN/EE motility. Thus, our results provide strong evidence that acidification of the TGN/EE, but not of the vacuole, is indispensable for functional secretion and recycling in plants.
AU - Yu, Luo
AU - Scholl, Stefan
AU - Doering, Anett
AU - Yi, Zhang
AU - Irani, Niloufer
AU - Di Rubbo, Simone
AU - Neumetzler, Lutz
AU - Krishnamoorthy, Praveen
AU - Van Houtte, Isabelle
AU - Mylle, Evelien
AU - Bischoff, Volker
AU - Vernhettes, Samantha
AU - Winne, Johan
AU - Friml, Jirí
AU - Stierhof, York
AU - Schumacher, Karin
AU - Persson, Staffan
AU - Russinova, Eugenia
ID - 1383
IS - 7
JF - Nature Plants
TI - V-ATPase activity in the TGN/EE is required for exocytosis and recycling in Arabidopsis
VL - 1
ER -
TY - THES
AB - This thesis is concerned with the computation and approximation of intrinsic volumes. Given a smooth body M and a certain digital approximation of it, we develop algorithms to approximate various intrinsic volumes of M using only measurements taken from its digital approximations. The crucial idea behind our novel algorithms is to link the recent theory of persistent homology to the theory of intrinsic volumes via the Crofton formula from integral geometry and, in particular, via Euler characteristic computations. Our main contributions are a multigrid convergent digital algorithm to compute the first intrinsic volume of a solid body in R^n as well as an appropriate integration pipeline to approximate integral-geometric integrals defined over the Grassmannian manifold.
AU - Pausinger, Florian
ID - 1399
TI - On the approximation of intrinsic volumes
ER -
TY - THES
AB - Cancer results from an uncontrolled growth of abnormal cells. Sequentially accumulated genetic and epigenetic alterations decrease cell death and increase cell replication. We used mathematical models to quantify the effect of driver gene mutations. The recently developed targeted therapies can lead to dramatic regressions. However, in solid cancers, clinical responses are often short-lived because resistant cancer cells evolve. We estimated that approximately 50 different mutations can confer resistance to a typical targeted therapeutic agent. We find that resistant cells are likely to be present in expanded subclones before the start of the treatment. The dominant strategy to prevent the evolution of resistance is combination therapy. Our analytical results suggest that in most patients, dual therapy, but not monotherapy, can result in long-term disease control. However, long-term control can only occur if there are no possible mutations in the genome that can cause cross-resistance to both drugs. Furthermore, we showed that simultaneous therapy with two drugs is much more likely to result in long-term disease control than sequential therapy with the same drugs. To improve our understanding of the underlying subclonal evolution we reconstruct the evolutionary history of a patient's cancer from next-generation sequencing data of spatially-distinct DNA samples. Using a quantitative measure of genetic relatedness, we found that pancreatic cancers and their metastases demonstrated a higher level of relatedness than that expected for any two cells randomly taken from a normal tissue. This minimal amount of genetic divergence among advanced lesions indicates that genetic heterogeneity, when quantitatively defined, is not a fundamental feature of the natural history of untreated pancreatic cancers. Our newly developed, phylogenomic tool Treeomics finds evidence for seeding patterns of metastases and can directly be used to discover rules governing the evolution of solid malignancies to transform cancer into a more predictable disease.
AU - Reiter, Johannes
ID - 1400
TI - The subclonal evolution of cancer
ER -
TY - CONF
AB - We consider the problem of statistical computations with persistence diagrams, a summary representation of topological features in data. These diagrams encode persistent homology, a widely used invariant in topological data analysis. While several avenues towards a statistical treatment of the diagrams have been explored recently, we follow an alternative route that is motivated by the success of methods based on the embedding of probability measures into reproducing kernel Hilbert spaces. In fact, a positive definite kernel on persistence diagrams has recently been proposed, connecting persistent homology to popular kernel-based learning techniques such as support vector machines. However, important properties of that kernel enabling a principled use in the context of probability measure embeddings remain to be explored. Our contribution is to close this gap by proving universality of a variant of the original kernel, and to demonstrate its effective use in twosample hypothesis testing on synthetic as well as real-world data.
AU - Kwitt, Roland
AU - Huber, Stefan
AU - Niethammer, Marc
AU - Lin, Weili
AU - Bauer, Ulrich
ID - 1424
TI - Statistical topological data analysis-A kernel perspective
VL - 28
ER -
TY - CONF
AB - In this work we aim at extending the theoretical foundations of lifelong learning. Previous work analyzing this scenario is based on the assumption that learning tasks are sampled i.i.d. from a task environment or limited to strongly constrained data distributions. Instead, we study two scenarios when lifelong learning is possible, even though the observed tasks do not form an i.i.d. sample: first, when they are sampled from the same environment, but possibly with dependencies, and second, when the task environment is allowed to change over time in a consistent way. In the first case we prove a PAC-Bayesian theorem that can be seen as a direct generalization of the analogous previous result for the i.i.d. case. For the second scenario we propose to learn an inductive bias in form of a transfer procedure. We present a generalization bound and show on a toy example how it can be used to identify a beneficial transfer algorithm.
AU - Pentina, Anastasia
AU - Lampert, Christoph
ID - 1425
TI - Lifelong learning with non-i.i.d. tasks
VL - 2015
ER -
TY - CONF
AB - Evolutionary algorithms (EAs) form a popular optimisation paradigm inspired by natural evolution. In recent years the field of evolutionary computation has developed a rigorous analytical theory to analyse their runtime on many illustrative problems. Here we apply this theory to a simple model of natural evolution. In the Strong Selection Weak Mutation (SSWM) evolutionary regime the time between occurrence of new mutations is much longer than the time it takes for a new beneficial mutation to take over the population. In this situation, the population only contains copies of one genotype and evolution can be modelled as a (1+1)-type process where the probability of accepting a new genotype (improvements or worsenings) depends on the change in fitness. We present an initial runtime analysis of SSWM, quantifying its performance for various parameters and investigating differences to the (1+1) EA. We show that SSWM can have a moderate advantage over the (1+1) EA at crossing fitness valleys and study an example where SSWM outperforms the (1+1) EA by taking advantage of information on the fitness gradient.
AU - Paixao, Tiago
AU - Sudholt, Dirk
AU - Heredia, Jorge
AU - Trubenova, Barbora
ID - 1430
T2 - Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation
TI - First steps towards a runtime comparison of natural and artificial evolution
ER -
TY - CONF
AB - Cryptographic access control offers selective access to encrypted data via a combination of key management and functionality-rich cryptographic schemes, such as attribute-based encryption. Using this approach, publicly available meta-data may inadvertently leak information on the access policy that is enforced by cryptography, which renders cryptographic access control unusable in settings where this information is highly sensitive. We begin to address this problem by presenting rigorous definitions for policy privacy in cryptographic access control. For concreteness we set our results in the model of Role-Based Access Control (RBAC), where we identify and formalize several different flavors of privacy, however, our framework should serve as inspiration for other models of access control. Based on our insights we propose a new system which significantly improves on the privacy properties of state-of-the-art constructions. Our design is based on a novel type of privacy-preserving attribute-based encryption, which we introduce and show how to instantiate. We present our results in the context of a cryptographic RBAC system by Ferrara et al. (CSF'13), which uses cryptography to control read access to files, while write access is still delegated to trusted monitors. We give an extension of the construction that permits cryptographic control over write access. Our construction assumes that key management uses out-of-band channels between the policy enforcer and the users but eliminates completely the need for monitoring read/write access to the data.
AU - Ferrara, Anna
AU - Fuchsbauer, Georg
AU - Liu, Bin
AU - Warinschi, Bogdan
ID - 1474
TI - Policy privacy in cryptographic access control
ER -
TY - CONF
AB - Simple board games, like Tic-Tac-Toe and CONNECT-4, play an important role not only in the development of mathematical and logical skills, but also in the emotional and social development. In this paper, we address the problem of generating targeted starting positions for such games. This can facilitate new approaches for bringing novice players to mastery, and also leads to discovery of interesting game variants. We present an approach that generates starting states of varying hardness levels for player 1 in a two-player board game, given rules of the board game, the desired number of steps required for player 1 to win, and the expertise levels of the two players. Our approach leverages symbolic methods and iterative simulation to efficiently search the extremely large state space. We present experimental results that include discovery of states of varying hardness levels for several simple grid-based board games. The presence of such states for standard game variants like 4×4 Tic-Tac-Toe opens up new games to be played that have never been played as the default start state is heavily biased.
AU - Ahmed, Umair
AU - Chatterjee, Krishnendu
AU - Gulwani, Sumit
ID - 1481
T2 - Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence
TI - Automatic generation of alternative starting positions for simple traditional board games
VL - 2
ER -
TY - CONF
AB - Topological data analysis offers a rich source of valuable information to study vision problems. Yet, so far we lack a theoretically sound connection to popular kernel-based learning techniques, such as kernel SVMs or kernel PCA. In this work, we establish such a connection by designing a multi-scale kernel for persistence diagrams, a stable summary representation of topological features in data. We show that this kernel is positive definite and prove its stability with respect to the 1-Wasserstein distance. Experiments on two benchmark datasets for 3D shape classification/retrieval and texture recognition show considerable performance gains of the proposed method compared to an alternative approach that is based on the recently introduced persistence landscapes.
AU - Reininghaus, Jan
AU - Huber, Stefan
AU - Bauer, Ulrich
AU - Kwitt, Roland
ID - 1483
TI - A stable multi-scale kernel for topological machine learning
ER -
TY - CONF
AB - Motivated by biological questions, we study configurations of equal-sized disks in the Euclidean plane that neither pack nor cover. Measuring the quality by the probability that a random point lies in exactly one disk, we show that the regular hexagonal grid gives the maximum among lattice configurations.
AU - Edelsbrunner, Herbert
AU - Iglesias Ham, Mabel
AU - Kurlin, Vitaliy
ID - 1495
T2 - Proceedings of the 27th Canadian Conference on Computational Geometry
TI - Relaxed disk packing
VL - 2015-August
ER -
TY - JOUR
AB - Detecting allelic biases from high-throughput sequencing data requires an approach that maximises sensitivity while minimizing false positives. Here, we present Allelome.PRO, an automated user-friendly bioinformatics pipeline, which uses high-throughput sequencing data from reciprocal crosses of two genetically distinct mouse strains to detect allele-specific expression and chromatin modifications. Allelome.PRO extends approaches used in previous studies that exclusively analyzed imprinted expression to give a complete picture of the ‘allelome’ by automatically categorising the allelic expression of all genes in a given cell type into imprinted, strain-biased, biallelic or non-informative. Allelome.PRO offers increased sensitivity to analyze lowly expressed transcripts, together with a robust false discovery rate empirically calculated from variation in the sequencing data. We used RNA-seq data from mouse embryonic fibroblasts from F1 reciprocal crosses to determine a biologically relevant allelic ratio cutoff, and define for the first time an entire allelome. Furthermore, we show that Allelome.PRO detects differential enrichment of H3K4me3 over promoters from ChIP-seq data validating the RNA-seq results. This approach can be easily extended to analyze histone marks of active enhancers, or transcription factor binding sites and therefore provides a powerful tool to identify candidate cis regulatory elements genome wide.
AU - Andergassen, Daniel
AU - Dotter, Christoph
AU - Kulinski, Tomasz
AU - Guenzl, Philipp
AU - Bammer, Philipp
AU - Barlow, Denise
AU - Pauler, Florian
AU - Hudson, Quanah
ID - 1497
IS - 21
JF - Nucleic Acids Research
TI - Allelome.PRO, a pipeline to define allele-specific genomic features from high-throughput sequencing data
VL - 43
ER -
TY - CONF
AB - Fault-tolerant distributed algorithms play an important role in many critical/high-availability applications. These algorithms are notoriously difficult to implement correctly, due to asynchronous communication and the occurrence of faults, such as the network dropping messages or computers crashing. Nonetheless there is surprisingly little language and verification support to build distributed systems based on fault-tolerant algorithms. In this paper, we present some of the challenges that a designer has to overcome to implement a fault-tolerant distributed system. Then we review different models that have been proposed to reason about distributed algorithms and sketch how such a model can form the basis for a domain-specific programming language. Adopting a high-level programming model can simplify the programmer's life and make the code amenable to automated verification, while still compiling to efficiently executable code. We conclude by summarizing the current status of an ongoing language design and implementation project that is based on this idea.
AU - Dragoi, Cezara
AU - Henzinger, Thomas A
AU - Zufferey, Damien
ID - 1498
SN - 978-3-939897-80-4
TI - The need for language support for fault-tolerant distributed systems
VL - 32
ER -
TY - CONF
AB - We consider weighted automata with both positive and negative integer weights on edges and
study the problem of synchronization using adaptive strategies that may only observe whether
the current weight-level is negative or nonnegative. We show that the synchronization problem is decidable in polynomial time for deterministic weighted automata.
AU - Kretinsky, Jan
AU - Larsen, Kim
AU - Laursen, Simon
AU - Srba, Jiří
ID - 1499
TI - Polynomial time decidability of weighted synchronization under partial observability
VL - 42
ER -
TY - JOUR
AB - We consider Markov decision processes (MDPs) which are a standard model for probabilistic systems. We focus on qualitative properties for MDPs that can express that desired behaviors of the system arise almost-surely (with probability 1) or with positive probability. We introduce a new simulation relation to capture the refinement relation of MDPs with respect to qualitative properties, and present discrete graph algorithms with quadratic complexity to compute the simulation relation. We present an automated technique for assume-guarantee style reasoning for compositional analysis of two-player games by giving a counterexample guided abstraction-refinement approach to compute our new simulation relation. We show a tight link between two-player games and MDPs, and as a consequence the results for games are lifted to MDPs with qualitative properties. We have implemented our algorithms and show that the compositional analysis leads to significant improvements.
AU - Chatterjee, Krishnendu
AU - Chmelik, Martin
AU - Daca, Przemyslaw
ID - 1501
IS - 2
JF - Formal Methods in System Design
TI - CEGAR for compositional analysis of qualitative properties in Markov decision processes
VL - 47
ER -
TY - CONF
AB - We extend the theory of input-output conformance with operators for merge and quotient. The former is useful when testing against multiple requirements or views. The latter can be used to generate tests for patches of an already tested system. Both operators can combine systems with different action alphabets, which is usually the case when constructing complex systems and specifications from parts, for instance different views as well as newly defined functionality of a~previous version of the system.
AU - Beneš, Nikola
AU - Daca, Przemyslaw
AU - Henzinger, Thomas A
AU - Kretinsky, Jan
AU - Nickovic, Dejan
ID - 1502
SN - 978-1-4503-3471-6
TI - Complete composition operators for IOCO-testing theory
ER -
TY - JOUR
AB - This paper is aimed at deriving the universality of the largest eigenvalue of a class of high-dimensional real or complex sample covariance matrices of the form W N =Σ 1/2XX∗Σ 1/2 . Here, X = (xij )M,N is an M× N random matrix with independent entries xij , 1 ≤ i M,≤ 1 ≤ j ≤ N such that Exij = 0, E|xij |2 = 1/N . On dimensionality, we assume that M = M(N) and N/M → d ε (0, ∞) as N ∞→. For a class of general deterministic positive-definite M × M matrices Σ , under some additional assumptions on the distribution of xij 's, we show that the limiting behavior of the largest eigenvalue of W N is universal, via pursuing a Green function comparison strategy raised in [Probab. Theory Related Fields 154 (2012) 341-407, Adv. Math. 229 (2012) 1435-1515] by Erd″os, Yau and Yin for Wigner matrices and extended by Pillai and Yin [Ann. Appl. Probab. 24 (2014) 935-1001] to sample covariance matrices in the null case (&Epsi = I ). Consequently, in the standard complex case (Ex2 ij = 0), combing this universality property and the results known for Gaussian matrices obtained by El Karoui in [Ann. Probab. 35 (2007) 663-714] (nonsingular case) and Onatski in [Ann. Appl. Probab. 18 (2008) 470-490] (singular case), we show that after an appropriate normalization the largest eigenvalue of W N converges weakly to the type 2 Tracy-Widom distribution TW2 . Moreover, in the real case, we show that whenΣ is spiked with a fixed number of subcritical spikes, the type 1 Tracy-Widom limit TW1 holds for the normalized largest eigenvalue of W N , which extends a result of Féral and Péché in [J. Math. Phys. 50 (2009) 073302] to the scenario of nondiagonal Σ and more generally distributed X . In summary, we establish the Tracy-Widom type universality for the largest eigenvalue of generally distributed sample covariance matrices under quite light assumptions on &Sigma . Applications of these limiting results to statistical signal detection and structure recognition of separable covariance matrices are also discussed.
AU - Bao, Zhigang
AU - Pan, Guangming
AU - Zhou, Wang
ID - 1505
IS - 1
JF - Annals of Statistics
TI - Universality for the largest eigenvalue of sample covariance matrices with general population
VL - 43
ER -
TY - JOUR
AB - Consider the square random matrix An = (aij)n,n, where {aij:= a(n)ij , i, j = 1, . . . , n} is a collection of independent real random variables with means zero and variances one. Under the additional moment condition supn max1≤i,j ≤n Ea4ij <∞, we prove Girko's logarithmic law of det An in the sense that as n→∞ log | detAn| ? (1/2) log(n-1)! d/→√(1/2) log n N(0, 1).
AU - Bao, Zhigang
AU - Pan, Guangming
AU - Zhou, Wang
ID - 1506
IS - 3
JF - Bernoulli
TI - The logarithmic law of random determinant
VL - 21
ER -
TY - JOUR
AB - We consider generalized Wigner ensembles and general β-ensembles with analytic potentials for any β ≥ 1. The recent universality results in particular assert that the local averages of consecutive eigenvalue gaps in the bulk of the spectrum are universal in the sense that they coincide with those of the corresponding Gaussian β-ensembles. In this article, we show that local averaging is not necessary for this result, i.e. we prove that the single gap distributions in the bulk are universal. In fact, with an additional step, our result can be extended to any C4(ℝ) potential.
AU - Erdös, László
AU - Yau, Horng
ID - 1508
IS - 8
JF - Journal of the European Mathematical Society
TI - Gap universality of generalized Wigner and β ensembles
VL - 17
ER -
TY - JOUR
AB - The Auxin Binding Protein1 (ABP1) has been identified based on its ability to bind auxin with high affinity and studied for a long time as a prime candidate for the extracellular auxin receptor responsible for mediating in particular the fast non-transcriptional auxin responses. However, the contradiction between the embryo-lethal phenotypes of the originally described Arabidopsis T-DNA insertional knock-out alleles (abp1-1 and abp1-1s) and the wild type-like phenotypes of other recently described loss-of-function alleles (abp1-c1 and abp1-TD1) questions the biological importance of ABP1 and relevance of the previous genetic studies. Here we show that there is no hidden copy of the ABP1 gene in the Arabidopsis genome but the embryo-lethal phenotypes of abp1-1 and abp1-1s alleles are very similar to the knock-out phenotypes of the neighboring gene, BELAYA SMERT (BSM). Furthermore, the allelic complementation test between bsm and abp1 alleles shows that the embryo-lethality in the abp1-1 and abp1-1s alleles is caused by the off-target disruption of the BSM locus by the T-DNA insertions. This clarifies the controversy of different phenotypes among published abp1 knock-out alleles and asks for reflections on the developmental role of ABP1.
AU - Michalko, Jaroslav
AU - Dravecka, Marta
AU - Bollenbach, Tobias
AU - Friml, Jirí
ID - 1509
JF - F1000 Research
TI - Embryo-lethal phenotypes in early abp1 mutants are due to disruption of the neighboring BSM gene
VL - 4
ER -
TY - CONF
AB - The concept of well group in a special but important case captures homological properties of the zero set of a continuous map f from K to R^n on a compact space K that are invariant with respect to perturbations of f. The perturbations are arbitrary continuous maps within L_infty distance r from f for a given r > 0. The main drawback of the approach is that the computability of well groups was shown only when dim K = n or n = 1. Our contribution to the theory of well groups is twofold: on the one hand we improve on the computability issue, but on the other hand we present a range of examples where the well groups are incomplete invariants, that is, fail to capture certain important robust properties of the zero set. For the first part, we identify a computable subgroup of the well group that is obtained by cap product with the pullback of the orientation of R^n by f. In other words, well groups can be algorithmically approximated from below. When f is smooth and dim K < 2n-2, our approximation of the (dim K-n)th well group is exact. For the second part, we find examples of maps f, f' from K to R^n with all well groups isomorphic but whose perturbations have different zero sets. We discuss on a possible replacement of the well groups of vector valued maps by an invariant of a better descriptive power and computability status.
AU - Franek, Peter
AU - Krcál, Marek
ID - 1510
TI - On computability and triviality of well groups
VL - 34
ER -
TY - CONF
AB - The fact that the complete graph K_5 does not embed in the plane has been generalized in two independent directions. On the one hand, the solution of the classical Heawood problem for graphs on surfaces established that the complete graph K_n embeds in a closed surface M if and only if (n-3)(n-4) is at most 6b_1(M), where b_1(M) is the first Z_2-Betti number of M. On the other hand, Van Kampen and Flores proved that the k-skeleton of the n-dimensional simplex (the higher-dimensional analogue of K_{n+1}) embeds in R^{2k} if and only if n is less or equal to 2k+2. Two decades ago, Kuhnel conjectured that the k-skeleton of the n-simplex embeds in a compact, (k-1)-connected 2k-manifold with kth Z_2-Betti number b_k only if the following generalized Heawood inequality holds: binom{n-k-1}{k+1} is at most binom{2k+1}{k+1} b_k. This is a common generalization of the case of graphs on surfaces as well as the Van Kampen--Flores theorem. In the spirit of Kuhnel's conjecture, we prove that if the k-skeleton of the n-simplex embeds in a 2k-manifold with kth Z_2-Betti number b_k, then n is at most 2b_k binom{2k+2}{k} + 2k + 5. This bound is weaker than the generalized Heawood inequality, but does not require the assumption that M is (k-1)-connected. Our proof uses a result of Volovikov about maps that satisfy a certain homological triviality condition.
AU - Goaoc, Xavier
AU - Mabillard, Isaac
AU - Paták, Pavel
AU - Patakova, Zuzana
AU - Tancer, Martin
AU - Wagner, Uli
ID - 1511
TI - On generalized Heawood inequalities for manifolds: A Van Kampen–Flores-type nonembeddability result
VL - 34
ER -
TY - CONF
AB - We show that very weak topological assumptions are enough to ensure the existence of a Helly-type theorem. More precisely, we show that for any non-negative integers b and d there exists an integer h(b,d) such that the following holds. If F is a finite family of subsets of R^d such that the ith reduced Betti number (with Z_2 coefficients in singular homology) of the intersection of any proper subfamily G of F is at most b for every non-negative integer i less or equal to (d-1)/2, then F has Helly number at most h(b,d). These topological conditions are sharp: not controlling any of these first Betti numbers allow for families with unbounded Helly number. Our proofs combine homological non-embeddability results with a Ramsey-based approach to build, given an arbitrary simplicial complex K, some well-behaved chain map from C_*(K) to C_*(R^d). Both techniques are of independent interest.
AU - Goaoc, Xavier
AU - Paták, Pavel
AU - Patakova, Zuzana
AU - Tancer, Martin
AU - Wagner, Uli
ID - 1512
TI - Bounding Helly numbers via Betti numbers
VL - 34
ER -
TY - JOUR
AB - Insects of the order Hemiptera (true bugs) use a wide range of mechanisms of sex determination, including genetic sex determination, paternal genome elimination, and haplodiploidy. Genetic sex determination, the prevalent mode, is generally controlled by a pair of XY sex chromosomes or by an XX/X0 system, but different configurations that include additional sex chromosomes are also present. Although this diversity of sex determining systems has been extensively studied at the cytogenetic level, only the X chromosome of the model pea aphid Acyrthosiphon pisum has been analyzed at the genomic level, and little is known about X chromosome biology in the rest of the order.
In this study, we take advantage of published DNA- and RNA-seq data from three additional Hemiptera species to perform a comparative analysis of the gene content and expression of the X chromosome throughout this clade. We find that, despite showing evidence of dosage compensation, the X chromosomes of these species show female-biased expression, and a deficit of male-biased genes, in direct contrast to the pea aphid X. We further detect an excess of shared gene content between these very distant species, suggesting that despite the diversity of sex determining systems, the same chromosomal element is used as the X throughout a large portion of the order.
AU - Pal, Arka
AU - Vicoso, Beatriz
ID - 1513
IS - 12
JF - Genome Biology and Evolution
TI - The X chromosome of hemipteran insects: Conservation, dosage compensation and sex-biased expression
VL - 7
ER -
TY - JOUR
AB - We study the large deviation rate functional for the empirical distribution of independent Brownian particles with drift. In one dimension, it has been shown by Adams, Dirr, Peletier and Zimmer that this functional is asymptotically equivalent (in the sense of Γ-convergence) to the Jordan-Kinderlehrer-Otto functional arising in the Wasserstein gradient flow structure of the Fokker-Planck equation. In higher dimensions, part of this statement (the lower bound) has been recently proved by Duong, Laschos and Renger, but the upper bound remained open, since the proof of Duong et al relies on regularity properties of optimal transport maps that are restricted to one dimension. In this note we present a new proof of the upper bound, thereby generalising the result of Adams et al to arbitrary dimensions.
AU - Erbar, Matthias
AU - Maas, Jan
AU - Renger, Michiel
ID - 1517
JF - Electronic Communications in Probability
TI - From large deviations to Wasserstein gradient flows in multiple dimensions
VL - 20
ER -
TY - JOUR
AB - Evolutionary biologists have an array of powerful theoretical techniques that can accurately predict changes in the genetic composition of populations. Changes in gene frequencies and genetic associations between loci can be tracked as they respond to a wide variety of evolutionary forces. However, it is often less clear how to decompose these various forces into components that accurately reflect the underlying biology. Here, we present several issues that arise in the definition and interpretation of selection and selection coefficients, focusing on insights gained through the examination of selection coefficients in multilocus notation. Using this notation, we discuss how its flexibility-which allows different biological units to be identified as targets of selection-is reflected in the interpretation of the coefficients that the notation generates. In many situations, it can be difficult to agree on whether loci can be considered to be under "direct" versus "indirect" selection, or to quantify this selection. We present arguments for what the terms direct and indirect selection might best encompass, considering a range of issues, from viability and sexual selection to kin selection. We show how multilocus notation can discriminate between direct and indirect selection, and describe when it can do so.
AU - Barton, Nicholas H
AU - Servedio, Maria
ID - 1519
IS - 5
JF - Evolution
TI - The interpretation of selection coefficients
VL - 69
ER -
TY - CONF
AB - Creating mechanical automata that can walk in stable and pleasing manners is a challenging task that requires both skill and expertise. We propose to use computational design to offset the technical difficulties of this process. A simple drag-and-drop interface allows casual users to create personalized walking toys from a library of pre-defined template mechanisms. Provided with this input, our method leverages physical simulation and evolutionary optimization to refine the mechanical designs such that the resulting toys are able to walk. The optimization process is guided by an intuitive set of objectives that measure the quality of the walking motions. We demonstrate our approach on a set of simulated mechanical toys with different numbers of legs and various distinct gaits. Two fabricated prototypes showcase the feasibility of our designs.
AU - Bharaj, Gaurav
AU - Coros, Stelian
AU - Thomaszewski, Bernhard
AU - Tompkin, James
AU - Bickel, Bernd
AU - Pfister, Hanspeter
ID - 1520
SN - 978-1-4503-3496-9
TI - Computational design of walking automata
ER -
TY - JOUR
AB - Based on 16 recommendations, efforts should be made to achieve the following goal: By 2025, all scholarly publication activity in Austria should be Open Access. In other words, the final versions of all scholarly publications resulting from the support of public resources must be freely accessible on the Internet without delay (Gold Open Access). The resources required to meet this obligation shall be provided to the authors, or the cost of the publication venues shall be borne directly by the research organisations.
AU - Bauer, Bruno
AU - Blechl, Guido
AU - Bock, Christoph
AU - Danowski, Patrick
AU - Ferus, Andreas
AU - Graschopf, Anton
AU - König, Thomas
AU - Mayer, Katja
AU - Reckling, Falk
AU - Rieck, Katharina
AU - Seitz, Peter
AU - Stöger, Herwig
AU - Welzig, Elvira
ID - 1525
IS - 3
JF - VÖB Mitteilungen
TI - Arbeitsgruppe „Nationale Strategie“ des Open Access Network Austria OANA
VL - 68
ER -
TY - JOUR
AB - In growing cells, protein synthesis and cell growth are typically not synchronous, and, thus, protein concentrations vary over the cell division cycle. We have developed a theoretical description of genetic regulatory systems in bacteria that explicitly considers the cell division cycle to investigate its impact on gene expression. We calculate the cell-to-cell variations arising from cells being at different stages in the division cycle for unregulated genes and for basic regulatory mechanisms. These variations contribute to the extrinsic noise observed in single-cell experiments, and are most significant for proteins with short lifetimes. Negative autoregulation buffers against variation of protein concentration over the division cycle, but the effect is found to be relatively weak. Stronger buffering is achieved by an increased protein lifetime. Positive autoregulation can strongly amplify such variation if the parameters are set to values that lead to resonance-like behaviour. For cooperative positive autoregulation, the concentration variation over the division cycle diminishes the parameter region of bistability and modulates the switching times between the two stable states. The same effects are seen for a two-gene mutual-repression toggle switch. By contrast, an oscillatory circuit, the repressilator, is only weakly affected by the division cycle.
AU - Bierbaum, Veronika
AU - Klumpp, Stefan
ID - 1530
IS - 6
JF - Physical Biology
TI - Impact of the cell division cycle on gene circuits
VL - 12
ER -
TY - JOUR
AB - The Heat Kernel Signature (HKS) is a scalar quantity which is derived from the heat kernel of a given shape. Due to its robustness, isometry invariance, and multiscale nature, it has been successfully applied in many geometric applications. From a more general point of view, the HKS can be considered as a descriptor of the metric of a Riemannian manifold. Given a symmetric positive definite tensor field we may interpret it as the metric of some Riemannian manifold and thereby apply the HKS to visualize and analyze the given tensor data. In this paper, we propose a generalization of this approach that enables the treatment of indefinite tensor fields, like the stress tensor, by interpreting them as a generator of a positive definite tensor field. To investigate the usefulness of this approach we consider the stress tensor from the two-point-load model example and from a mechanical work piece.
AU - Zobel, Valentin
AU - Jan Reininghaus
AU - Hotz, Ingrid
ID - 1531
JF - Mathematics and Visualization
TI - Visualizing symmetric indefinite 2D tensor fields using The Heat Kernel Signature
VL - 40
ER -
TY - JOUR
AB - This paper addresses the problem of semantic segmentation, where the possible class labels are from a predefined set. We exploit top-down guidance, i.e., the coarse localization of the objects and their class labels provided by object detectors. For each detected bounding box, figure-ground segmentation is performed and the final result is achieved by merging the figure-ground segmentations. The main idea of the proposed approach, which is presented in our preliminary work, is to reformulate the figure-ground segmentation problem as sparse reconstruction pursuing the object mask in a nonparametric manner. The latent segmentation mask should be coherent subject to sparse error caused by intra-category diversity; thus, the object mask is inferred by making use of sparse representations over the training set. To handle local spatial deformations, local patch-level masks are also considered and inferred by sparse representations over the spatially nearby patches. The sparse reconstruction coefficients and the latent mask are alternately optimized by applying the Lasso algorithm and the accelerated proximal gradient method. The proposed formulation results in a convex optimization problem; thus, the global optimal solution is achieved. In this paper, we provide theoretical analysis of the convergence and optimality. We also give an extended numerical analysis of the proposed algorithm and a comprehensive comparison with the related semantic segmentation methods on the challenging PASCAL visual object class object segmentation datasets and the Weizmann horse dataset. The experimental results demonstrate that the proposed algorithm achieves a competitive performance when compared with the state of the arts.
AU - Xia, Wei
AU - Domokos, Csaba
AU - Xiong, Junjun
AU - Cheong, Loongfah
AU - Yan, Shuicheng
ID - 1533
IS - 8
JF - IEEE Transactions on Circuits and Systems for Video Technology
TI - Segmentation over detection via optimal sparse reconstructions
VL - 25
ER -
TY - JOUR
AB - PIN proteins are auxin export carriers that direct intercellular auxin flow and in turn regulate many aspects of plant growth and development including responses to environmental changes. The Arabidopsis R2R3-MYB transcription factor FOUR LIPS (FLP) and its paralogue MYB88 regulate terminal divisions during stomatal development, as well as female reproductive development and stress responses. Here we show that FLP and MYB88 act redundantly but differentially in regulating the transcription of PIN3 and PIN7 in gravity-sensing cells of primary and lateral roots. On the one hand, FLP is involved in responses to gravity stimulation in primary roots, whereas on the other, FLP and MYB88 function complementarily in establishing the gravitropic set-point angles of lateral roots. Our results support a model in which FLP and MYB88 expression specifically determines the temporal-spatial patterns of PIN3 and PIN7 transcription that are closely associated with their preferential functions during root responses to gravity.
AU - Wang, Hongzhe
AU - Yang, Kezhen
AU - Zou, Junjie
AU - Zhu, Lingling
AU - Xie, Zidian
AU - Morita, Miyoterao
AU - Tasaka, Masao
AU - Friml, Jirí
AU - Grotewold, Erich
AU - Beeckman, Tom
AU - Vanneste, Steffen
AU - Sack, Fred
AU - Le, Jie
ID - 1534
JF - Nature Communications
TI - Transcriptional regulation of PIN genes by FOUR LIPS and MYB88 during Arabidopsis root gravitropism
VL - 6
ER -
TY - JOUR
AB - Neuronal and neuroendocrine L-type calcium channels (Cav1.2, Cav1.3) open readily at relatively low membrane potentials and allow Ca2+ to enter the cells near resting potentials. In this way, Cav1.2 and Cav1.3 shape the action potential waveform, contribute to gene expression, synaptic plasticity, neuronal differentiation, hormone secretion and pacemaker activity. In the chromaffin cells (CCs) of the adrenal medulla, Cav1.3 is highly expressed and is shown to support most of the pacemaking current that sustains action potential (AP) firings and part of the catecholamine secretion. Cav1.3 forms Ca2+-nanodomains with the fast inactivating BK channels and drives the resting SK currents. These latter set the inter-spike interval duration between consecutive spikes during spontaneous firing and the rate of spike adaptation during sustained depolarizations. Cav1.3 plays also a primary role in the switch from “tonic” to “burst” firing that occurs in mouse CCs when either the availability of voltage-gated Na channels (Nav) is reduced or the β2 subunit featuring the fast inactivating BK channels is deleted. Here, we discuss the functional role of these “neuronlike” firing modes in CCs and how Cav1.3 contributes to them. The open issue is to understand how these novel firing patterns are adapted to regulate the quantity of circulating catecholamines during resting condition or in response to acute and chronic stress.
AU - Vandael, David H
AU - Marcantoni, Andrea
AU - Carbone, Emilio
ID - 1535
IS - 2
JF - Current Molecular Pharmacology
TI - Cav1.3 channels as key regulators of neuron-like firings and catecholamine release in chromaffin cells
VL - 8
ER -
TY - JOUR
AB - Strigolactones, first discovered as germination stimulants for parasitic weeds [1], are carotenoid-derived phytohormones that play major roles in inhibiting lateral bud outgrowth and promoting plant-mycorrhizal symbiosis [2-4]. Furthermore, strigolactones are involved in the regulation of lateral and adventitious root development, root cell division [5, 6], secondary growth [7], and leaf senescence [8]. Recently, we discovered the strigolactone transporter Petunia axillaris PLEIOTROPIC DRUG RESISTANCE 1 (PaPDR1), which is required for efficient mycorrhizal colonization and inhibition of lateral bud outgrowth [9]. However, how strigolactones are transported through the plant remained unknown. Here we show that PaPDR1 exhibits a cell-type-specific asymmetric localization in different root tissues. In root tips, PaPDR1 is co-expressed with the strigolactone biosynthetic gene DAD1 (CCD8), and it is localized at the apical membrane of root hypodermal cells, presumably mediating the shootward transport of strigolactone. Above the root tip, in the hypodermal passage cells that form gates for the entry of mycorrhizal fungi, PaPDR1 is present in the outer-lateral membrane, compatible with its postulated function as strigolactone exporter from root to soil. Transport studies are in line with our localization studies since (1) a papdr1 mutant displays impaired transport of strigolactones out of the root tip to the shoot as well as into the rhizosphere and (2) DAD1 expression and PIN1/PIN2 levels change in plants deregulated for PDR1 expression, suggestive of variations in endogenous strigolactone contents. In conclusion, our results indicate that the polar localizations of PaPDR1 mediate directional shootward strigolactone transport as well as localized exudation into the soil.
AU - Sasse, Joëlle
AU - Simon, Sibu
AU - Gübeli, Christian
AU - Liu, Guowei
AU - Cheng, Xi
AU - Friml, Jirí
AU - Bouwmeester, Harro
AU - Martinoia, Enrico
AU - Borghi, Lorenzo
ID - 1536
IS - 5
JF - Current Biology
TI - Asymmetric localizations of the ABC transporter PaPDR1 trace paths of directional strigolactone transport
VL - 25
ER -
TY - JOUR
AB - 3D amoeboid cell migration is central to many developmental and disease-related processes such as cancer metastasis. Here, we identify a unique prototypic amoeboid cell migration mode in early zebrafish embryos, termed stable-bleb migration. Stable-bleb cells display an invariant polarized balloon-like shape with exceptional migration speed and persistence. Progenitor cells can be reversibly transformed into stable-bleb cells irrespective of their primary fate and motile characteristics by increasing myosin II activity through biochemical or mechanical stimuli. Using a combination of theory and experiments, we show that, in stable-bleb cells, cortical contractility fluctuations trigger a stochastic switch into amoeboid motility, and a positive feedback between cortical flows and gradients in contractility maintains stable-bleb cell polarization. We further show that rearward cortical flows drive stable-bleb cell migration in various adhesive and non-adhesive environments, unraveling a highly versatile amoeboid migration phenotype.
AU - Ruprecht, Verena
AU - Wieser, Stefan
AU - Callan Jones, Andrew
AU - Smutny, Michael
AU - Morita, Hitoshi
AU - Sako, Keisuke
AU - Barone, Vanessa
AU - Ritsch Marte, Monika
AU - Sixt, Michael K
AU - Voituriez, Raphaël
AU - Heisenberg, Carl-Philipp J
ID - 1537
IS - 4
JF - Cell
TI - Cortical contractility triggers a stochastic switch to fast amoeboid cell motility
VL - 160
ER -
TY - JOUR
AB - Systems biology rests on the idea that biological complexity can be better unraveled through the interplay of modeling and experimentation. However, the success of this approach depends critically on the informativeness of the chosen experiments, which is usually unknown a priori. Here, we propose a systematic scheme based on iterations of optimal experiment design, flow cytometry experiments, and Bayesian parameter inference to guide the discovery process in the case of stochastic biochemical reaction networks. To illustrate the benefit of our methodology, we apply it to the characterization of an engineered light-inducible gene expression circuit in yeast and compare the performance of the resulting model with models identified from nonoptimal experiments. In particular, we compare the parameter posterior distributions and the precision to which the outcome of future experiments can be predicted. Moreover, we illustrate how the identified stochastic model can be used to determine light induction patterns that make either the average amount of protein or the variability in a population of cells follow a desired profile. Our results show that optimal experiment design allows one to derive models that are accurate enough to precisely predict and regulate the protein expression in heterogeneous cell populations over extended periods of time.
AU - Ruess, Jakob
AU - Parise, Francesca
AU - Milias Argeitis, Andreas
AU - Khammash, Mustafa
AU - Lygeros, John
ID - 1538
IS - 26
JF - PNAS
TI - Iterative experiment design guides the characterization of a light-inducible gene expression circuit
VL - 112
ER -
TY - JOUR
AB - Many stochastic models of biochemical reaction networks contain some chemical species for which the number of molecules that are present in the system can only be finite (for instance due to conservation laws), but also other species that can be present in arbitrarily large amounts. The prime example of such networks are models of gene expression, which typically contain a small and finite number of possible states for the promoter but an infinite number of possible states for the amount of mRNA and protein. One of the main approaches to analyze such models is through the use of equations for the time evolution of moments of the chemical species. Recently, a new approach based on conditional moments of the species with infinite state space given all the different possible states of the finite species has been proposed. It was argued that this approach allows one to capture more details about the full underlying probability distribution with a smaller number of equations. Here, I show that the result that less moments provide more information can only stem from an unnecessarily complicated description of the system in the classical formulation. The foundation of this argument will be the derivation of moment equations that describe the complete probability distribution over the finite state space but only low-order moments over the infinite state space. I will show that the number of equations that is needed is always less than what was previously claimed and always less than the number of conditional moment equations up to the same order. To support these arguments, a symbolic algorithm is provided that can be used to derive minimal systems of unconditional moment equations for models with partially finite state space.
AU - Ruess, Jakob
ID - 1539
IS - 24
JF - Journal of Chemical Physics
TI - Minimal moment equations for stochastic models of biochemical reaction networks with partially finite state space
VL - 143
ER -
TY - JOUR
AB - Plant sexual reproduction involves highly structured and specialized organs: stamens (male) and gynoecia (female, containing ovules). These organs synchronously develop within protective flower buds, until anthesis, via tightly coordinated mechanisms that are essential for effective fertilization and production of viable seeds. The phytohormone auxin is one of the key endogenous signalling molecules controlling initiation and development of these, and other, plant organs. In particular, its uneven distribution, resulting from tightly controlled production, metabolism and directional transport, is an important morphogenic factor. In this review we discuss how developmentally controlled and localized auxin biosynthesis and transport contribute to the coordinated development of plants' reproductive organs, and their fertilized derivatives (embryos) via the regulation of auxin levels and distribution within and around them. Current understanding of the links between de novo local auxin biosynthesis, auxin transport and/or signalling is presented to highlight the importance of the non-cell autonomous action of auxin production on development and morphogenesis of reproductive organs and embryos. An overview of transcription factor families, which spatiotemporally define local auxin production by controlling key auxin biosynthetic enzymes, is also presented.
AU - Robert, Hélène
AU - Crhák Khaitová, Lucie
AU - Mroue, Souad
AU - Benková, Eva
ID - 1540
IS - 16
JF - Journal of Experimental Botany
TI - The importance of localized auxin production for morphogenesis of reproductive organs and embryos in Arabidopsis
VL - 66
ER -
TY - CONF
AB - We present XSpeed a parallel state-space exploration algorithm for continuous systems with linear dynamics and nondeterministic inputs. The motivation of having parallel algorithms is to exploit the computational power of multi-core processors to speed-up performance. The parallelization is achieved on two fronts. First, we propose a parallel implementation of the support function algorithm by sampling functions in parallel. Second, we propose a parallel state-space exploration by slicing the time horizon and computing the reachable states in the time slices in parallel. The second method can be however applied only to a class of linear systems with invertible dynamics and fixed input. A GP-GPU implementation is also presented following a lazy evaluation strategy on support functions. The parallel algorithms are implemented in the tool XSpeed. We evaluated the performance on two benchmarks including an 28 dimension Helicopter model. Comparison with the sequential counterpart shows a maximum speed-up of almost 7× on a 6 core, 12 thread Intel Xeon CPU E5-2420 processor. Our GP-GPU implementation shows a maximum speed-up of 12× over the sequential implementation and 53× over SpaceEx (LGG scenario), the state of the art tool for reachability analysis of linear hybrid systems. Experiments illustrate that our parallel algorithm with time slicing not only speeds-up performance but also improves precision.
AU - Ray, Rajarshi
AU - Gurung, Amit
AU - Das, Binayak
AU - Bartocci, Ezio
AU - Bogomolov, Sergiy
AU - Grosu, Radu
ID - 1541
TI - XSpeed: Accelerating reachability analysis on multi-core processors
VL - 9434
ER -
TY - JOUR
AB - The theory of population genetics and evolutionary computation have been evolving separately for nearly 30 years. Many results have been independently obtained in both fields and many others are unique to its respective field. We aim to bridge this gap by developing a unifying framework for evolutionary processes that allows both evolutionary algorithms and population genetics models to be cast in the same formal framework. The framework we present here decomposes the evolutionary process into its several components in order to facilitate the identification of similarities between different models. In particular, we propose a classification of evolutionary operators based on the defining properties of the different components. We cast several commonly used operators from both fields into this common framework. Using this, we map different evolutionary and genetic algorithms to different evolutionary regimes and identify candidates with the most potential for the translation of results between the fields. This provides a unified description of evolutionary processes and represents a stepping stone towards new tools and results to both fields.
AU - Paixao, Tiago
AU - Badkobeh, Golnaz
AU - Barton, Nicholas H
AU - Çörüş, Doğan
AU - Dang, Duccuong
AU - Friedrich, Tobias
AU - Lehre, Per
AU - Sudholt, Dirk
AU - Sutton, Andrew
AU - Trubenova, Barbora
ID - 1542
JF - Journal of Theoretical Biology
TI - Toward a unifying framework for evolutionary processes
VL - 383
ER -
TY - JOUR
AB - A plethora of diverse programmed cell death (PCD) processes has been described in living organisms. In animals and plants, different forms of PCD play crucial roles in development, immunity, and responses to the environment. While the molecular control of some animal PCD forms such as apoptosis is known in great detail, we still know comparatively little about the regulation of the diverse types of plant PCD. In part, this deficiency in molecular understanding is caused by the lack of reliable reporters to detect PCD processes. Here, we addressed this issue by using a combination of bioinformatics approaches to identify commonly regulated genes during diverse plant PCD processes in Arabidopsis (Arabidopsis thaliana). Our results indicate that the transcriptional signatures of developmentally controlled cell death are largely distinct from the ones associated with environmentally induced cell death. Moreover, different cases of developmental PCD share a set of cell death-associated genes. Most of these genes are evolutionary conserved within the green plant lineage, arguing for an evolutionary conserved core machinery of developmental PCD. Based on this information, we established an array of specific promoter-reporter lines for developmental PCD in Arabidopsis. These PCD indicators represent a powerful resource that can be used in addition to established morphological and biochemical methods to detect and analyze PCD processes in vivo and in planta.
AU - Olvera Carrillo, Yadira
AU - Van Bel, Michiel
AU - Van Hautegem, Tom
AU - Fendrych, Matyas
AU - Huysmans, Marlies
AU - Šimášková, Mária
AU - Van Durme, Matthias
AU - Buscaill, Pierre
AU - Rivas, Susana
AU - Coll, Núria
AU - Coppens, Frederik
AU - Maere, Steven
AU - Nowack, Moritz
ID - 1543
IS - 4
JF - Plant Physiology
TI - A conserved core of programmed cell death indicator genes discriminates developmentally and environmentally induced programmed cell death in plants
VL - 169
ER -
TY - CHAP
AB - Cell division in prokaryotes and eukaryotes is commonly initiated by the well-controlled binding of proteins to the cytoplasmic side of the cell membrane. However, a precise characterization of the spatiotemporal dynamics of membrane-bound proteins is often difficult to achieve in vivo. Here, we present protocols for the use of supported lipid bilayers to rebuild the cytokinetic machineries of cells with greatly different dimensions: the bacterium Escherichia coli and eggs of the vertebrate Xenopus laevis. Combined with total internal reflection fluorescence microscopy, these experimental setups allow for precise quantitative analyses of membrane-bound proteins. The protocols described to obtain glass-supported membranes from bacterial and vertebrate lipids can be used as starting points for other reconstitution experiments. We believe that similar biochemical assays will be instrumental to study the biochemistry and biophysics underlying a variety of complex cellular tasks, such as signaling, vesicle trafficking, and cell motility.
AU - Nguyen, Phuong
AU - Field, Christine
AU - Groen, Aaron
AU - Mitchison, Timothy
AU - Loose, Martin
ID - 1544
T2 - Building a Cell from its Components Parts
TI - Using supported bilayers to study the spatiotemporal organization of membrane-bound proteins
VL - 128
ER -
TY - JOUR
AB - Synaptic efficacy and precision are influenced by the coupling of voltage-gated Ca2+ channels (VGCCs) to vesicles. But because the topography of VGCCs and their proximity to vesicles is unknown, a quantitative understanding of the determinants of vesicular release at nanometer scale is lacking. To investigate this, we combined freeze-fracture replica immunogold labeling of Cav2.1 channels, local [Ca2+] imaging, and patch pipette perfusion of EGTA at the calyx of Held. Between postnatal day 7 and 21, VGCCs formed variable sized clusters and vesicular release became less sensitive to EGTA, whereas fixed Ca2+ buffer properties remained constant. Experimentally constrained reaction-diffusion simulations suggest that Ca2+ sensors for vesicular release are located at the perimeter of VGCC clusters (<30nm) and predict that VGCC number per cluster determines vesicular release probability without altering release time course. This "perimeter release model" provides a unifying framework accounting for developmental changes in both synaptic efficacy and time course.
AU - Nakamura, Yukihiro
AU - Harada, Harumi
AU - Kamasawa, Naomi
AU - Matsui, Ko
AU - Rothman, Jason
AU - Shigemoto, Ryuichi
AU - Silver, R Angus
AU - Digregorio, David
AU - Takahashi, Tomoyuki
ID - 1546
IS - 1
JF - Neuron
TI - Nanoscale distribution of presynaptic Ca2+ channels and its impact on vesicular release during development
VL - 85
ER -
TY - JOUR
AB - Let G be a graph on the vertex set V(G) = {x1,…,xn} with the edge set E(G), and let R = K[x1,…, xn] be the polynomial ring over a field K. Two monomial ideals are associated to G, the edge ideal I(G) generated by all monomials xixj with {xi,xj} ∈ E(G), and the vertex cover ideal IG generated by monomials ∏xi∈Cxi for all minimal vertex covers C of G. A minimal vertex cover of G is a subset C ⊂ V(G) such that each edge has at least one vertex in C and no proper subset of C has the same property. Indeed, the vertex cover ideal of G is the Alexander dual of the edge ideal of G. In this paper, for an unmixed bipartite graph G we consider the lattice of vertex covers LG and we explicitly describe the minimal free resolution of the ideal associated to LG which is exactly the vertex cover ideal of G. Then we compute depth, projective dimension, regularity and extremal Betti numbers of R/I(G) in terms of the associated lattice.
AU - Mohammadi, Fatemeh
AU - Moradi, Somayeh
ID - 1547
IS - 3
JF - Bulletin of the Korean Mathematical Society
TI - Resolution of unmixed bipartite graphs
VL - 52
ER -
TY - JOUR
AB - Reproduction within a host and transmission to the next host are crucial for the virulence and fitness of pathogens. Nevertheless, basic knowledge about such parameters is often missing from the literature, even for well-studied bacteria, such as Bacillus thuringiensis, an endospore-forming insect pathogen, which infects its hosts via the oral route. To characterize bacterial replication success, we made use of an experimental oral infection system for the red flour beetle Tribolium castaneum and developed a flow cytometric assay for the quantification of both spore ingestion by the individual beetle larvae and the resulting spore load after bacterial replication and resporulation within cadavers. On average, spore numbers increased 460-fold, showing that Bacillus thuringiensis grows and replicates successfully in insect cadavers. By inoculating cadaver-derived spores and spores from bacterial stock cultures into nutrient medium, we next investigated outgrowth characteristics of vegetative cells and found that cadaver- derived bacteria showed reduced growth compared to bacteria from the stock cultures. Interestingly, this reduced growth was a consequence of inhibited spore germination, probably originating from the host and resulting in reduced host mortality in subsequent infections by cadaver-derived spores. Nevertheless, we further showed that Bacillus thuringiensis transmission was possible via larval cannibalism when no other food was offered. These results contribute to our understanding of the ecology of Bacillus thuringiensis as an insect pathogen.
AU - Milutinovic, Barbara
AU - Höfling, Christina
AU - Futo, Momir
AU - Scharsack, Jörn
AU - Kurtz, Joachim
ID - 1548
IS - 23
JF - Applied and Environmental Microbiology
TI - Infection of Tribolium castaneum with Bacillus thuringiensis: Quantification of bacterial replication within cadavers, transmission via cannibalism, and inhibition of spore germination
VL - 81
ER -