Exact and approximate determinization of discounted-sum automata - Boker, Udi; Henzinger, Thomas A (Logical Methods in Computer Science)
A discounted-sum automaton (NDA) is a nondeterministic finite automaton with edge weights, valuing a run by the discounted sum of visited edge weights. More precisely, the weight in the i-th position of the run is divided by λi, where the discount factor λ is a fixed rational number greater than 1. The value of a word is the minimal value of the automaton runs on it. Discounted summation is a common and useful measuring scheme, especially for infinite sequences, reflecting the assumption that earlier weights are more important than later weights. Unfortunately, determinization of NDAs, which is often essential in formal verification, is, in general, not possible. We provide positive news, showing that every NDA with an integral discount factor is determinizable. We complete the picture by proving that the integers characterize exactly the discount factors that guarantee determinizability: for every nonintegral rational discount factor λ, there is a nondeterminizable λ-NDA. We also prove that the class of NDAs with integral discount factors enjoys closure under the algebraic operations min, max, addition, and subtraction, which is not the case for general NDAs nor for deterministic NDAs. For general NDAs, we look into approximate determinization, which is always possible as the influence of a word's suffix decays. We show that the naive approach, of unfolding the automaton computations up to a sufficient level, is doubly exponential in the discount factor. We provide an alternative construction for approximate determinization, which is singly exponential in the discount factor, in the precision, and in the number of states. We also prove matching lower bounds, showing that the exponential dependency on each of these three parameters cannot be avoided. All our results hold equally for automata over finite words and for automata over infinite words.

Markov decision processes with multiple long-run average objectives - Brázdil, Tomáš; Brožek, Václav; Chatterjee, Krishnendu; Forejt, Vojtěch; Kučera, Antonín (Logical Methods in Computer Science)
We study Markov decision processes (MDPs) with multiple limit-average (or mean-payoff) functions. We consider two different objectives, namely, expectation and satisfaction objectives. Given an MDP with κ limit-average functions, in the expectation objective the goal is to maximize the expected limit-average value, and in the satisfaction objective the goal is to maximize the probability of runs such that the limit-average value stays above a given vector. We show that under the expectation objective, in contrast to the case of one limit-average function, both randomization and memory are necessary for strategies even for ε-approximation, and that finite-memory randomized strategies are sufficient for achieving Pareto optimal values. Under the satisfaction objective, in contrast to the case of one limit-average function, infinite memory is necessary for strategies achieving a specific value (i.e. randomized finite-memory strategies are not sufficient), whereas memoryless randomized strategies are sufficient for ε-approximation, for all ε > 0. We further prove that the decision problems for both expectation and satisfaction objectives can be solved in polynomial time and the trade-off curve (Pareto curve) can be ε-approximated in time polynomial in the size of the MDP and 1/ε, and exponential in the number of limit-average functions, for all ε > 0. Our analysis also reveals flaws in previous work for MDPs with multiple mean-payoff functions under the expectation objective, corrects the flaws, and allows us to obtain improved results.

Disease associations between honeybees and bumblebees as a threat to wild pollinators - Fürst, Matthias; Mcmahon, Dino; Osborne, Juliet; Paxton, Robert; Brown, Mark (Nature)
Emerging infectious diseases (EIDs) pose a risk to human welfare, both directly and indirectly, by affecting managed livestock and wildlife that provide valuable resources and ecosystem services, such as the pollination of crops. Honeybees (Apis mellifera), the prevailing managed insect crop pollinator, suffer from a range of emerging and exotic high-impact pathogens, and population maintenance requires active management by beekeepers to control them. Wild pollinators such as bumblebees (Bombus spp.) are in global decline, one cause of which may be pathogen spillover from managed pollinators like honeybees or commercial colonies of bumblebees. Here we use a combination of infection experiments and landscape-scale field data to show that honeybee EIDs are indeed widespread infectious agents within the pollinator assemblage. The prevalence of deformed wing virus (DWV) and the exotic parasite Nosema ceranae in honeybees and bumblebees is linked; as honeybees have higher DWV prevalence, and sympatric bumblebees and honeybees are infected by the same DWV strains, Apis is the likely source of at least one major EID in wild pollinators. Lessons learned from vertebrates highlight the need for increased pathogen control in managed bee species to maintain wild pollinators, as declines in native pollinators may be caused by interspecies pathogen transmission originating from managed pollinators.

