TY - JOUR
AB - The BCI competition IV stands in the tradition of prior BCI competitions that aim to provide high quality neuroscientific data for open access to the scientific community. As experienced already in prior competitions not only scientists from the narrow field of BCI compete, but scholars with a broad variety of backgrounds and nationalities. They include high specialists as well as students.The goals of all BCI competitions have always been to challenge with respect to novel paradigms and complex data. We report on the following challenges: (1) asynchronous data, (2) synthetic, (3) multi-class continuous data, (4) sessionto-session transfer, (5) directionally modulated MEG, (6) finger movements recorded by ECoG. As after past competitions, our hope is that winning entries may enhance the analysis methods of future BCIs.
AU - Tangermann, Michael
AU - Müller, Klaus
AU - Aertsen, Ad
AU - Birbaumer, Niels
AU - Braun, Christoph
AU - Brunner, Clemens
AU - Leeb, Robert
AU - Mehring, Carsten
AU - Miller, Kai
AU - Müller Putz, Gernot
AU - Nolte, Guido
AU - Pfurtscheller, Gert
AU - Preissl, Hubert
AU - Schalk, Gerwin
AU - Schlögl, Alois
AU - Vidaurre, Carmen
AU - Waldert, Stephan
AU - Blankertz, Benjamin
ID - 493
JF - Frontiers in Neuroscience
TI - Review of the BCI competition IV
VL - 6
ER -
TY - JOUR
AB - We solve the longstanding open problems of the blow-up involved in the translations, when possible, of a nondeterministic Büchi word automaton (NBW) to a nondeterministic co-Büchi word automaton (NCW) and to a deterministic co-Büchi word automaton (DCW). For the NBW to NCW translation, the currently known upper bound is 2o(nlog n) and the lower bound is 1.5n. We improve the upper bound to n2n and describe a matching lower bound of 2ω(n). For the NBW to DCW translation, the currently known upper bound is 2o(nlog n). We improve it to 2 o(n), which is asymptotically tight. Both of our upper-bound constructions are based on a simple subset construction, do not involve intermediate automata with richer acceptance conditions, and can be implemented symbolically. We continue and solve the open problems of translating nondeterministic Streett, Rabin, Muller, and parity word automata to NCW and to DCW. Going via an intermediate NBW is not optimal and we describe direct, simple, and asymptotically tight constructions, involving a 2o(n) blow-up. The constructions are variants of the subset construction, providing a unified approach for translating all common classes of automata to NCW and DCW. Beyond the theoretical importance of the results, we point to numerous applications of the new constructions. In particular, they imply a simple subset-construction based translation, when possible, of LTL to deterministic Büchi word automata.
AU - Boker, Udi
AU - Kupferman, Orna
ID - 494
IS - 4
JF - ACM Transactions on Computational Logic (TOCL)
TI - Translating to Co-Büchi made tight, unified, and useful
VL - 13
ER -
TY - CONF
AB - An automaton with advice is a finite state automaton which has access to an additional fixed infinite string called an advice tape. We refine the Myhill-Nerode theorem to characterize the languages of finite strings that are accepted by automata with advice. We do the same for tree automata with advice.
AU - Kruckman, Alex
AU - Rubin, Sasha
AU - Sheridan, John
AU - Zax, Ben
ID - 495
T2 - Proceedings GandALF 2012
TI - A Myhill Nerode theorem for automata with advice
VL - 96
ER -
TY - CONF
AB - We study the expressive power of logical interpretations on the class of scattered trees, namely those with countably many infinite branches. Scattered trees can be thought of as the tree analogue of scattered linear orders. Every scattered tree has an ordinal rank that reflects the structure of its infinite branches. We prove, roughly, that trees and orders of large rank cannot be interpreted in scattered trees of small rank. We consider a quite general notion of interpretation: each element of the interpreted structure is represented by a set of tuples of subsets of the interpreting tree. Our trees are countable, not necessarily finitely branching, and may have finitely many unary predicates as labellings. We also show how to replace injective set-interpretations in (not necessarily scattered) trees by 'finitary' set-interpretations.
AU - Rabinovich, Alexander
AU - Rubin, Sasha
ID - 496
TI - Interpretations in trees with countably many branches
ER -
TY - CONF
AB - One central issue in the formal design and analysis of reactive systems is the notion of refinement that asks whether all behaviors of the implementation is allowed by the specification. The local interpretation of behavior leads to the notion of simulation. Alternating transition systems (ATSs) provide a general model for composite reactive systems, and the simulation relation for ATSs is known as alternating simulation. The simulation relation for fair transition systems is called fair simulation. In this work our main contributions are as follows: (1) We present an improved algorithm for fair simulation with Büchi fairness constraints; our algorithm requires O(n 3·m) time as compared to the previous known O(n 6)-time algorithm, where n is the number of states and m is the number of transitions. (2) We present a game based algorithm for alternating simulation that requires O(m2)-time as compared to the previous known O((n·m)2)-time algorithm, where n is the number of states and m is the size of transition relation. (3) We present an iterative algorithm for alternating simulation that matches the time complexity of the game based algorithm, but is more space efficient than the game based algorithm. © Krishnendu Chatterjee, Siddhesh Chaubal, and Pritish Kamath.
AU - Chatterjee, Krishnendu
AU - Chaubal, Siddhesh
AU - Kamath, Pritish
ID - 497
TI - Faster algorithms for alternating refinement relations
VL - 16
ER -
TY - JOUR
AB - Understanding patterns and correlates of local adaptation in heterogeneous landscapes can provide important information in the selection of appropriate seed sources for restoration. We assessed the extent of local adaptation of fitness components in 12 population pairs of the perennial herb Rutidosis leptorrhynchoides (Asteraceae) and examined whether spatial scale (0.7-600 km), environmental distance, quantitative (QST) and neutral (FST) genetic differentiation, and size of the local and foreign populations could predict patterns of adaptive differentiation. Local adaptation varied among populations and fitness components. Including all population pairs, local adaptation was observed for seedling survival, but not for biomass, while foreign genotype advantage was observed for reproduction (number of inflorescences). Among population pairs, local adaptation increased with QST and local population size for biomass. QST was associated with environmental distance, suggesting ecological selection for phenotypic divergence. However, low FST and variation in population structure in small populations demonstrates the interaction of gene flow and drift in constraining local adaptation in R. leptorrhynchoides. Our study indicates that for species in heterogeneous landscapes, collecting seed from large populations from similar environments to candidate sites is likely to provide the most appropriate seed sources for restoration.
AU - Pickup, Melinda
AU - Field, David
AU - Rowell, David
AU - Young, Andrew
ID - 498
IS - 8
JF - Evolutionary Applications
TI - Predicting local adaptation in fragmented plant populations: Implications for restoration genetics
VL - 5
ER -
TY - JOUR
AU - Sixt, Michael K
ID - 506
IS - 3
JF - Journal of Cell Biology
TI - Cell migration: Fibroblasts find a new way to get ahead
VL - 197
ER -
TY - GEN
AB - 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 ω-regular 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 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.
AU - Chatterjee, Krishnendu
AU - Velner, Yaron
ID - 5377
SN - 2664-1690
TI - Mean-payoff pushdown games
ER -
TY - GEN
AB - One central issue in the formal design and analysis of reactive systems is the notion of refinement that asks whether all behaviors of the implementation is allowed by the specification. The local interpretation of behavior leads to the notion of simulation. Alternating transition systems (ATSs) provide a general model for composite reactive systems, and the simulation relation for ATSs is known as alternating simulation. The simulation relation for fair transition systems is called fair simulation. In this work our main contributions are as follows: (1) We present an improved algorithm for fair simulation with Büchi fairness constraints; our algorithm requires O(n3 · m) time as compared to the previous known O(n6)-time algorithm, where n is the number of states and m is the number of transitions. (2) We present a game based algorithm for alternating simulation that requires O(m2)-time as compared to the previous known O((n · m)2)-time algorithm, where n is the number of states and m is the size of transition relation. (3) We present an iterative algorithm for alternating simulation that matches the time complexity of the game based algorithm, but is more space efficient than the game based algorithm.
AU - Chatterjee, Krishnendu
AU - Chaubal, Siddhesh
AU - Kamath, Pritish
ID - 5378
SN - 2664-1690
TI - Faster algorithms for alternating refinement relations
ER -
TY - GEN
AB - We consider the problem of inference in agraphical model with binary variables. While in theory it is arguably preferable to compute marginal probabilities, in practice researchers often use MAP inference due to the availability of efficient discrete optimization algorithms. We bridge the gap between the two approaches by introducing the Discrete Marginals technique in which approximate marginals are obtained by minimizing an objective function with unary and pair-wise terms over a discretized domain. This allows the use of techniques originally devel-oped for MAP-MRF inference and learning. We explore two ways to set up the objective function - by discretizing the Bethe free energy and by learning it from training data. Experimental results show that for certain types of graphs a learned function can out-perform the Bethe approximation. We also establish a link between the Bethe free energy and submodular functions.
AU - Korc, Filip
AU - Kolmogorov, Vladimir
AU - Lampert, Christoph
ID - 5396
SN - 2664-1690
TI - Approximating marginals using discrete energy minimization
ER -
TY - GEN
AB - This document is created as a part of the project “Repository for Research Data on IST Austria”. It summarises the actual state of research data at IST Austria, based on survey results. It supports the choice of appropriate software, which would best fit the requirements of their users, the researchers.
AU - Porsche, Jana
ID - 5398
TI - Actual state of research data @ ISTAustria
ER -
TY - CHAP
AU - Gupta, Ashutosh
ID - 5745
SN - 0302-9743
T2 - Automated Technology for Verification and Analysis
TI - Improved Single Pass Algorithms for Resolution Proof Reduction
VL - 7561
ER -
TY - JOUR
AB - First we note that the best polynomial approximation to vertical bar x vertical bar on the set, which consists of an interval on the positive half-axis and a point on the negative half-axis, can be given by means of the classical Chebyshev polynomials. Then we explore the cases when a solution of the related problem on two intervals can be given in elementary functions.
AU - Pausinger, Florian
ID - 6588
IS - 1
JF - Journal of Mathematical Physics, Analysis, Geometry
SN - 1812-9471
TI - Elementary solutions of the Bernstein problem on two intervals
VL - 8
ER -
TY - CONF
AB - Software model checking, as an undecidable problem, has three possible outcomes: (1) the program satisfies the specification, (2) the program does not satisfy the specification, and (3) the model checker fails. The third outcome usually manifests itself in a space-out, time-out, or one component of the verification tool giving up; in all of these failing cases, significant computation is performed by the verification tool before the failure, but no result is reported. We propose to reformulate the model-checking problem as follows, in order to have the verification tool report a summary of the performed work even in case of failure: given a program and a specification, the model checker returns a condition Ψ - usually a state predicate - such that the program satisfies the specification under the condition Ψ - that is, as long as the program does not leave the states in which Ψ is satisfied. In our experiments, we investigated as one major application of conditional model checking the sequential combination of model checkers with information passing. We give the condition that one model checker produces, as input to a second conditional model checker, such that the verification problem for the second is restricted to the part of the state space that is not covered by the condition, i.e., the second model checker works on the problems that the first model checker could not solve. Our experiments demonstrate that repeated application of conditional model checkers, passing information from one model checker to the next, can significantly improve the verification results and performance, i.e., we can now verify programs that we could not verify before.
AU - Beyer, Dirk
AU - Henzinger, Thomas A
AU - Keremoglu, Mehmet
AU - Wendler, Philipp
ID - 1384
T2 - Proceedings of the ACM SIGSOFT 20th International Symposium on the Foundations of Software Engineering
TI - Conditional model checking: A technique to pass information between verifiers
ER -
TY - JOUR
AB - Hierarchical Timing Language (HTL) is a coordination language for distributed, hard real-time applications. HTL is a hierarchical extension of Giotto and, like its predecessor, based on the logical execution time (LET) paradigm of real-time programming. Giotto is compiled into code for a virtual machine, called the EmbeddedMachine (or E machine). If HTL is targeted to the E machine, then the hierarchicalprogram structure needs to be flattened; the flattening makes separatecompilation difficult, and may result in E machinecode of exponential size. In this paper, we propose a generalization of the E machine, which supports a hierarchicalprogram structure at runtime through real-time trigger mechanisms that are arranged in a tree. We present the generalized E machine, and a modular compiler for HTL that generates code of linear size. The compiler may generate code for any part of a given HTL program separately in any order.
AU - Ghosal, Arkadeb
AU - Iercan, Daniel
AU - Kirsch, Christoph
AU - Henzinger, Thomas A
AU - Sangiovanni Vincentelli, Alberto
ID - 3836
IS - 2
JF - Science of Computer Programming
TI - Separate compilation of hierarchical real-time programs into linear-bounded embedded machine code
VL - 77
ER -
TY - JOUR
AB - We summarize classical and recent results about two-player games played on graphs with ω-regular objectives. These games have applications in the verification and synthesis of reactive systems. Important distinctions are whether a graph game is turn-based or concurrent; deterministic or stochastic; zero-sum or not. We cluster known results and open problems according to these classifications.
AU - Chatterjee, Krishnendu
AU - Henzinger, Thomas A
ID - 3846
IS - 2
JF - Journal of Computer and System Sciences
TI - A survey of stochastic ω regular games
VL - 78
ER -
TY - JOUR
AB - We consider the offset-deconstruction problem: Given a polygonal shape Q with n vertices, can it be expressed, up to a tolerance ε in Hausdorff distance, as the Minkowski sum of another polygonal shape P with a disk of fixed radius? If it does, we also seek a preferably simple-looking solution P; then, P's offset constitutes an accurate, vertex-reduced, and smoothened approximation of Q. We give an O(nlogn)-time exact decision algorithm that handles any polygonal shape, assuming the real-RAM model of computation. A variant of the algorithm, which we have implemented using the cgal library, is based on rational arithmetic and answers the same deconstruction problem up to an uncertainty parameter δ its running time additionally depends on δ. If the input shape is found to be approximable, this algorithm also computes an approximate solution for the problem. It also allows us to solve parameter-optimization problems induced by the offset-deconstruction problem. For convex shapes, the complexity of the exact decision algorithm drops to O(n), which is also the time required to compute a solution P with at most one more vertex than a vertex-minimal one.
AU - Berberich, Eric
AU - Halperin, Dan
AU - Kerber, Michael
AU - Pogalnikova, Roza
ID - 3115
IS - 4
JF - Discrete & Computational Geometry
TI - Deconstructing approximate offsets
VL - 48
ER -
TY - JOUR
AB - We consider the problem of minimizing a function represented as a sum of submodular terms. We assume each term allows an efficient computation of exchange capacities. This holds, for example, for terms depending on a small number of variables, or for certain cardinality-dependent terms. A naive application of submodular minimization algorithms would not exploit the existence of specialized exchange capacity subroutines for individual terms. To overcome this, we cast the problem as a submodular flow (SF) problem in an auxiliary graph in such a way that applying most existing SF algorithms would rely only on these subroutines. We then explore in more detail Iwata's capacity scaling approach for submodular flows (Iwata 1997 [19]). In particular, we show how to improve its complexity in the case when the function contains cardinality-dependent terms.
AU - Kolmogorov, Vladimir
ID - 3117
IS - 15
JF - Discrete Applied Mathematics
TI - Minimizing a sum of submodular functions
VL - 160
ER -
TY - JOUR
AB - We present a method for recovering a temporally coherent, deforming triangle mesh with arbitrarily changing topology from an incoherent sequence of static closed surfaces. We solve this problem using the surface geometry alone, without any prior information like surface templates or velocity fields. Our system combines a proven strategy for triangle mesh improvement, a robust multi-resolution non-rigid registration routine, and a reliable technique for changing surface mesh topology. We also introduce a novel topological constraint enforcement algorithm to ensure that the output and input always have similar topology. We apply our technique to a series of diverse input data from video reconstructions, physics simulations, and artistic morphs. The structured output of our algorithm allows us to efficiently track information like colors and displacement maps, recover velocity information, and solve PDEs on the mesh as a post process.
AU - Bojsen-Hansen, Morten
AU - Li, Hao
AU - Wojtan, Christopher J
ID - 3118
IS - 4
JF - ACM Transactions on Graphics
TI - Tracking surfaces with evolving topology
VL - 31
ER -
TY - CONF
AB - We present an approach for artist-directed animation of liquids using multiple levels of control over the simulation, ranging from the overall tracking of desired shapes to highly detailed secondary effects such as dripping streams, separating sheets of fluid, surface waves and ripples. The first portion of our technique is a volume preserving morph that allows the animator to produce a plausible fluid-like motion from a sparse set of control meshes. By rasterizing the resulting control meshes onto the simulation grid, the mesh velocities act as boundary conditions during the projection step of the fluid simulation. We can then blend this motion together with uncontrolled fluid velocities to achieve a more relaxed control over the fluid that captures natural inertial effects. Our method can produce highly detailed liquid surfaces with control over sub-grid details by using a mesh-based surface tracker on top of a coarse grid-based fluid simulation. We can create ripples and waves on the fluid surface attracting the surface mesh to the control mesh with spring-like forces and also by running a wave simulation over the surface mesh. Our video results demonstrate how our control scheme can be used to create animated characters and shapes that are made of water.
AU - Raveendran, Karthik
AU - Thuerey, Nils
AU - Wojtan, Christopher J
AU - Turk, Greg
ID - 3119
T2 - Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation
TI - Controlling liquids using meshes
ER -
TY - JOUR
AB - We introduce a strategy based on Kustin-Miller unprojection that allows us to construct many hundreds of Gorenstein codimension 4 ideals with 9 × 16 resolutions (that is, nine equations and sixteen first syzygies). Our two basic games are called Tom and Jerry; the main application is the biregular construction of most of the anticanonically polarised Mori Fano 3-folds of Altinok's thesis. There are 115 cases whose numerical data (in effect, the Hilbert series) allow a Type I projection. In every case, at least one Tom and one Jerry construction works, providing at least two deformation families of quasismooth Fano 3-folds having the same numerics but different topology. © 2012 Copyright Foundation Compositio Mathematica.
AU - Brown, Gavin
AU - Kerber, Michael
AU - Reid, Miles
ID - 3120
IS - 4
JF - Compositio Mathematica
TI - Fano 3 folds in codimension 4 Tom and Jerry Part I
VL - 148
ER -
TY - JOUR
AB - Voltage-activated Ca(2+) channels (VACCs) mediate Ca(2+) influx to trigger action potential-evoked neurotransmitter release, but the mechanism by which Ca(2+) regulates spontaneous transmission is unclear. We found that VACCs are the major physiological triggers for spontaneous release at mouse neocortical inhibitory synapses. Moreover, despite the absence of a synchronizing action potential, we found that spontaneous fusion of a GABA-containing vesicle required the activation of multiple tightly coupled VACCs of variable type.
AU - Williams, Courtney
AU - Chen, Wenyan
AU - Lee, Chia
AU - Yaeger, Daniel
AU - Vyleta, Nicholas
AU - Smith, Stephen
ID - 3121
IS - 9
JF - Nature Neuroscience
TI - Coactivation of multiple tightly coupled calcium channels triggers spontaneous release of GABA
VL - 15
ER -
TY - JOUR
AB - Since Darwin's pioneering research on plant reproductive biology (e.g. Darwin 1877), understanding the mechanisms maintaining the diverse sexual strategies of plants has remained an important challenge for evolutionary biologists. In some species, populations are sexually polymorphic and contain two or more mating morphs (sex phenotypes). Differences in morphology or phenology among the morphs influence patterns of non-random mating. In these populations, negative frequency-dependent selection arising from disassortative (intermorph) mating is usually required for the evolutionary maintenance of sexual polymorphism, but few studies have demonstrated the required patterns of non-random mating. In the current issue of Molecular Ecology, Shang (2012) make an important contribution to our understanding of how disassortative mating influences sex phenotype ratios in Acer pictum subsp. mono (painted maple), a heterodichogamous, deciduous tree of eastern China. They monitored sex expression in 97 adults and used paternity analysis of open-pollinated seed to examine disassortative mating among three sex phenotypes. Using a deterministic 'pollen transfer' model, Shang et al. present convincing evidence that differences in the degree of disassortative mating in progeny arrays of the sex phenotypes can explain their uneven frequencies in the adult population. This study provides a useful example of how the deployment of genetic markers, demographic monitoring and modelling can be integrated to investigate the maintenance of sexual diversity in plants.
AU - Field, David
AU - Barrett, Spencer
ID - 3122
IS - 15
JF - Molecular Ecology
TI - Disassortative mating and the maintenance of sexual polymorphism in painted maple
VL - 21
ER -
TY - CONF
AB - We introduce the idea of using an explicit triangle mesh to track the air/fluid interface in a smoothed particle hydrodynamics (SPH) simulator. Once an initial surface mesh is created, this mesh is carried forward in time using nearby particle velocities to advect the mesh vertices. The mesh connectivity remains mostly unchanged across time-steps; it is only modified locally for topology change events or for the improvement of triangle quality. In order to ensure that the surface mesh does not diverge from the underlying particle simulation, we periodically project the mesh surface onto an implicit surface defined by the physics simulation. The mesh surface gives us several advantages over previous SPH surface tracking techniques. We demonstrate a new method for surface tension calculations that clearly outperforms the state of the art in SPH surface tension for computer graphics. We also demonstrate a method for tracking detailed surface information (like colors) that is less susceptible to numerical diffusion than competing techniques. Finally, our temporally-coherent surface mesh allows us to simulate high-resolution surface wave dynamics without being limited by the particle resolution of the SPH simulation.
AU - Yu, Jihun
AU - Wojtan, Christopher J
AU - Turk, Greg
AU - Yap, Chee
ID - 3123
IS - 2
T2 - Computer Graphics Forum
TI - Explicit mesh surfaces for particle based fluids
VL - 31
ER -
TY - CONF
AB - We consider the problem of inference in a graphical model with binary variables. While in theory it is arguably preferable to compute marginal probabilities, in practice researchers often use MAP inference due to the availability of efficient discrete optimization algorithms. We bridge the gap between the two approaches by introducing the Discrete Marginals technique in which approximate marginals are obtained by minimizing an objective function with unary and pairwise terms over a discretized domain. This allows the use of techniques originally developed for MAP-MRF inference and learning. We explore two ways to set up the objective function - by discretizing the Bethe free energy and by learning it from training data. Experimental results show that for certain types of graphs a learned function can outperform the Bethe approximation. We also establish a link between the Bethe free energy and submodular functions.
AU - Korc, Filip
AU - Kolmogorov, Vladimir
AU - Lampert, Christoph
ID - 3124
TI - Approximating marginals using discrete energy minimization
ER -
TY - CONF
AB - We propose a new learning method to infer a mid-level feature representation that combines the advantage of semantic attribute representations with the higher expressive power of non-semantic features. The idea lies in augmenting an existing attribute-based representation with additional dimensions for which an autoencoder model is coupled with a large-margin principle. This construction allows a smooth transition between the zero-shot regime with no training example, the unsupervised regime with training examples but without class labels, and the supervised regime with training examples and with class labels. The resulting optimization problem can be solved efficiently, because several of the necessity steps have closed-form solutions. Through extensive experiments we show that the augmented representation achieves better results in terms of object categorization accuracy than the semantic representation alone.
AU - Sharmanska, Viktoriia
AU - Quadrianto, Novi
AU - Lampert, Christoph
ID - 3125
IS - PART 5
TI - Augmented attribute representations
VL - 7576
ER -
TY - CONF
AB - In this work we propose a new information-theoretic clustering algorithm that infers cluster memberships by direct optimization of a non-parametric mutual information estimate between data distribution and cluster assignment. Although the optimization objective has a solid theoretical foundation it is hard to optimize. We propose an approximate optimization formulation that leads to an efficient algorithm with low runtime complexity. The algorithm has a single free parameter, the number of clusters to find. We demonstrate superior performance on several synthetic and real datasets.
AU - Müller, Andreas
AU - Nowozin, Sebastian
AU - Lampert, Christoph
ID - 3126
TI - Information theoretic clustering using minimal spanning trees
VL - 7476
ER -
TY - CONF
AB - When searching for characteristic subpatterns in potentially noisy graph data, it appears self-evident that having multiple observations would be better than having just one. However, it turns out that the inconsistencies introduced when different graph instances have different edge sets pose a serious challenge. In this work we address this challenge for the problem of finding maximum weighted cliques.
We introduce the concept of most persistent soft-clique. This is subset of vertices, that 1) is almost fully or at least densely connected, 2) occurs in all or almost all graph instances, and 3) has the maximum weight. We present a measure of clique-ness, that essentially counts the number of edge missing to make a subset of vertices into a clique. With this measure, we show that the problem of finding the most persistent soft-clique problem can be cast either as: a) a max-min two person game optimization problem, or b) a min-min soft margin optimization problem. Both formulations lead to the same solution when using a partial Lagrangian method to solve the optimization problems. By experiments on synthetic data and on real social network data, we show that the proposed method is able to reliably find soft cliques in graph data, even if that is distorted by random noise or unreliable observations.
AU - Quadrianto, Novi
AU - Lampert, Christoph
AU - Chen, Chao
ID - 3127
T2 - Proceedings of the 29th International Conference on Machine Learning
TI - The most persistent soft-clique in a set of sampled graphs
ER -
TY - JOUR
AB - We consider two-player zero-sum stochastic games on graphs with ω-regular winning conditions specified as parity objectives. These games have applications in the design and control of reactive systems. We survey the complexity results for the problem of deciding the winner in such games, and in classes of interest obtained as special cases, based on the information and the power of randomization available to the players, on the class of objectives and on the winning mode. On the basis of information, these games can be classified as follows: (a) partial-observation (both players have partial view of the game); (b) one-sided partial-observation (one player has partial-observation and the other player has complete-observation); and (c) complete-observation (both players have complete view of the game). The one-sided partial-observation games have two important subclasses: the one-player games, known as partial-observation Markov decision processes (POMDPs), and the blind one-player games, known as probabilistic automata. On the basis of randomization, (a) the players may not be allowed to use randomization (pure strategies), or (b) they may choose a probability distribution over actions but the actual random choice is external and not visible to the player (actions invisible), or (c) they may use full randomization. Finally, various classes of games are obtained by restricting the parity objective to a reachability, safety, Büchi, or coBüchi condition. We also consider several winning modes, such as sure-winning (i.e., all outcomes of a strategy have to satisfy the winning condition), almost-sure winning (i.e., winning with probability 1), limit-sure winning (i.e., winning with probability arbitrarily close to 1), and value-threshold winning (i.e., winning with probability at least ν, where ν is a given rational).
AU - Chatterjee, Krishnendu
AU - Doyen, Laurent
AU - Henzinger, Thomas A
ID - 3128
IS - 2
JF - Formal Methods in System Design
TI - A survey of partial-observation stochastic parity games
VL - 43
ER -
TY - CONF
AB - Let K be a simplicial complex and g the rank of its p-th homology group Hp(K) defined with ℤ2 coefficients. We show that we can compute a basis H of Hp(K) and annotate each p-simplex of K with a binary vector of length g with the following property: the annotations, summed over all p-simplices in any p-cycle z, provide the coordinate vector of the homology class [z] in the basis H. The basis and the annotations for all simplices can be computed in O(n ω ) time, where n is the size of K and ω < 2.376 is a quantity so that two n×n matrices can be multiplied in O(n ω ) time. The precomputed annotations permit answering queries about the independence or the triviality of p-cycles efficiently.
Using annotations of edges in 2-complexes, we derive better algorithms for computing optimal basis and optimal homologous cycles in 1 - dimensional homology. Specifically, for computing an optimal basis of H1(K) , we improve the previously known time complexity from O(n 4) to O(n ω + n 2 g ω − 1). Here n denotes the size of the 2-skeleton of K and g the rank of H1(K) . Computing an optimal cycle homologous to a given 1-cycle is NP-hard even for surfaces and an algorithm taking 2 O(g) nlogn time is known for surfaces. We extend this algorithm to work with arbitrary 2-complexes in O(n ω ) + 2 O(g) n 2logn time using annotations.
AU - Busaryev, Oleksiy
AU - Cabello, Sergio
AU - Chen, Chao
AU - Dey, Tamal
AU - Wang, Yusu
ID - 3129
TI - Annotating simplices with a homology basis and its applications
VL - 7357
ER -
TY - JOUR
AB - Essential genes code for fundamental cellular functions required for the viability of an organism. For this reason, essential genes are often highly conserved across organisms. However, this is not always the case: orthologues of genes that are essential in one organism are sometimes not essential in other organisms or are absent from their genomes. This suggests that, in the course of evolution, essential genes can be rendered nonessential. How can a gene become non-essential? Here we used genetic manipulation to deplete the products of 26 different essential genes in Escherichia coli. This depletion results in a lethal phenotype, which could often be rescued by the overexpression of a non-homologous, non-essential gene, most likely through replacement of the essential function. We also show that, in a smaller number of cases, the essential genes can be fully deleted from the genome, suggesting that complete functional replacement is possible. Finally, we show that essential genes whose function can be replaced in the laboratory are more likely to be non-essential or not present in other taxa. These results are consistent with the notion that patterns of evolutionary conservation of essential genes are influenced by their compensability-that is, by how easily they can be functionally replaced, for example through increased expression of other genes.
AU - Bergmiller, Tobias
AU - Ackermann, Martin
AU - Silander, Olin
ID - 3130
IS - 6
JF - PLoS Genetics
TI - Patterns of evolutionary conservation of essential genes correlate with their compensability
VL - 8
ER -
TY - JOUR
AB - In large populations, many beneficial mutations may be simultaneously available and may compete with one another, slowing adaptation. By finding the probability of fixation of a favorable allele in a simple model of a haploid sexual population, we find limits to the rate of adaptive substitution, Λ, that depend on simple parameter combinations. When variance in fitness is low and linkage is loose, the baseline rate of substitution is Λ 0=2NU〈s〉 is the population size, U is the rate of beneficial mutations per genome, and 〈s〉 is their mean selective advantage. Heritable variance ν in log fitness due to unlinked loci reduces Λ by e -4ν under polygamy and e -8ν under monogamy. With a linear genetic map of length R Morgans, interference is yet stronger. We use a scaling argument to show that the density of adaptive substitutions depends on s, N, U, and R only through the baseline density: Λ/R=F(Λ 0/R). Under the approximation that the interference due to different sweeps adds up, we show that Λ/R~(Λ 0/R)/(1+2Λ 0/R), implying that interference prevents the rate of adaptive substitution from exceeding one per centimorgan per 200 generations. Simulations and numerical calculations confirm the scaling argument and confirm the additive approximation for Λ 0/R 1; for higher Λ 0/R, the rate of adaptation grows above R/2, but only very slowly. We also consider the effect of sweeps on neutral diversity and show that, while even occasional sweeps can greatly reduce neutral diversity, this effect saturates as sweeps become more common-diversity can be maintained even in populations experiencing very strong interference. Our results indicate that for some organisms the rate of adaptive substitution may be primarily recombination-limited, depending only weakly on the mutation supply and the strength of selection.
AU - Weissman, Daniel
AU - Barton, Nicholas H
ID - 3131
IS - 6
JF - PLoS Genetics
TI - Limits to the rate of adaptive substitution in sexual populations
VL - 8
ER -
TY - JOUR
AB - Reproductive division of labour is a characteristic trait of social insects. The dominant reproductive individual, often the queen, uses chemical communication and/or behaviour to maintain her social status. Queens of many social insects communicate their fertility status via cuticle-bound substances. As these substances usually possess a low volatility, their range in queen–worker communication is potentially limited. Here, we investigate the range and impact of behavioural and chemical queen signals on workers of the ant Temnothorax longispinosus. We compared the behaviour and ovary development of workers subjected to three different treatments: workers with direct chemical and physical contact to the queen, those solely under the influence of volatile queen substances and those entirely separated from the queen. In addition to short-ranged queen signals preventing ovary development in workers, we discovered a novel secondary pathway influencing worker behaviour. Workers with no physical contact to the queen, but exposed to volatile substances, started to develop their ovaries, but did not change their behaviour compared to workers in direct contact to the queen. In contrast, workers in queen-separated groups showed both increased ovary development and aggressive dominance interactions. We conclude that T. longispinosus queens influence worker ovary development and behaviour via two independent signals, both ensuring social harmony within the colony.
AU - Konrad, Matthias
AU - Pamminger, Tobias
AU - Foitzik, Susanne
ID - 3132
IS - 8
JF - Naturwissenschaften
TI - Two pathways ensuring social harmony
VL - 99
ER -
TY - CONF
AB - This note contributes to the point calculus of persistent homology by extending Alexander duality from spaces to real-valued functions. Given a perfect Morse function f: S n+1 →[0, 1 and a decomposition S n+1 = U ∪ V into two (n + 1)-manifolds with common boundary M, we prove elementary relationships between the persistence diagrams of f restricted to U, to V, and to M.
AU - Edelsbrunner, Herbert
AU - Kerber, Michael
ID - 3133
T2 - Proceedings of the twenty-eighth annual symposium on Computational geometry
TI - Alexander duality for functions: The persistent behavior of land and water and shore
ER -
TY - CONF
AB - It has been an open question whether the sum of finitely many isotropic Gaussian kernels in n ≥ 2 dimensions can have more modes than kernels, until in 2003 Carreira-Perpiñán and Williams exhibited n +1 isotropic Gaussian kernels in ℝ n with n + 2 modes. We give a detailed analysis of this example, showing that it has exponentially many critical points and that the resilience of the extra mode grows like √n. In addition, we exhibit finite configurations of isotropic Gaussian kernels with superlinearly many modes.
AU - Edelsbrunner, Herbert
AU - Fasy, Brittany
AU - Rote, Günter
ID - 3134
T2 - Proceedings of the twenty-eighth annual symposium on Computational geometry
TI - Add isotropic Gaussian kernels at own risk: More and more resilient modes in higher dimensions
ER -
TY - CONF
AB - We introduce consumption games, a model for discrete interactive system with multiple resources that are consumed or reloaded independently. More precisely, a consumption game is a finite-state graph where each transition is labeled by a vector of resource updates, where every update is a non-positive number or ω. The ω updates model the reloading of a given resource. Each vertex belongs either to player □ or player ◇, where the aim of player □ is to play so that the resources are never exhausted. We consider several natural algorithmic problems about consumption games, and show that although these problems are computationally hard in general, they are solvable in polynomial time for every fixed number of resource types (i.e., the dimension of the update vectors) and bounded resource updates.
AU - Brázdil, Brázdil
AU - Chatterjee, Krishnendu
AU - Kučera, Antonín
AU - Novotny, Petr
ID - 3135
TI - Efficient controller synthesis for consumption games with multiple resource types
VL - 7358
ER -
TY - CONF
AB - Continuous-time Markov chains (CTMC) with their rich theory and efficient simulation algorithms have been successfully used in modeling stochastic processes in diverse areas such as computer science, physics, and biology. However, systems that comprise non-instantaneous events cannot be accurately and efficiently modeled with CTMCs. In this paper we define delayed CTMCs, an extension of CTMCs that allows for the specification of a lower bound on the time interval between an event's initiation and its completion, and we propose an algorithm for the computation of their behavior. Our algorithm effectively decomposes the computation into two stages: a pure CTMC governs event initiations while a deterministic process guarantees lower bounds on event completion times. Furthermore, from the nature of delayed CTMCs, we obtain a parallelized version of our algorithm. We use our formalism to model genetic regulatory circuits (biological systems where delayed events are common) and report on the results of our numerical algorithm as run on a cluster. We compare performance and accuracy of our results with results obtained by using pure CTMCs. © 2012 Springer-Verlag.
AU - Guet, Calin C
AU - Gupta, Ashutosh
AU - Henzinger, Thomas A
AU - Mateescu, Maria
AU - Sezgin, Ali
ID - 3136
TI - Delayed continuous time Markov chains for genetic regulatory circuits
VL - 7358
ER -
TY - CONF
AB - We propose synchronous interfaces, a new interface theory for discrete-time systems. We use an application to time-triggered scheduling to drive the design choices for our formalism; in particular, additionally to deriving useful mathematical properties, we focus on providing a syntax which is adapted to natural high-level system modeling. As a result, we develop an interface model that relies on a guarded-command based language and is equipped with shared variables and explicit discrete-time clocks. We define all standard interface operations: compatibility checking, composition, refinement, and shared refinement. Apart from the synchronous interface model, the contribution of this paper is the establishment of a formal relation between interface theories and real-time scheduling, where we demonstrate a fully automatic framework for the incremental computation of time-triggered schedules.
AU - Delahaye, Benoît
AU - Fahrenberg, Uli
AU - Henzinger, Thomas A
AU - Legay, Axel
AU - Nickovic, Dejan
ID - 3155
TI - Synchronous interface theories and time triggered scheduling
VL - 7273
ER -
TY - JOUR
AB - Dispersal is crucial for gene flow and often determines the long-term stability of meta-populations, particularly in rare species with specialized life cycles. Such species are often foci of conservation efforts because they suffer disproportionally from degradation and fragmentation of their habitat. However, detailed knowledge of effective gene flow through dispersal is often missing, so that conservation strategies have to be based on mark-recapture observations that are suspected to be poor predictors of long-distance dispersal. These constraints have been especially severe in the study of butterfly populations, where microsatellite markers have been difficult to develop. We used eight microsatellite markers to analyse genetic population structure of the Large Blue butterfly Maculinea arion in Sweden. During recent decades, this species has become an icon of insect conservation after massive decline throughout Europe and extinction in Britain followed by reintroduction of a seed population from the Swedish island of Öland. We find that populations are highly structured genetically, but that gene flow occurs over distances 15 times longer than the maximum distance recorded from mark-recapture studies, which can only be explained by maximum dispersal distances at least twice as large as previously accepted. However, we also find evidence that gaps between sites with suitable habitat exceeding ∼ 20 km induce genetic erosion that can be detected from bottleneck analyses. Although further work is needed, our results suggest that M. arion can maintain fully functional metapopulations when they consist of optimal habitat patches that are no further apart than ∼10 km.
AU - Ugelvig, Line V
AU - Andersen, Anne
AU - Boomsma, Jacobus
AU - Nash, David
ID - 3156
IS - 13
JF - Molecular Ecology
TI - Dispersal and gene flow in the rare parasitic Large Blue butterfly Maculinea arion
VL - 21
ER -
TY - JOUR
AB - Colorectal tumours that are wild type for KRAS are often sensitive to EGFR blockade, but almost always develop resistance within several months of initiating therapy. The mechanisms underlying this acquired resistance to anti-EGFR antibodies are largely unknown. This situation is in marked contrast to that of small-molecule targeted agents, such as inhibitors of ABL, EGFR, BRAF and MEK, in which mutations in the genes encoding the protein targets render the tumours resistant to the effects of the drugs. The simplest hypothesis to account for the development of resistance to EGFR blockade is that rare cells with KRAS mutations pre-exist at low levels in tumours with ostensibly wild-type KRAS genes. Although this hypothesis would seem readily testable, there is no evidence in pre-clinical models to support it, nor is there data from patients. To test this hypothesis, we determined whether mutant KRAS DNA could be detected in the circulation of 28 patients receiving monotherapy with panitumumab, a therapeutic anti-EGFR antibody. We found that 9 out of 24 (38%) patients whose tumours were initially KRAS wild type developed detectable mutations in KRAS in their sera, three of which developed multiple different KRAS mutations. The appearance of these mutations was very consistent, generally occurring between 5 and 6months following treatment. Mathematical modelling indicated that the mutations were present in expanded subclones before the initiation of panitumumab treatment. These results suggest that the emergence of KRAS mutations is a mediator of acquired resistance to EGFR blockade and that these mutations can be detected in a non-invasive manner. They explain why solid tumours develop resistance to targeted therapies in a highly reproducible fashion.
AU - Diaz Jr, Luis
AU - Williams, Richard
AU - Wu, Jian
AU - Kinde, Isaac
AU - Hecht, Joel
AU - Berlin, Jordan
AU - Allen, Benjamin
AU - Božić, Ivana
AU - Reiter, Johannes
AU - Nowak, Martin
AU - Kinzler, Kenneth
AU - Oliner, Kelly
AU - Vogelstein, Bert
ID - 3157
IS - 7404
JF - Nature
TI - The molecular evolution of acquired resistance to targeted EGFR blockade in colorectal cancers
VL - 486
ER -
TY - JOUR
AB - We describe here the development and characterization of a conditionally inducible mouse model expressing Lifeact-GFP, a peptide that reports the dynamics of filamentous actin. We have used this model to study platelets, megakaryocytes and melanoblasts and we provide evidence that Lifeact-GFP is a useful reporter in these cell types ex vivo. In the case of platelets and megakaryocytes, these cells are not transfectable by traditional methods, so conditional activation of Lifeact allows the study of actin dynamics in these cells live. We studied melanoblasts in native skin explants from embryos, allowing the visualization of live actin dynamics during cytokinesis and migration. Our study revealed that melanoblasts lacking the small GTPase Rac1 show a delay in the formation of new pseudopodia following cytokinesis that accounts for the previously reported cytokinesis delay in these cells. Thus, through use of this mouse model, we were able to gain insights into the actin dynamics of cells that could only previously be studied using fixed specimens or following isolation from their native tissue environment.
AU - Schachtner, Hannah
AU - Li, Ang
AU - Stevenson, David
AU - Calaminus, Simon
AU - Thomas, Steven
AU - Watson, Steve
AU - Sixt, Michael K
AU - Wedlich Söldner, Roland
AU - Strathdee, Douglas
AU - Machesky, Laura
ID - 3158
IS - 11-12
JF - European Journal of Cell Biology
TI - Tissue inducible Lifeact expression allows visualization of actin dynamics in vivo and ex vivo
VL - 91
ER -
TY - JOUR
AB - The structure of hierarchical networks in biological and physical systems has long been characterized using the Horton-Strahler ordering scheme. The scheme assigns an integer order to each edge in the network based on the topology of branching such that the order increases from distal parts of the network (e.g., mountain streams or capillaries) to the "root" of the network (e.g., the river outlet or the aorta). However, Horton-Strahler ordering cannot be applied to networks with loops because they they create a contradiction in the edge ordering in terms of which edge precedes another in the hierarchy. Here, we present a generalization of the Horton-Strahler order to weighted planar reticular networks, where weights are assumed to correlate with the importance of network edges, e.g., weights estimated from edge widths may correlate to flow capacity. Our method assigns hierarchical levels not only to edges of the network, but also to its loops, and classifies the edges into reticular edges, which are responsible for loop formation, and tree edges. In addition, we perform a detailed and rigorous theoretical analysis of the sensitivity of the hierarchical levels to weight perturbations. In doing so, we show that the ordering of the reticular edges is more robust to noise in weight estimation than is the ordering of the tree edges. We discuss applications of this generalized Horton-Strahler ordering to the study of leaf venation and other biological networks.
AU - Mileyko, Yuriy
AU - Edelsbrunner, Herbert
AU - Price, Charles
AU - Weitz, Joshua
ID - 3159
IS - 6
JF - PLoS One
TI - Hierarchical ordering of reticular networks
VL - 7
ER -
TY - JOUR
AB - There is a long-running controversy about how early cell fate decisions are made in the developing mammalian embryo. 1,2 In particular, it is controversial when the first events that can predict the establishment of the pluripotent and extra-embryonic lineages in the blastocyst of the pre-implantation embryo occur. It has long been proposed that the position and polarity of cells at the 16- to 32-cell stage embryo influence their decision to either give rise to the pluripotent cell lineage that eventually contributes to the inner cell mass (ICM), comprising the primitive endoderm (PE) and the epiblast (EPI), or the extra-embryonic trophectoderm (TE) surrounding the blastocoel. The positioning of cells in the embryo at this developmental stage could largely be the result of random events, making this a stochastic model of cell lineage allocation. Contrary to such a stochastic model, some studies have detected putative differences in the lineage potential of individual blastomeres before compaction, indicating that the first cell fate decisions may occur as early as at the 4-cell stage. Using a non-invasive, quantitative in vivo imaging assay to study the kinetic behavior of Oct4 (also known as POU5F1), a key transcription factor (TF) controlling pre-implantation development in the mouse embryo, 3-5 a recent study identifies Oct4 kinetics as a predictive measure of cell lineage patterning in the early mouse embryo. 6 Here, we discuss the implications of such molecular heterogeneities in early development and offer potential avenues toward a mechanistic understanding of these observations, contributing to the resolution of the controversy of developmental cell lineage allocation.
AU - Pantazis, Periklis
AU - Bollenbach, Tobias
ID - 3160
IS - 11
JF - Cell Cycle
TI - Transcription factor kinetics and the emerging asymmetry in the early mammalian embryo
VL - 11
ER -
TY - JOUR
AB - Some inflammatory stimuli trigger activation of the NLRP3 inflammasome by inducing efflux of cellular potassium. Loss of cellular potassium is known to potently suppress protein synthesis, leading us to test whether the inhibition of protein synthesis itself serves as an activating signal for the NLRP3 inflammasome. Murine bone marrow-derived macrophages, either primed by LPS or unprimed, were exposed to a panel of inhibitors of ribosomal function: ricin, cycloheximide, puromycin, pactamycin, and anisomycin. Macrophages were also exposed to nigericin, ATP, monosodium urate (MSU), and poly I:C. Synthesis of pro-IL-ß and release of IL-1ß from cells in response to these agents was detected by immunoblotting and ELISA. Release of intracellular potassium was measured by mass spectrometry. Inhibition of translation by each of the tested translation inhibitors led to processing of IL-1ß, which was released from cells. Processing and release of IL-1ß was reduced or absent from cells deficient in NLRP3, ASC, or caspase-1, demonstrating the role of the NLRP3 inflammasome. Despite the inability of these inhibitors to trigger efflux of intracellular potassium, the addition of high extracellular potassium suppressed activation of the NLRP3 inflammasome. MSU and double-stranded RNA, which are known to activate the NLRP3 inflammasome, also substantially inhibited protein translation, supporting a close association between inhibition of translation and inflammasome activation. These data demonstrate that translational inhibition itself constitutes a heretofore-unrecognized mechanism underlying IL-1ß dependent inflammatory signaling and that other physical, chemical, or pathogen-associated agents that impair translation may lead to IL-1ß-dependent inflammation through activation of the NLRP3 inflammasome. For agents that inhibit translation through decreased cellular potassium, the application of high extracellular potassium restores protein translation and suppresses activation of the NLRP inflammasome. For agents that inhibit translation through mechanisms that do not involve loss of potassium, high extracellular potassium suppresses IL-1ß processing through a mechanism that remains undefined.
AU - Vyleta, Meghan
AU - Wong, John
AU - Magun, Bruce
ID - 3161
IS - 5
JF - PLoS One
TI - Suppression of ribosomal function triggers innate immune signaling through activation of the NLRP3 inflammasome
VL - 7
ER -
TY - CONF
AB - Given a dense-time real-valued signal and a parameterized temporal logic formula with both magnitude and timing parameters, we compute the subset of the parameter space that renders the formula satisfied by the trace. We provide two preliminary implementations, one which follows the exact semantics and attempts to compute the validity domain by quantifier elimination in linear arithmetics and one which conducts adaptive search in the parameter space.
AU - Asarin, Eugene
AU - Donzé, Alexandre
AU - Maler, Oded
AU - Nickovic, Dejan
ID - 3162
TI - Parametric identification of temporal properties
VL - 7186
ER -
TY - JOUR
AB - Overview of the Special Issue on structured prediction and inference.
AU - Blaschko, Matthew
AU - Lampert, Christoph
ID - 3164
IS - 3
JF - International Journal of Computer Vision
TI - Guest editorial: Special issue on structured prediction and inference
VL - 99
ER -
TY - CONF
AB - Computing the winning set for Büchi objectives in alternating games on graphs is a central problem in computer aided verification with a large number of applications. The long standing best known upper bound for solving the problem is Õ(n·m), where n is the number of vertices and m is the number of edges in the graph. We are the first to break the Õ(n·m) boundary by presenting a new technique that reduces the running time to O(n 2). This bound also leads to O(n 2) time algorithms for computing the set of almost-sure winning vertices for Büchi objectives (1) in alternating games with probabilistic transitions (improving an earlier bound of Õ(n·m)), (2) in concurrent graph games with constant actions (improving an earlier bound of O(n 3)), and (3) in Markov decision processes (improving for m > n 4/3 an earlier bound of O(min(m 1.5, m·n 2/3)). We also show that the same technique can be used to compute the maximal end-component decomposition of a graph in time O(n 2), which is an improvement over earlier bounds for m > n 4/3. Finally, we show how to maintain the winning set for Büchi objectives in alternating games under a sequence of edge insertions or a sequence of edge deletions in O(n) amortized time per operation. This is the first dynamic algorithm for this problem.
AU - Chatterjee, Krishnendu
AU - Henzinger, Monika
ID - 3165
T2 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
TI - An O(n2) time algorithm for alternating Büchi games
ER -
TY - JOUR
AB - There is evidence that the genetic code was established prior to the existence of proteins, when metabolism was powered by ribozymes. Also, early proto-organisms had to rely on simple anaerobic bioenergetic processes. In this work I propose that amino acid fermentation powered metabolism in the RNA world, and that this was facilitated by proto-adapters, the precursors of the tRNAs. Amino acids were used as carbon sources rather than as catalytic or structural elements. In modern bacteria, amino acid fermentation is known as the Stickland reaction. This pathway involves two amino acids: the first undergoes oxidative deamination, and the second acts as an electron acceptor through reductive deamination. This redox reaction results in two keto acids that are employed to synthesise ATP via substrate-level phosphorylation. The Stickland reaction is the basic bioenergetic pathway of some bacteria of the genus Clostridium. Two other facts support Stickland fermentation in the RNA world. First, several Stickland amino acid pairs are synthesised in abiotic amino acid synthesis. This suggests that amino acids that could be used as an energy substrate were freely available. Second, anticodons that have complementary sequences often correspond to amino acids that form Stickland pairs. The main hypothesis of this paper is that pairs of complementary proto-adapters were assigned to Stickland amino acids pairs. There are signatures of this hypothesis in the genetic code. Furthermore, it is argued that the proto-adapters formed double strands that brought amino acid pairs into proximity to facilitate their mutual redox reaction, structurally constraining the anticodon pairs that are assigned to these amino acid pairs. Significance tests which randomise the code are performed to study the extent of the variability of the energetic (ATP) yield. Random assignments can lead to a substantial yield of ATP and maintain enough variability, thus selection can act and refine the assignments into a proto-code that optimises the energetic yield. Monte Carlo simulations are performed to evaluate the establishment of these simple proto-codes, based on amino acid substitutions and codon swapping. In all cases, donor amino acids are assigned to anticodons composed of U+G, and have low redundancy (1-2 codons), whereas acceptor amino acids are assigned to the the remaining codons. These bioenergetic and structural constraints allow for a metabolic role for amino acids before their co-option as catalyst cofactors. Reviewers: this article was reviewed by Prof. William Martin, Prof. Eors Szathmary (nominated by Dr. Gaspar Jekely) and Dr. Adam Kun (nominated by Dr. Sandor Pongor)
AU - Vladar, Harold
ID - 3166
JF - Biology Direct
TI - Amino acid fermentation at the origin of the genetic code
VL - 7
ER -
TY - JOUR
AU - Weber, Michele
ID - 3167
IS - 6077
JF - Science
TI - NextGen speaks 13
VL - 336
ER -
TY - JOUR
AB - The induction of a signaling pathway is characterized by transient complex formation and mutual posttranslational modification of proteins. To faithfully capture this combinatorial process in a mathematical model is an important challenge in systems biology. Exploiting the limited context on which most binding and modification events are conditioned, attempts have been made to reduce the combinatorial complexity by quotienting the reachable set of molecular species into species aggregates while preserving the deterministic semantics of the thermodynamic limit. Recently, we proposed a quotienting that also preserves the stochastic semantics and that is complete in the sense that the semantics of individual species can be recovered from the aggregate semantics. In this paper, we prove that this quotienting yields a sufficient condition for weak lumpability (that is to say that the quotient system is still Markovian for a given set of initial distributions) and that it gives rise to a backward Markov bisimulation between the original and aggregated transition system (which means that the conditional probability of being in a given state in the original system knowing that we are in its equivalence class is an invariant of the system). We illustrate the framework on a case study of the epidermal growth factor (EGF)/insulin receptor crosstalk.
AU - Feret, Jérôme
AU - Henzinger, Thomas A
AU - Koeppl, Heinz
AU - Petrov, Tatjana
ID - 3168
JF - Theoretical Computer Science
TI - Lumpability abstractions of rule based systems
VL - 431
ER -