@article{2941, author = {Dolbilin, Nikolai and Edelsbrunner, Herbert and Musin, Oleg}, journal = {Russian Mathematical Surveys}, number = {4}, pages = {781 -- 783}, publisher = {IOP Publishing}, title = {{On the optimality of functionals over triangulations of Delaunay sets}}, doi = {10.1070/RM2012v067n04ABEH004807}, volume = {67}, year = {2012}, } @inproceedings{2942, abstract = {Interface theories provide a formal framework for component-based development of software and hardware which supports the incremental design of systems and the independent implementability of components. These capabilities are ensured through mathematical properties of the parallel composition operator and the refinement relation for components. More recently, a conjunction operation was added to interface theories in order to provide support for handling multiple viewpoints, requirements engineering, and component reuse. Unfortunately, the conjunction operator does not allow independent implementability in general. In this paper, we study conditions that need to be imposed on interface models in order to enforce independent implementability with respect to conjunction. We focus on multiple viewpoint specifications and propose a new compatibility criterion between two interfaces, which we call orthogonality. We show that orthogonal interfaces can be refined separately, while preserving both orthogonality and composability with other interfaces. We illustrate the independent implementability of different viewpoints with a FIFO buffer example.}, author = {Henzinger, Thomas A and Nickovic, Dejan}, booktitle = { Conference proceedings Monterey Workshop 2012}, location = {Oxford, UK}, pages = {380 -- 395}, publisher = {Springer}, title = {{Independent implementability of viewpoints}}, doi = {10.1007/978-3-642-34059-8_20}, volume = {7539}, year = {2012}, } @article{2943, abstract = {We examine whether the Escherichia coli chromosome is folded into a self-adherent nucleoprotein complex, or alternately is a confined but otherwise unconstrained self-avoiding polymer. We address this through in vivo visualization, using an inducible GFP fusion to the nucleoid-associated protein Fis to non-specifically decorate the entire chromosome. For a range of different growth conditions, the chromosome is a compact structure that does not fill the volume of the cell, and which moves from the new pole to the cell centre. During rapid growth, chromosome segregation occurs well before cell division, with daughter chromosomes coupled by a thin inter-daughter filament before complete segregation, whereas during slow growth chromosomes stay adjacent until cell division occurs. Image correlation analysis indicates that sub-nucleoid structure is stable on a 1min timescale, comparable to the timescale for redistribution time measured for GFP-Fis after photobleaching. Optical deconvolution and writhe calculation analysis indicate that the nucleoid has a large-scale coiled organization rather than being an amorphous mass. Our observations are consistent with the chromosome having a self-adherent filament organization.}, author = {Hadizadeh Yazdi, Nastaran and Guet, Calin C and Johnson, Reid and Marko, John}, journal = {Molecular Microbiology}, number = {6}, pages = {1318 -- 1333}, publisher = {Wiley-Blackwell}, title = {{Variation of the folding and dynamics of the Escherichia coli chromosome with growth conditions}}, doi = {10.1111/mmi.12071}, volume = {86}, year = {2012}, } @article{2945, abstract = {In search of foreign antigens, lymphocytes recirculate from the blood, through lymph nodes, into lymphatics and back to the blood. Dendritic cells also migrate to lymph nodes for optimal interaction with lymphocytes. This continuous trafficking of immune cells into and out of lymph nodes is essential for immune surveillance of foreign invaders. In this article, we review our current understanding of the functions of high endothelial venules (HEVs), stroma and lymphatics in the entry, positioning and exit of immune cells in lymph nodes during homeostasis, and we highlight the unexpected role of dendritic cells in the control of lymphocyte homing through HEVs.}, author = {Girard, Jean and Moussion, Christine and Förster, Reinhold}, journal = {Nature Reviews Immunology}, number = {11}, pages = {762 -- 773}, publisher = {Nature Publishing Group}, title = {{HEVs, lymphatics and homeostatic immune cell trafficking in lymph nodes}}, doi = {10.1038/nri3298}, volume = {12}, year = {2012}, } @article{2946, abstract = {MicroRNAs (miRNAs) are small noncoding RNAs that function in literally all cellular processes. miRNAs interact with Argonaute (Ago) proteins and guide them to specific target sites located in the 3′-untranslated region (3′-UTR) of target mRNAs leading to translational repression and deadenylation-induced mRNA degradation. Most miRNAs are processed from hairpin-structured precursors by the consecutive action of the RNase III enzymes Drosha and Dicer. However, processing of miR-451 is Dicer independent and cleavage is mediated by the endonuclease Ago2. Here we have characterized miR-451 sequence and structure requirements for processing as well as sorting of miRNAs into different Ago proteins. Pre-miR-451 appears to be optimized for Ago2 cleavage and changes result in reduced processing. In addition, we show that the mature miR-451 only associates with Ago2 suggesting that mature miRNAs are not exchanged between different members of the Ago protein family. Based on cloning and deep sequencing of endogenous miRNAs associated with Ago1-3, we do not find evidence for miRNA sorting in human cells. However, Ago identity appears to influence the length of some miRNAs, while others remain unaffected.}, author = {Dueck, Anne and Ziegler, Christian and Eichner, Alexander and Berezikov, Eugène and Meister, Gunter}, journal = {Nucleic Acids Research}, number = {19}, pages = {9850 -- 9862}, publisher = {Oxford University Press}, title = {{MicroRNAs associated with the different human Argonaute proteins}}, doi = {10.1093/nar/gks705}, volume = {40}, year = {2012}, } @inproceedings{2947, abstract = {We introduce games with probabilistic uncertainty, a model for controller synthesis in which the controller observes the state through imprecise sensors that provide correct information about the current state with a fixed probability. That is, in each step, the sensors return an observed state, and given the observed state, there is a probability distribution (due to the estimation error) over the actual current state. The controller must base its decision on the observed state (rather than the actual current state, which it does not know). On the other hand, we assume that the environment can perfectly observe the current state. We show that controller synthesis for qualitative ω-regular objectives in our model can be reduced in polynomial time to standard partial-observation stochastic games, and vice-versa. As a consequence we establish the precise decidability frontier for the new class of games, and establish optimal complexity results for all the decidable problems.}, author = {Chatterjee, Krishnendu and Chmelik, Martin and Majumdar, Ritankar}, location = {Thiruvananthapuram, India}, pages = {385 -- 399}, publisher = {Springer}, title = {{Equivalence of games with probabilistic uncertainty and partial observation games}}, doi = {10.1007/978-3-642-33386-6_30}, volume = {7561}, year = {2012}, } @article{2949, author = {Dupret, David and Csicsvari, Jozsef L}, journal = {Nature Neuroscience}, number = {11}, pages = {1471 -- 1472}, publisher = {Nature Publishing Group}, title = {{The medial entorhinal cortex keeps Up}}, doi = {10.1038/nn.3245}, volume = {15}, year = {2012}, } @article{2950, abstract = {Contractile actomyosin rings drive various fundamental morphogenetic processes ranging from cytokinesis to wound healing. Actomyosin rings are generally thought to function by circumferential contraction. Here, we show that the spreading of the enveloping cell layer (EVL) over the yolk cell during zebrafish gastrulation is driven by a contractile actomyosin ring. In contrast to previous suggestions, we find that this ring functions not only by circumferential contraction but also by a flow-friction mechanism. This generates a pulling force through resistance against retrograde actomyosin flow. EVL spreading proceeds normally in situations where circumferential contraction is unproductive, indicating that the flow-friction mechanism is sufficient. Thus, actomyosin rings can function in epithelial morphogenesis through a combination of cable-constriction and flow-friction mechanisms.}, author = {Behrndt, Martin and Salbreux, Guillaume and Campinho, Pedro and Hauschild, Robert and Oswald, Felix and Roensch, Julia and Grill, Stephan and Heisenberg, Carl-Philipp J}, journal = {Science}, number = {6104}, pages = {257 -- 260}, publisher = {American Association for the Advancement of Science}, title = {{Forces driving epithelial spreading in zebrafish gastrulation}}, doi = {10.1126/science.1224143}, volume = {338}, year = {2012}, } @article{2951, abstract = {Differential cell adhesion and cortex tension are thought to drive cell sorting by controlling cell-cell contact formation. Here, we show that cell adhesion and cortex tension have different mechanical functions in controlling progenitor cell-cell contact formation and sorting during zebrafish gastrulation. Cortex tension controls cell-cell contact expansion by modulating interfacial tension at the contact. By contrast, adhesion has little direct function in contact expansion, but instead is needed to mechanically couple the cortices of adhering cells at their contacts, allowing cortex tension to control contact expansion. The coupling function of adhesion is mediated by E-cadherin and limited by the mechanical anchoring of E-cadherin to the cortex. Thus, cell adhesion provides the mechanical scaffold for cell cortex tension to drive cell sorting during gastrulation.}, author = {Maître, Jean-Léon and Berthoumieux, Hélène and Krens, Gabriel and Salbreux, Guillaume and Julicher, Frank and Paluch, Ewa and Heisenberg, Carl-Philipp J}, journal = {Science}, number = {6104}, pages = {253 -- 256}, publisher = {American Association for the Advancement of Science}, title = {{Adhesion functions in cell sorting by mechanically coupling the cortices of adhering cells}}, doi = {10.1126/science.1225399}, volume = {338}, year = {2012}, } @article{2952, abstract = {Body axis elongation represents a common and fundamental morphogenetic process in development. A key mechanism triggering body axis elongation without additional growth is convergent extension (CE), whereby a tissue undergoes simultaneous narrowing and extension. Both collective cell migration and cell intercalation are thought to drive CE and are used to different degrees in various species as they elongate their body axis. Here, we provide an overview of CE as a general strategy for body axis elongation and discuss conserved and divergent mechanisms underlying CE among different species.}, author = {Tada, Masazumi and Heisenberg, Carl-Philipp J}, journal = {Development}, number = {21}, pages = {3897 -- 3904}, publisher = {Company of Biologists}, title = {{Convergent extension Using collective cell migration and cell intercalation to shape embryos}}, doi = {10.1242/dev.073007}, volume = {139}, year = {2012}, } @article{2953, author = {Heisenberg, Carl-Philipp J and Fässler, Reinhard}, journal = {Current Opinion in Cell Biology}, number = {5}, pages = {559 -- 561}, publisher = {Elsevier}, title = {{Cell-cell adhesion and extracellular matrix diversity counts}}, doi = {10.1016/j.ceb.2012.09.002}, volume = {24}, year = {2012}, } @article{2954, abstract = {Spontaneous postsynaptic currents (PSCs) provide key information about the mechanisms of synaptic transmission and the activity modes of neuronal networks. However, detecting spontaneous PSCs in vitro and in vivo has been challenging, because of the small amplitude, the variable kinetics, and the undefined time of generation of these events. Here, we describe a, to our knowledge, new method for detecting spontaneous synaptic events by deconvolution, using a template that approximates the average time course of spontaneous PSCs. A recorded PSC trace is deconvolved from the template, resulting in a series of delta-like functions. The maxima of these delta-like events are reliably detected, revealing the precise onset times of the spontaneous PSCs. Among all detection methods, the deconvolution-based method has a unique temporal resolution, allowing the detection of individual events in high-frequency bursts. Furthermore, the deconvolution-based method has a high amplitude resolution, because deconvolution can substantially increase the signal/noise ratio. When tested against previously published methods using experimental data, the deconvolution-based method was superior for spontaneous PSCs recorded in vivo. Using the high-resolution deconvolution-based detection algorithm, we show that the frequency of spontaneous excitatory postsynaptic currents in dentate gyrus granule cells is 4.5 times higher in vivo than in vitro.}, author = {Pernia-Andrade, Alejandro and Goswami, Sarit and Stickler, Yvonne and Fröbe, Ulrich and Schlögl, Alois and Jonas, Peter M}, journal = {Biophysical Journal}, number = {7}, pages = {1429 -- 1439}, publisher = {Biophysical}, title = {{A deconvolution based method with high sensitivity and temporal resolution for detection of spontaneous synaptic currents in vitro and in vivo}}, doi = {10.1016/j.bpj.2012.08.039}, volume = {103}, year = {2012}, } @inproceedings{2955, abstract = {We consider two-player stochastic games played on finite graphs with reachability objectives where the first player tries to ensure a target state to be visited almost-surely (i.e., with probability 1), or positively (i.e., with positive probability), no matter the strategy of the second player. We classify such games according to the information and the power of randomization available to the players. On the basis of information, the game can be one-sided with either (a) player 1, or (b) player 2 having partial observation (and the other player has perfect observation), or two-sided with (c) both players having partial observation. On the basis of randomization, the players (a) may not be allowed to use randomization (pure strategies), or (b) may choose a probability distribution over actions but the actual random choice is external and not visible to the player (actions invisible), or (c) may use full randomization. Our main results for pure strategies are as follows. (1) For one-sided games with player 1 having partial observation we show that (in contrast to full randomized strategies) belief-based (subset-construction based) strategies are not sufficient, and we present an exponential upper bound on memory both for almostsure and positive winning strategies; we show that the problem of deciding the existence of almost-sure and positive winning strategies for player 1 is EXPTIME-complete. (2) For one-sided games with player 2 having partial observation we show that non-elementary memory is both necessary and sufficient for both almost-sure and positive winning strategies. (3) We show that for the general (two-sided) case finite-memory strategies are sufficient for both positive and almost-sure winning, and at least non-elementary memory is required. We establish the equivalence of the almost-sure winning problems for pure strategies and for randomized strategies with actions invisible. Our equivalence result exhibits serious flaws in previous results of the literature: we show a non-elementary memory lower bound for almost-sure winning whereas an exponential upper bound was previously claimed.}, author = {Chatterjee, Krishnendu and Doyen, Laurent}, booktitle = {Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science}, location = {Dubrovnik, Croatia}, publisher = {IEEE}, title = {{Partial-observation stochastic games: How to win when belief fails}}, doi = {10.1109/LICS.2012.28}, year = {2012}, } @inproceedings{2956, abstract = {Two-player games on graphs are central in many problems in formal verification and program analysis such as synthesis and verification of open systems. In this work we consider solving recursive game graphs (or pushdown game graphs) that can model the control flow of sequential programs with recursion. While pushdown games have been studied before with qualitative objectives, such as reachability and parity objectives, in this work we study for the first time such games with the most well-studied quantitative objective, namely, mean payoff objectives. In pushdown games two types of strategies are relevant: (1) global strategies, that depend on the entire global history; and (2) modular strategies, that have only local memory and thus do not depend on the context of invocation, but only on the history of the current invocation of the module. Our main results are as follows: (1) One-player pushdown games with mean-payoff objectives under global strategies are decidable in polynomial time. (2) Two-player pushdown games with mean-payoff objectives under global strategies are undecidable. (3) One-player pushdown games with mean-payoff objectives under modular strategies are NP-hard. (4) Two-player pushdown games with mean-payoff objectives under modular strategies can be solved in NP (i.e., both one-player and two-player pushdown games with mean-payoff objectives under modular strategies are NP-complete). We also establish the optimal strategy complexity showing that global strategies for mean-payoff objectives require infinite memory even in one-player pushdown games; and memoryless modular strategies are sufficient in two-player pushdown games. Finally we also show that all the problems have the same computational complexity if the stack boundedness condition is added, where along with the mean-payoff objective the player must also ensure that the stack height is bounded.}, author = {Chatterjee, Krishnendu and Velner, Yaron}, booktitle = {Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science}, location = {Dubrovnik, Croatia }, publisher = {IEEE}, title = {{Mean payoff pushdown games}}, doi = {10.1109/LICS.2012.30}, year = {2012}, } @inproceedings{2957, abstract = {We consider probabilistic automata on infinite words with acceptance defined by parity conditions. We consider three qualitative decision problems: (i) the positive decision problem asks whether there is a word that is accepted with positive probability; (ii) the almost decision problem asks whether there is a word that is accepted with probability 1; and (iii) the limit decision problem asks whether words are accepted with probability arbitrarily close to 1. We unify and generalize several decidability results for probabilistic automata over infinite words, and identify a robust (closed under union and intersection) subclass of probabilistic automata for which all the qualitative decision problems are decidable for parity conditions. We also show that if the input words are restricted to lasso shape (regular) words, then the positive and almost problems are decidable for all probabilistic automata with parity conditions. For most decidable problems we show an optimal PSPACE-complete complexity bound.}, author = {Chatterjee, Krishnendu and Tracol, Mathieu}, booktitle = {Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science}, location = {Dubrovnik, Croatia }, publisher = {IEEE}, title = {{Decidable problems for probabilistic automata on infinite words}}, doi = {10.1109/LICS.2012.29}, year = {2012}, } @article{2958, abstract = {The activity of hippocampal pyramidal cells reflects both the current position of the animal and information related to its current behavior. Here we investigated whether single hippocampal neurons can encode several independent features defining trials during a memory task. We also tested whether task-related information is represented by partial remapping of the place cell population or, instead, via firing rate modulation of spatially stable place cells. To address these two questions, the activity of hippocampal neurons was recorded in rats performing a conditional discrimination task on a modified T-maze in which the identity of a food reward guided behavior. When the rat was on the central arm of the maze, the firing rate of pyramidal cells changed depending on two independent factors: (1) the identity of the food reward given to the animal and (2) the previous location of the animal on the maze. Importantly, some pyramidal cells encoded information relative to both factors. This trial-type specific and retrospective coding did not interfere with the spatial representation of the maze: hippocampal cells had stable place fields and their theta-phase precession profiles were unaltered during the task, indicating that trial-related information was encoded via rate remapping. During error trials, encoding of both trial-related information and spatial location was impaired. Finally, we found that pyramidal cells also encode trial-related information via rate remapping during the continuous version of the rewarded alternation task without delays. These results suggest that hippocampal neurons can encode several task-related cognitive aspects via rate remapping.}, author = {Allen, Kevin and Rawlins, J Nick and Bannerman, David and Csicsvari, Jozsef L}, journal = {Journal of Neuroscience}, number = {42}, pages = {14752 -- 14766}, publisher = {Society for Neuroscience}, title = {{Hippocampal place cells can encode multiple trial-dependent features through rate remapping}}, doi = {10.1523/JNEUROSCI.6175-11.2012}, volume = {32}, year = {2012}, } @article{2959, abstract = {We study maximum likelihood estimation in Gaussian graphical models from a geometric point of view. An algebraic elimination criterion allows us to find exact lower bounds on the number of observations needed to ensure that the maximum likelihood estimator (MLE) exists with probability one. This is applied to bipartite graphs, grids and colored graphs. We also study the ML degree, and we present the first instance of a graph for which the MLE exists with probability one, even when the number of observations equals the treewidth.}, author = {Uhler, Caroline}, journal = {Annals of Statistics}, number = {1}, pages = {238 -- 261}, publisher = {Institute of Mathematical Statistics}, title = {{Geometry of maximum likelihood estimation in Gaussian graphical models}}, doi = {10.1214/11-AOS957}, volume = {40}, year = {2012}, } @article{2962, abstract = {The choice of summary statistics is a crucial step in approximate Bayesian computation (ABC). Since statistics are often not sufficient, this choice involves a trade-off between loss of information and reduction of dimensionality. The latter may increase the efficiency of ABC. Here, we propose an approach for choosing summary statistics based on boosting, a technique from the machine learning literature. We consider different types of boosting and compare them to partial least squares regression as an alternative. To mitigate the lack of sufficiency, we also propose an approach for choosing summary statistics locally, in the putative neighborhood of the true parameter value. We study a demographic model motivated by the re-introduction of Alpine ibex (Capra ibex) into the Swiss Alps. The parameters of interest are the mean and standard deviation across microsatellites of the scaled ancestral mutation rate (θanc = 4 Ne u), and the proportion of males obtaining access to matings per breeding season (ω). By simulation, we assess the properties of the posterior distribution obtained with the various methods. According to our criteria, ABC with summary statistics chosen locally via boosting with the L2-loss performs best. Applying that method to the ibex data, we estimate θanc ≈ 1.288, and find that most of the variation across loci of the ancestral mutation rate u is between 7.7×10−4 and 3.5×10−3 per locus per generation. The proportion of males with access to matings is estimated to ω ≈ 0.21, which is in good agreement with recent independent estimates.}, author = {Aeschbacher, Simon and Beaumont, Mark and Futschik, Andreas}, journal = {Genetics}, number = {3}, pages = {1027 -- 1047}, publisher = {Genetics Society of America}, title = {{A novel approach for choosing summary statistics in approximate Bayesian computation}}, doi = {10.1534/genetics.112.143164}, volume = {192}, year = {2012}, } @article{2963, abstract = {Zebra finches are an ubiquitous model system for the study of vocal learning in animal communication. Their song has been well described, but its possible function(s) in social communication are only partly understood. The so-called ‘directed song’ is a high-intensity, high-performance song given during courtship in close proximity to the female, which is known to mediate mate choice and mating. However, this singing mode constitutes only a fraction of zebra finch males’ prolific song output. Potential communicative functions of their second, ‘undirected’ singing mode remain unresolved in the face of contradicting reports of both facilitating and inhibiting effects of social company on singing. We addressed this issue by experimentally manipulating social contexts in a within-subject design, comparing a solo versus male or female only company condition, each lasting for 24 hours. Males’ total song output was significantly higher when a conspecific was in audible and visible distance than when they were alone. Male and female company had an equally facilitating effect on song output. Our findings thus indicate that singing motivation is facilitated rather than inhibited by social company, suggesting that singing in zebra finches might function both in inter- and intrasexual communication. }, author = {Jesse, Fabienne and Riebel, Katharina}, journal = {Behavioural Processes}, number = {3}, pages = {262 -- 266}, publisher = {Elsevier}, title = {{Social facilitation of male song by male and female conspecifics in the zebra finch, Taeniopygia guttata}}, doi = {10.1016/j.beproc.2012.09.006}, volume = {91}, year = {2012}, } @phdthesis{2964, abstract = {CA3 pyramidal neurons are important for memory formation and pattern completion in the hippocampal network. These neurons receive multiple excitatory inputs from numerous sources. Therefore, the rules of spatiotemporal integration of multiple synaptic inputs and propagation of action potentials are important to understand how CA3 neurons contribute to higher brain functions at cellular level. By using confocally targeted patch-clamp recording techniques, we investigated the biophysical properties of rat CA3 pyramidal neuron dendrites. We found two distinct dendritic domains critical for action potential initiation and propagation: In the proximal domain, action potentials initiated in the axon backpropagate actively with large amplitude and fast time course. In the distal domain, Na+-channel mediated dendritic spikes are efficiently evoked by local dendritic depolarization or waveforms mimicking synaptic events. These findings can be explained by a high Na+-to-K+ conductance density ratio of CA3 pyramidal neuron dendrites. The results challenge the prevailing view that proximal mossy fiber inputs activate CA3 pyramidal neurons more efficiently than distal perforant inputs by showing that the distal synapses trigger a different form of activity represented by dendritic spikes. The high probability of dendritic spike initiation in the distal area may enhance the computational power of CA3 pyramidal neurons in the hippocampal network. }, author = {Kim, Sooyun}, issn = {2663-337X}, pages = {65}, publisher = {Institute of Science and Technology Austria}, title = {{Active properties of hippocampal CA3 pyramidal neuron dendrites}}, year = {2012}, }