How to fake auxiliary input - Jetchev, Dimitar; Pietrzak, Krzysztof Z
Consider a joint distribution (X,A) on a set. We show that for any family of distinguishers, there exists a simulator such that 1 no function in can distinguish (X,A) from (X,h(X)) with advantage ε, 2 h is only O(2 3ℓ ε -2) times less efficient than the functions in. For the most interesting settings of the parameters (in particular, the cryptographic case where X has superlogarithmic min-entropy, ε > 0 is negligible and consists of circuits of polynomial size), we can make the simulator h deterministic. As an illustrative application of our theorem, we give a new security proof for the leakage-resilient stream-cipher from Eurocrypt'09. Our proof is simpler and quantitatively much better than the original proof using the dense model theorem, giving meaningful security guarantees if instantiated with a standard blockcipher like AES. Subsequent to this work, Chung, Lui and Pass gave an interactive variant of our main theorem, and used it to investigate weak notions of Zero-Knowledge. Vadhan and Zheng give a more constructive version of our theorem using their new uniform min-max theorem.

Battery transition systems - Boker, Udi; Henzinger, Thomas A; Radhakrishna, Arjun
The analysis of the energy consumption of software is an important goal for quantitative formal methods. Current methods, using weighted transition systems or energy games, model the energy source as an ideal resource whose status is characterized by one number, namely the amount of remaining energy. Real batteries, however, exhibit behaviors that can deviate substantially from an ideal energy resource. Based on a discretization of a standard continuous battery model, we introduce battery transition systems. In this model, a battery is viewed as consisting of two parts-the available-charge tank and the bound-charge tank. Any charge or discharge is applied to the available-charge tank. Over time, the energy from each tank diffuses to the other tank. Battery transition systems are infinite state systems that, being not well-structured, fall into no decidable class that is known to us. Nonetheless, we are able to prove that the !-regular modelchecking problem is decidable for battery transition systems. We also present a case study on the verification of control programs for energy-constrained semi-autonomous robots.

The TPLATE adaptor complex drives clathrin-mediated endocytosis in plants - Gadeyne, Astrid; Sánchez Rodríguez, Clara; Vanneste, Steffen; Di Rubbo, Simone; Zauber, Henrik; Vanneste, Kevin; Van Leene, Jelle; De Winne, Nancy; Eeckhout, Dominique; Persiau, Geert; Van De Slijke, Eveline; Cannoot, Bernard; et al. (Cell)
Clathrin-mediated endocytosis is the major mechanism for eukaryotic plasma membrane-based proteome turn-over. In plants, clathrin-mediated endocytosis is essential for physiology and development, but the identification and organization of the machinery operating this process remains largely obscure. Here, we identified an eight-core-component protein complex, the TPLATE complex, essential for plant growth via its role as major adaptor module for clathrin-mediated endocytosis. This complex consists of evolutionarily unique proteins that associate closely with core endocytic elements. The TPLATE complex is recruited as dynamic foci at the plasma membrane preceding recruitment of adaptor protein complex 2, clathrin, and dynamin-related proteins. Reduced function of different complex components severely impaired internalization of assorted endocytic cargoes, demonstrating its pivotal role in clathrin-mediated endocytosis. Taken together, the TPLATE complex is an early endocytic module representing a unique evolutionary plant adaptation of the canonical eukaryotic pathway for clathrin-mediated endocytosis.

Optogenetic countering of glial acidosis suppresses glial glutamate release and ischemic brain damage - Beppu, Kaoru; Sasaki, Takuya; Tanaka, Kenji; Yamanaka, Akihiro; Fukazawa, Yugo; Shigemoto, Ryuichi; Matsui, Ko (Neuron)
The brain demands high-energy supply and obstruction of blood flow causes rapid deterioration of the healthiness of brain cells. Two major events occur upon ischemia: acidosis and liberation of excess glutamate, which leads to excitotoxicity. However, cellular source of glutamate and its release mechanism upon ischemia remained unknown. Here we show a causal relationship between glial acidosis and neuronal excitotoxicity. As the major cation that flows through channelrhodopsin-2 (ChR2) is proton, this could be regarded as an optogenetic tool for instant intracellular acidification. Optical activation of ChR2 expressed in glial cells led to glial acidification and to release of glutamate. On the other hand, glial alkalization via optogenetic activation of a proton pump, archaerhodopsin (ArchT), led to cessation of glutamate release and to the relief of ischemic brain damage in vivo. Our results suggest that controlling glial pH may be an effective therapeutic strategy for intervention of ischemic brain damage.

A miR-155-dependent microRNA hierarchy in dendritic cell maturation and macrophage activation - Dueck, Anne; Eichner, Alexander; Sixt, Michael K; Meister, Gunter (FEBS Letters)
MicroRNAs (miRNAs) are small RNAs that play important regulatory roles in many cellular pathways. MiRNAs associate with members of the Argonaute protein family and bind to partially complementary sequences on mRNAs and induce translational repression or mRNA decay. Using deep sequencing and Northern blotting, we characterized miRNA expression in wild type and miR-155-deficient dendritic cells (DCs) and macrophages. Analysis of different stimuli (LPS, LDL, eLDL, oxLDL) reveals a direct influence of miR-155 on the expression levels of other miRNAs. For example, miR-455 is negatively regulated in miR-155-deficient cells possibly due to inhibition of the transcription factor C/EBPbeta by miR-155. Based on our comprehensive data sets, we propose a model of hierarchical miRNA expression dominated by miR-155 in DCs and macrophages.

Analyzing the in vivo status of exogenously applied auxins: A HPLC-based method to characterize the intracellularly localized auxin transporters - Simon, Sibu; Skůpa, Petr; Dobrev, Petre; Petrášek, Jan; Zažímalová, Eva; Friml, Jirí (Plant Chemical Genomics)
Exogenous application of biologically important molecules for plant growth promotion and/or regulation is very common both in plant research and horticulture. Plant hormones such as auxins and cytokinins are classes of compounds which are often applied exogenously. Nevertheless, plants possess a well-established machinery to regulate the active pool of exogenously applied compounds by converting them to metabolites and conjugates. Consequently, it is often very useful to know the in vivo status of applied compounds to connect them with some of the regulatory events in plant developmental processes. The in vivo status of applied compounds can be measured by incubating plants with radiolabeled compounds, followed by extraction, purification, and HPLC metabolic profiling of plant extracts. Recently we have used this method to characterize the intracellularly localized PIN protein, PIN5. Here we explain the method in detail, with a focus on general application.

Alternating traps in Muller and parity games - Grinshpun, Andrey; Phalitnonkiat, Pakawat; Rubin, Sasha; Tarfulea, Andrei (Theoretical Computer Science)
Muller games are played by two players moving a token along a graph; the winner is determined by the set of vertices that occur infinitely often. The central algorithmic problem is to compute the winning regions for the players. Different classes and representations of Muller games lead to problems of varying computational complexity. One such class are parity games; these are of particular significance in computational complexity, as they remain one of the few combinatorial problems known to be in NP ∩ co-NP but not known to be in P. We show that winning regions for a Muller game can be determined from the alternating structure of its traps. To every Muller game we then associate a natural number that we call its trap depth; this parameter measures how complicated the trap structure is. We present algorithms for parity games that run in polynomial time for graphs of bounded trap depth, and in general run in time exponential in the trap depth.

Thumbs down: A molecular-morphogenetic approach to avian digit homology - Capek, Daniel; Metscher, Brian; Müller, Gerd (Journal of Experimental Zoology Part B: Molecular and Developmental Evolution)
Avian forelimb digit homology remains one of the standard themes in comparative biology and EvoDevo research. In order to resolve the apparent contradictions between embryological and paleontological evidence a variety of hypotheses have been presented in recent years. The proposals range from excluding birds from the dinosaur clade, to assignments of homology by different criteria, or even assuming a hexadactyl tetrapod limb ground state. At present two approaches prevail: the frame shift hypothesis and the pyramid reduction hypothesis. While the former postulates a homeotic shift of digit identities, the latter argues for a gradual bilateral reduction of phalanges and digits. Here we present a new model that integrates elements from both hypotheses with the existing experimental and fossil evidence. We start from the main feature common to both earlier concepts, the initiating ontogenetic event: reduction and loss of the anterior-most digit. It is proposed that a concerted mechanism of molecular regulation and developmental mechanics is capable of shifting the boundaries of hoxD expression in embryonic forelimb buds as well as changing the digit phenotypes. Based on a distinction between positional (topological) and compositional (phenotypic) homology criteria, we argue that the identity of the avian digits is II, III, IV, despite a partially altered phenotype. Finally, we introduce an alternative digit reduction scheme that reconciles the current fossil evidence with the presented molecular-morphogenetic model. Our approach identifies specific experiments that allow to test whether gene expression can be shifted and digit phenotypes can be altered by induced digit loss or digit gain.

Inter-regulation of the unfolded protein response and auxin signaling - Chen, Yani; Aung, Kyaw; Rolčík, Jakub; Walicki, Kathryn; Friml, Jirí; Brandizzí, Federica (Plant Journal)
The unfolded protein response (UPR) is a signaling network triggered by overload of protein-folding demand in the endoplasmic reticulum (ER), a condition termed ER stress. The UPR is critical for growth and development; nonetheless, connections between the UPR and other cellular regulatory processes remain largely unknown. Here, we identify a link between the UPR and the phytohormone auxin, a master regulator of plant physiology. We show that ER stress triggers down-regulation of auxin receptors and transporters in Arabidopsis thaliana. We also demonstrate that an Arabidopsis mutant of a conserved ER stress sensor IRE1 exhibits defects in the auxin response and levels. These data not only support that the plant IRE1 is required for auxin homeostasis, they also reveal a species-specific feature of IRE1 in multicellular eukaryotes. Furthermore, by establishing that UPR activation is reduced in mutants of ER-localized auxin transporters, including PIN5, we define a long-neglected biological significance of ER-based auxin regulation. We further examine the functional relationship of IRE1 and PIN5 by showing that an ire1 pin5 triple mutant enhances defects of UPR activation and auxin homeostasis in ire1 or pin5. Our results imply that the plant UPR has evolved a hormone-dependent strategy for coordinating ER function with physiological processes.

Powerful sequence similarity search methods and in-depth manual analyses can identify remote homologs in many apparently "orphan" viral proteins - Kuchibhatla, Durga; Sherman, Westley; Chung, Betty; Cook, Shelley; Schneider, Georg; Eisenhaber, Birgit; Karlin, David (Journal of Virology)
The genome sequences of new viruses often contain many "orphan" or "taxon-specific" proteins apparently lacking homologs. However, because viral proteins evolve very fast, commonly used sequence similarity detection methods such as BLAST may overlook homologs. We analyzed a data set of proteins from RNA viruses characterized as "genus specific" by BLAST. More powerful methods developed recently, such as HHblits or HHpred (available through web-based, user-friendly interfaces), could detect distant homologs of a quarter of these proteins, suggesting that these methods should be used to annotate viral genomes. In-depth manual analyses of a subset of the remaining sequences, guided by contextual information such as taxonomy, gene order, or domain cooccurrence, identified distant homologs of another third. Thus, a combination of powerful automated methods and manual analyses can uncover distant homologs of many proteins thought to be orphans. We expect these methodological results to be also applicable to cellular organisms, since they generally evolve much more slowly than RNA viruses. As an application, we reanalyzed the genome of a bee pathogen, Chronic bee paralysis virus (CBPV). We could identify homologs of most of its proteins thought to be orphans; in each case, identifying homologs provided functional clues. We discovered that CBPV encodes a domain homologous to the Alphavirus methyltransferase-guanylyltransferase; a putative membrane protein, SP24, with homologs in unrelated insect viruses and insect-transmitted plant viruses having different morphologies (cileviruses, higreviruses, blunerviruses, negeviruses); and a putative virion glycoprotein, ORF2, also found in negeviruses. SP24 and ORF2 are probably major structural components of the virionsd.

Sharp wave/ripple network oscillations and learning-associated hippocampal maps - Csicsvari, Jozsef L; Dupret, David (Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences)
Sharp wave/ripple (SWR, 150–250 Hz) hippocampal events have long been postulated to be involved in memory consolidation. However, more recent work has investigated SWRs that occur during active waking behaviour: findings that suggest that SWRs may also play a role in cell assembly strengthening or spatial working memory. Do such theories of SWR function apply to animal learning? This review discusses how general theories linking SWRs to memory-related function may explain circuit mechanisms related to rodent spatial learning and to the associated stabilization of new cognitive maps.

Genetic background alters dominance relationships between mat alleles in the ciliate Tetrahymena Thermophila - Phadke, Sujal; Paixao, Tiago; Pham, Tuan; Pham, Stephanie; Zufall, Rebecca (Journal of Heredity)
The pattern of inheritance and mechanism of sex determination can have important evolutionary consequences. We studied probabilistic sex determination in the ciliate Tetrahymena thermophila, which was previously shown to cause evolution of skewed sex ratios. We find that the genetic background alters the sex determination patterns of mat alleles in heterozygotes and that allelic interaction can differentially influence the expression probability of the 7 sexes. We quantify the dominance relationships between several mat alleles and find that A-type alleles, which specify sex I, are indeed recessive to B-type alleles, which are unable to specify that sex. Our results provide additional support for the presence of modifier loci and raise implications for the dynamics of sex ratios in populations of T. thermophila.

Expression of TWISTED DWARF1 lacking its in-plane membrane anchor leads to increased cell elongation and hypermorphic growth - Bailly, Aurélien; Wang, Bangjun; Zwiewka, Marta; Pollmann, Stephan; Schenck, Daniel; Lüthen, Hartwig; Schulz, Alexander; Friml, Jirí; Geisler, Markus (Plant Journal)
Plant growth is achieved predominantly by cellular elongation, which is thought to be controlled on several levels by apoplastic auxin. Auxin export into the apoplast is achieved by plasma membrane efflux catalysts of the PIN-FORMED (PIN) and ATP-binding cassette protein subfamily B/phosphor- glycoprotein (ABCB/PGP) classes; the latter were shown to depend on interaction with the FKBP42, TWISTED DWARF1 (TWD1). Here by using a transgenic approach in combination with phenotypical, biochemical and cell biological analyses we demonstrate the importance of a putative C-terminal in-plane membrane anchor of TWD1 in the regulation of ABCB-mediated auxin transport. In contrast with dwarfed twd1 loss-of-function alleles, TWD1 gain-of-function lines that lack a putative in-plane membrane anchor (HA-TWD1-Ct) show hypermorphic plant architecture, characterized by enhanced stem length and leaf surface but reduced shoot branching. Greater hypocotyl length is the result of enhanced cell elongation that correlates with reduced polar auxin transport capacity for HA-TWD1-Ct. As a consequence, HA-TWD1-Ct displays higher hypocotyl auxin accumulation, which is shown to result in elevated auxin-induced cell elongation rates. Our data highlight the importance of C-terminal membrane anchoring for TWD1 action, which is required for specific regulation of ABCB-mediated auxin transport. These data support a model in which TWD1 controls lateral ABCB1-mediated export into the apoplast, which is required for auxin-mediated cell elongation.

Theta-gamma-modulated synaptic currents in hippocampal granule cells in vivo define a mechanism for network oscillations - Pernia-Andrade, Alejandro; Jonas, Peter M (Neuron)
Theta-gamma network oscillations are thought to represent key reference signals for information processing in neuronal ensembles, but the underlying synaptic mechanisms remain unclear. To address this question, we performed whole-cell (WC) patch-clamp recordings from mature hippocampal granule cells (GCs) in vivo in the dentate gyrus of anesthetized and awake rats. GCs in vivo fired action potentials at low frequency, consistent with sparse coding in the dentate gyrus. GCs were exposed to barrages of fast AMPAR-mediated excitatory postsynaptic currents (EPSCs), primarily relayed from the entorhinal cortex, and inhibitory postsynaptic currents (IPSCs), presumably generated by local interneurons. EPSCs exhibited coherence with the field potential predominantly in the theta frequency band, whereas IPSCs showed coherence primarily in the gamma range. Action potentials in GCs were phase locked to network oscillations. Thus, theta-gamma-modulated synaptic currents may provide a framework for sparse temporal coding of information in the dentate gyrus.

Stable length estimates of tube-like shapes - Edelsbrunner, Herbert; Pausinger, Florian (Journal of Mathematical Imaging and Vision)
Motivated by applications in biology, we present an algorithm for estimating the length of tube-like shapes in 3-dimensional Euclidean space. In a first step, we combine the tube formula of Weyl with integral geometric methods to obtain an integral representation of the length, which we approximate using a variant of the Koksma-Hlawka Theorem. In a second step, we use tools from computational topology to decrease the dependence on small perturbations of the shape. We present computational experiments that shed light on the stability and the convergence rate of our algorithm.

Searching for collective behavior in a large network of sensory neurons - Tkacik, Gasper; Marre, Olivier; Amodei, Dario; Schneidman, Elad; Bialek, William; Berry, Michael (PLoS Computational Biology)
Maximum entropy models are the least structured probability distributions that exactly reproduce a chosen set of statistics measured in an interacting network. Here we use this principle to construct probabilistic models which describe the correlated spiking activity of populations of up to 120 neurons in the salamander retina as it responds to natural movies. Already in groups as small as 10 neurons, interactions between spikes can no longer be regarded as small perturbations in an otherwise independent system; for 40 or more neurons pairwise interactions need to be supplemented by a global interaction that controls the distribution of synchrony in the population. Here we show that such “K-pairwise” models—being systematic extensions of the previously used pairwise Ising models—provide an excellent account of the data. We explore the properties of the neural vocabulary by: 1) estimating its entropy, which constrains the population's capacity to represent visual information; 2) classifying activity patterns into a small set of metastable collective modes; 3) showing that the neural codeword ensembles are extremely inhomogenous; 4) demonstrating that the state of individual neurons is highly predictable from the rest of the population, allowing the capacity for error correction.

DICE, an efficient system for iterative genomic editing in human pluripotent stem cells - Zhu, Fangfang; Gamboa, Matthew; Farruggio, Alfonso; Hippenmeyer, Simon; Tasic, Bosiljka; Schüle, Birgitt; Chen Tsai, Yanru; Calos, Michele (Nucleic Acids Research)
To reveal the full potential of human pluripotent stem cells, new methods for rapid, site-specific genomic engineering are needed. Here, we describe a system for precise genetic modification of human embryonic stem cells (ESCs) and induced pluripotent stem cells (iPSCs). We identified a novel human locus, H11, located in a safe, intergenic, transcriptionally active region of chromosome 22, as the recipient site, to provide robust, ubiquitous expression of inserted genes. Recipient cell lines were established by site-specific placement of a ‘landing pad’ cassette carrying attP sites for phiC31 and Bxb1 integrases at the H11 locus by spontaneous or TALEN-assisted homologous recombination. Dual integrase cassette exchange (DICE) mediated by phiC31 and Bxb1 integrases was used to insert genes of interest flanked by phiC31 and Bxb1 attB sites at the H11 locus, replacing the landing pad. This system provided complete control over content, direction and copy number of inserted genes, with a specificity of 100%. A series of genes, including mCherry and various combinations of the neural transcription factors LMX1a, FOXA2 and OTX2, were inserted in recipient cell lines derived from H9 ESC, as well as iPSC lines derived from a Parkinson’s disease patient and a normal sibling control. The DICE system offers rapid, efficient and precise gene insertion in ESC and iPSC and is particularly well suited for repeated modifications of the same locus.