@misc{5423, abstract = {We present a flexible framework for the automated competitive analysis of on-line scheduling algorithms for firm- deadline real-time tasks based on multi-objective graphs: Given a taskset and an on-line scheduling algorithm specified as a labeled transition system, along with some optional safety, liveness, and/or limit-average constraints for the adversary, we automatically compute the competitive ratio of the algorithm w.r.t. a clairvoyant scheduler. We demonstrate the flexibility and power of our approach by comparing the competitive ratio of several on-line algorithms, including D(over), that have been proposed in the past, for various tasksets. Our experimental results reveal that none of these algorithms is universally optimal, in the sense that there are tasksets where other schedulers provide better performance. Our framework is hence a very useful design tool for selecting optimal algorithms for a given application. }, author = {Chatterjee, Krishnendu and Kössler, Alexander and Pavlogiannis, Andreas and Schmid, Ulrich}, issn = {2664-1690}, pages = {14}, publisher = {IST Austria}, title = {{A framework for automated competitive analysis of on-line scheduling of firm-deadline tasks}}, doi = {10.15479/AT:IST-2014-300-v1-1}, year = {2014}, } @misc{5424, abstract = {We consider partially observable Markov decision processes (POMDPs), that are a standard framework for robotics applications to model uncertainties present in the real world, with temporal logic specifications. All temporal logic specifications in linear-time temporal logic (LTL) can be expressed as parity objectives. We study the qualitative analysis problem for POMDPs with parity objectives that asks whether there is a controller (policy) to ensure that the objective holds with probability 1 (almost-surely). While the qualitative analysis of POMDPs with parity objectives is undecidable, recent results show that when restricted to finite-memory policies the problem is EXPTIME-complete. While the problem is intractable in theory, we present a practical approach to solve the qualitative analysis problem. We designed several heuristics to deal with the exponential complexity, and have used our implementation on a number of well-known POMDP examples for robotics applications. Our results provide the first practical approach to solve the qualitative analysis of robot motion planning with LTL properties in the presence of uncertainty.}, author = {Chatterjee, Krishnendu and Chmelik, Martin and Gupta, Raghav and Kanodia, Ayush}, issn = {2664-1690}, pages = {12}, publisher = {IST Austria}, title = {{Qualitative analysis of POMDPs with temporal logic specifications for robotics applications}}, doi = {10.15479/AT:IST-2014-305-v1-1}, year = {2014}, } @misc{5426, abstract = {We consider partially observable Markov decision processes (POMDPs), that are a standard framework for robotics applications to model uncertainties present in the real world, with temporal logic specifications. All temporal logic specifications in linear-time temporal logic (LTL) can be expressed as parity objectives. We study the qualitative analysis problem for POMDPs with parity objectives that asks whether there is a controller (policy) to ensure that the objective holds with probability 1 (almost-surely). While the qualitative analysis of POMDPs with parity objectives is undecidable, recent results show that when restricted to finite-memory policies the problem is EXPTIME-complete. While the problem is intractable in theory, we present a practical approach to solve the qualitative analysis problem. We designed several heuristics to deal with the exponential complexity, and have used our implementation on a number of well-known POMDP examples for robotics applications. Our results provide the first practical approach to solve the qualitative analysis of robot motion planning with LTL properties in the presence of uncertainty.}, author = {Chatterjee, Krishnendu and Chmelik, Martin and Gupta, Raghav and Kanodia, Ayush}, issn = {2664-1690}, pages = {10}, publisher = {IST Austria}, title = {{Qualitative analysis of POMDPs with temporal logic specifications for robotics applications}}, doi = {10.15479/AT:IST-2014-305-v2-1}, year = {2014}, } @misc{5427, abstract = {We consider graphs with n nodes together with their tree-decomposition that has b = O ( n ) bags and width t , on the standard RAM computational model with wordsize W = Θ (log n ) . Our contributions are two-fold: Our first contribution is an algorithm that given a graph and its tree-decomposition as input, computes a binary and balanced tree-decomposition of width at most 4 · t + 3 of the graph in O ( b ) time and space, improving a long-standing (from 1992) bound of O ( n · log n ) time for constant treewidth graphs. Our second contribution is on reachability queries for low treewidth graphs. We build on our tree-balancing algorithm and present a data-structure for graph reachability that requires O ( n · t 2 ) preprocessing time, O ( n · t ) space, and O ( d t/ log n e ) time for pair queries, and O ( n · t · log t/ log n ) time for single-source queries. For constant t our data-structure uses O ( n ) time for preprocessing, O (1) time for pair queries, and O ( n/ log n ) time for single-source queries. This is (asymptotically) optimal and is faster than DFS/BFS when answering more than a constant number of single-source queries.}, author = {Chatterjee, Krishnendu and Ibsen-Jensen, Rasmus and Pavlogiannis, Andreas}, issn = {2664-1690}, pages = {24}, publisher = {IST Austria}, title = {{Optimal tree-decomposition balancing and reachability on low treewidth graphs}}, doi = {10.15479/AT:IST-2014-314-v1-1}, year = {2014}, } @misc{5428, abstract = {Simulation is an attractive alternative for language inclusion for automata as it is an under-approximation of language inclusion, but usually has much lower complexity. For non-deterministic automata, while language inclusion is PSPACE-complete, simulation can be computed in polynomial time. Simulation has also been extended in two orthogonal directions, namely, (1) fair simulation, for simulation over specified set of infinite runs; and (2) quantitative simulation, for simulation between weighted automata. Again, while fair trace inclusion is PSPACE-complete, fair simulation can be computed in polynomial time. For weighted automata, the (quantitative) language inclusion problem is undecidable for mean-payoff automata and the decidability is open for discounted-sum automata, whereas the (quantitative) simulation reduce to mean-payoff games and discounted-sum games, which admit pseudo-polynomial time algorithms. In this work, we study (quantitative) simulation for weighted automata with Büchi acceptance conditions, i.e., we generalize fair simulation from non-weighted automata to weighted automata. We show that imposing Büchi acceptance conditions on weighted automata changes many fundamental properties of the simulation games. For example, whereas for mean-payoff and discounted-sum games, the players do not need memory to play optimally; we show in contrast that for simulation games with Büchi acceptance conditions, (i) for mean-payoff objectives, optimal strategies for both players require infinite memory in general, and (ii) for discounted-sum objectives, optimal strategies need not exist for both players. While the simulation games with Büchi acceptance conditions are more complicated (e.g., due to infinite-memory requirements for mean-payoff objectives) as compared to their counterpart without Büchi acceptance conditions, we still present pseudo-polynomial time algorithms to solve simulation games with Büchi acceptance conditions for both weighted mean-payoff and weighted discounted-sum automata.}, author = {Chatterjee, Krishnendu and Henzinger, Thomas A and Otop, Jan and Velner, Yaron}, issn = {2664-1690}, pages = {26}, publisher = {IST Austria}, title = {{Quantitative fair simulation games}}, doi = {10.15479/AT:IST-2014-315-v1-1}, year = {2014}, } @inbook{6178, abstract = {Mechanically coupled cells can generate forces driving cell and tissue morphogenesis during development. Visualization and measuring of these forces is of major importance to better understand the complexity of the biomechanic processes that shape cells and tissues. Here, we describe how UV laser ablation can be utilized to quantitatively assess mechanical tension in different tissues of the developing zebrafish and in cultures of primary germ layer progenitor cells ex vivo.}, author = {Smutny, Michael and Behrndt, Martin and Campinho, Pedro and Ruprecht, Verena and Heisenberg, Carl-Philipp J}, booktitle = {Tissue Morphogenesis}, editor = {Nelson, Celeste}, isbn = {9781493911639}, issn = {1940-6029}, pages = {219--235}, publisher = {Springer}, title = {{UV laser ablation to measure cell and tissue-generated forces in the zebrafish embryo in vivo and ex vivo}}, doi = {10.1007/978-1-4939-1164-6_15}, volume = {1189}, year = {2014}, } @book{6853, abstract = {This monograph presents a short course in computational geometry and topology. In the first part the book covers Voronoi diagrams and Delaunay triangulations, then it presents the theory of alpha complexes which play a crucial role in biology. The central part of the book is the homology theory and their computation, including the theory of persistence which is indispensable for applications, e.g. shape reconstruction. The target audience comprises researchers and practitioners in mathematics, biology, neuroscience and computer science, but the book may also be beneficial to graduate students of these fields.}, author = {Edelsbrunner, Herbert}, isbn = {9-783-3190-5956-3}, issn = {2191-5318}, pages = {IX, 110}, publisher = {Springer Nature}, title = {{A Short Course in Computational Geometry and Topology}}, doi = {10.1007/978-3-319-05957-0}, year = {2014}, } @inproceedings{10793, abstract = {The Hanani–Tutte theorem is a classical result proved for the first time in the 1930s that characterizes planar graphs as graphs that admit a drawing in the plane in which every pair of edges not sharing a vertex cross an even number of times. We generalize this classical result to clustered graphs with two disjoint clusters, and show that a straightforward extension of our result to flat clustered graphs with three or more disjoint clusters is not possible. We also give a new and short proof for a related result by Di Battista and Frati based on the matroid intersection algorithm.}, author = {Fulek, Radoslav and Kynčl, Jan and Malinović, Igor and Pálvölgyi, Dömötör}, booktitle = {International Symposium on Graph Drawing}, issn = {0302-9743}, pages = {428--436}, publisher = {Springer Nature}, title = {{Clustered planarity testing revisited}}, doi = {10.1007/978-3-662-45803-7_36}, volume = {8871}, year = {2014}, } @book{10811, abstract = {Auxin is an important signaling compound in plants and vital for plant development and growth. The present book, Auxin and its Role in Plant Development, provides the reader with detailed and comprehensive insight into the functioning of the molecule on the whole and specifically in plant development. In the first part, the functioning, metabolism and signaling pathways of auxin in plants are explained, the second part depicts the specific role of auxin in plant development and the third part describes the interaction and functioning of the signaling compound upon stimuli of the environment. Each chapter is written by international experts in the respective field and designed for scientists and researchers in plant biology, plant development and cell biology to summarize the recent progress in understanding the role of auxin and suggest future perspectives for auxin research.}, editor = {Zažímalová, Eva and Petrášek, Jan and Benková, Eva}, isbn = {9783709115251}, pages = {444}, publisher = {Springer Nature}, title = {{Auxin and Its Role in Plant Development}}, doi = {10.1007/978-3-7091-1526-8}, year = {2014}, } @article{10814, abstract = {We review recent progress towards a rigorous understanding of the excitation spectrum of bosonic quantum many-body systems. In particular, we explain how one can rigorously establish the predictions resulting from the Bogoliubov approximation in the mean field limit. The latter predicts that the spectrum is made up of elementary excitations, whose energy behaves linearly in the momentum for small momentum. This property is crucial for the superfluid behavior of the system. We also discuss a list of open problems in this field.}, author = {Seiringer, Robert}, issn = {1869-7135}, journal = {Jahresbericht der Deutschen Mathematiker-Vereinigung}, keywords = {General Medicine}, pages = {21--41}, publisher = {Springer Nature}, title = {{The excitation spectrum for Bose fluids with weak interactions}}, doi = {10.1365/s13291-014-0083-9}, volume = {116}, year = {2014}, } @article{10815, abstract = {In the last several decades, developmental biology has clarified the molecular mechanisms of embryogenesis and organogenesis. In particular, it has demonstrated that the “tool-kit genes” essential for regulating developmental processes are not only highly conserved among species, but are also used as systems at various times and places in an organism to control distinct developmental events. Therefore, mutations in many of these tool-kit genes may cause congenital diseases involving morphological abnormalities. This link between genes and abnormal morphological phenotypes underscores the importance of understanding how cells behave and contribute to morphogenesis as a result of gene function. Recent improvements in live imaging and in quantitative analyses of cellular dynamics will advance our understanding of the cellular pathogenesis of congenital diseases associated with aberrant morphologies. In these studies, it is critical to select an appropriate model organism for the particular phenomenon of interest.}, author = {Hashimoto, Masakazu and Morita, Hitoshi and Ueno, Naoto}, issn = {0914-3505}, journal = {Congenital Anomalies}, keywords = {Developmental Biology, Embryology, General Medicine, Pediatrics, Perinatology, and Child Health}, number = {1}, pages = {1--7}, publisher = {Wiley}, title = {{Molecular and cellular mechanisms of development underlying congenital diseases}}, doi = {10.1111/cga.12039}, volume = {54}, year = {2014}, } @article{9458, abstract = {Dnmt1 epigenetically propagates symmetrical CG methylation in many eukaryotes. Their genomes are typically depleted of CG dinucleotides because of imperfect repair of deaminated methylcytosines. Here, we extensively survey diverse species lacking Dnmt1 and show that, surprisingly, symmetrical CG methylation is nonetheless frequently present and catalyzed by a different DNA methyltransferase family, Dnmt5. Numerous Dnmt5-containing organisms that diverged more than a billion years ago exhibit clustered methylation, specifically in nucleosome linkers. Clustered methylation occurs at unprecedented densities and directly disfavors nucleosomes, contributing to nucleosome positioning between clusters. Dense methylation is enabled by a regime of genomic sequence evolution that enriches CG dinucleotides and drives the highest CG frequencies known. Species with linker methylation have small, transcriptionally active nuclei that approach the physical limits of chromatin compaction. These features constitute a previously unappreciated genome architecture, in which dense methylation influences nucleosome positions, likely facilitating nuclear processes under extreme spatial constraints.}, author = {Huff, Jason T. and Zilberman, Daniel}, issn = {1097-4172}, journal = {Cell}, number = {6}, pages = {1286--1297}, publisher = {Elsevier}, title = {{Dnmt1-independent CG methylation contributes to nucleosome positioning in diverse eukaryotes}}, doi = {10.1016/j.cell.2014.01.029}, volume = {156}, year = {2014}, } @article{9479, abstract = {Centromeres mediate chromosome segregation and are defined by the centromere-specific histone H3 variant (CenH3)/centromere protein A (CENP-A). Removal of CenH3 from centromeres is a general property of terminally differentiated cells, and the persistence of CenH3 increases the risk of diseases such as cancer. However, active mechanisms of centromere disassembly are unknown. Nondividing Arabidopsis pollen vegetative cells, which transport engulfed sperm by extended tip growth, undergo loss of CenH3; centromeric heterochromatin decondensation; and bulk activation of silent rRNA genes, accompanied by their translocation into the nucleolus. Here, we show that these processes are blocked by mutations in the evolutionarily conserved AAA-ATPase molecular chaperone, CDC48A, homologous to yeast Cdc48 and human p97 proteins, both of which are implicated in ubiquitin/small ubiquitin-like modifier (SUMO)-targeted protein degradation. We demonstrate that CDC48A physically associates with its heterodimeric cofactor UFD1-NPL4, known to bind ubiquitin and SUMO, as well as with SUMO1-modified CenH3 and mutations in NPL4 phenocopy cdc48a mutations. In WT vegetative cell nuclei, genetically unlinked ribosomal DNA (rDNA) loci are uniquely clustered together within the nucleolus and all major rRNA gene variants, including those rDNA variants silenced in leaves, are transcribed. In cdc48a mutant vegetative cell nuclei, however, these rDNA loci frequently colocalized with condensed centromeric heterochromatin at the external periphery of the nucleolus. Our results indicate that the CDC48ANPL4 complex actively removes sumoylated CenH3 from centromeres and disrupts centromeric heterochromatin to release bulk rRNA genes into the nucleolus for ribosome production, which fuels single nucleus-driven pollen tube growth and is essential for plant reproduction.}, author = {Mérai, Zsuzsanna and Chumak, Nina and García-Aguilar, Marcelina and Hsieh, Tzung-Fu and Nishimura, Toshiro and Schoft, Vera K. and Bindics, János and Ślusarz, Lucyna and Arnoux, Stéphanie and Opravil, Susanne and Mechtler, Karl and Zilberman, Daniel and Fischer, Robert L. and Tamaru, Hisashi}, issn = {1091-6490}, journal = {Proceedings of the National Academy of Sciences}, number = {45}, pages = {16166--16171}, publisher = {National Academy of Sciences}, title = {{The AAA-ATPase molecular chaperone Cdc48/p97 disassembles sumoylated centromeres, decondenses heterochromatin, and activates ribosomal RNA genes}}, doi = {10.1073/pnas.1418564111}, volume = {111}, year = {2014}, } @article{9519, abstract = {Transposons are selfish genetic sequences that can increase their copy number and inflict substantial damage on their hosts. To combat these genomic parasites, plants have evolved multiple pathways to identify and silence transposons by methylating their DNA. Plants have also evolved mechanisms to limit the collateral damage from the antitransposon machinery. In this review, we examine recent developments that have elucidated many of the molecular workings of these pathways. We also highlight the evidence that the methylation and demethylation pathways interact, indicating that plants have a highly sophisticated, integrated system of transposon defense that has an important role in the regulation of gene expression.}, author = {Kim, M. Yvonne and Zilberman, Daniel}, issn = {1878-4372}, journal = {Trends in Plant Science}, number = {5}, pages = {320--326}, publisher = {Elsevier}, title = {{DNA methylation as a system of plant genomic immunity}}, doi = {10.1016/j.tplants.2014.01.014}, volume = {19}, year = {2014}, } @misc{9722, author = {Lovrics, Anna and Gao, Yu and Juhász, Bianka and Bock, István and Byrne, Helen M. and Dinnyés, András and Kovács, Krisztián}, publisher = {Public Library of Science}, title = {{Transition probability between TF expression states when Dbx2 inhibits Nkx2.2}}, doi = {10.1371/journal.pone.0111430.s006}, year = {2014}, } @misc{9739, author = {Chatterjee, Krishnendu and Pavlogiannis, Andreas and Adlam, Ben and Novak, Martin}, publisher = {Public Library of Science}, title = {{Detailed proofs for “The time scale of evolutionary innovation”}}, doi = {10.1371/journal.pcbi.1003818.s001}, year = {2014}, } @misc{9740, abstract = {The fitness effects of symbionts on their hosts can be context-dependent, with usually benign symbionts causing detrimental effects when their hosts are stressed, or typically parasitic symbionts providing protection towards their hosts (e.g. against pathogen infection). Here, we studied the novel association between the invasive garden ant Lasius neglectus and its fungal ectosymbiont Laboulbenia formicarum for potential costs and benefits. We tested ants with different Laboulbenia levels for their survival and immunity under resource limitation and exposure to the obligate killing entomopathogen Metarhizium brunneum. While survival of L. neglectus workers under starvation was significantly decreased with increasing Laboulbenia levels, host survival under Metarhizium exposure increased with higher levels of the ectosymbiont, suggesting a symbiont-mediated anti-pathogen protection, which seems to be driven mechanistically by both improved sanitary behaviours and an upregulated immune system. Ants with high Laboulbenia levels showed significantly longer self-grooming and elevated expression of immune genes relevant for wound repair and antifungal responses (β-1,3-glucan binding protein, Prophenoloxidase), compared with ants carrying low Laboulbenia levels. This suggests that the ectosymbiont Laboulbenia formicarum weakens its ant host by either direct resource exploitation or the costs of an upregulated behavioural and immunological response, which, however, provides a prophylactic protection upon later exposure to pathogens.}, author = {Konrad, Matthias and Grasse, Anna V and Tragust, Simon and Cremer, Sylvia}, publisher = {Dryad}, title = {{Data from: Anti-pathogen protection versus survival costs mediated by an ectosymbiont in an ant host}}, doi = {10.5061/dryad.vm0vc}, year = {2014}, } @misc{9741, abstract = {In rapidly changing environments, selection history may impact the dynamics of adaptation. Mutations selected in one environment may result in pleiotropic fitness trade-offs in subsequent novel environments, slowing the rates of adaptation. Epistatic interactions between mutations selected in sequential stressful environments may slow or accelerate subsequent rates of adaptation, depending on the nature of that interaction. We explored the dynamics of adaptation during sequential exposure to herbicides with different modes of action in Chlamydomonas reinhardtii. Evolution of resistance to two of the herbicides was largely independent of selection history. For carbetamide, previous adaptation to other herbicide modes of action positively impacted the likelihood of adaptation to this herbicide. Furthermore, while adaptation to all individual herbicides was associated with pleiotropic fitness costs in stress-free environments, we observed that accumulation of resistance mechanisms was accompanied by a reduction in overall fitness costs. We suggest that antagonistic epistasis may be a driving mechanism that enables populations to more readily adapt in novel environments. These findings highlight the potential for sequences of xenobiotics to facilitate the rapid evolution of multiple-drug and -pesticide resistance, as well as the potential for epistatic interactions between adaptive mutations to facilitate evolutionary rescue in rapidly changing environments.}, author = {Lagator, Mato and Colegrave, Nick and Neve, Paul}, publisher = {Dryad}, title = {{Data from: Selection history and epistatic interactions impact dynamics of adaptation to novel environmental stresses}}, doi = {10.5061/dryad.85dn7}, year = {2014}, } @misc{9747, abstract = {Understanding the effects of sex and migration on adaptation to novel environments remains a key problem in evolutionary biology. Using a single-cell alga Chlamydomonas reinhardtii, we investigated how sex and migration affected rates of evolutionary rescue in a sink environment, and subsequent changes in fitness following evolutionary rescue. We show that sex and migration affect both the rate of evolutionary rescue and subsequent adaptation. However, their combined effects change as the populations adapt to a sink habitat. Both sex and migration independently increased rates of evolutionary rescue, but the effect of sex on subsequent fitness improvements, following initial rescue, changed with migration, as sex was beneficial in the absence of migration but constraining adaptation when combined with migration. These results suggest that sex and migration are beneficial during the initial stages of adaptation, but can become detrimental as the population adapts to its environment.}, author = {Lagator, Mato and Morgan, Andrew and Neve, Paul and Colegrave, Nick}, publisher = {Dryad}, title = {{Data from: Role of sex and migration in adaptation to sink environments}}, doi = {10.5061/dryad.s42n1}, year = {2014}, } @misc{9752, abstract = {Redundancies and correlations in the responses of sensory neurons may seem to waste neural resources, but they can also carry cues about structured stimuli and may help the brain to correct for response errors. To investigate the effect of stimulus structure on redundancy in retina, we measured simultaneous responses from populations of retinal ganglion cells presented with natural and artificial stimuli that varied greatly in correlation structure; these stimuli and recordings are publicly available online. Responding to spatio-temporally structured stimuli such as natural movies, pairs of ganglion cells were modestly more correlated than in response to white noise checkerboards, but they were much less correlated than predicted by a non-adapting functional model of retinal response. Meanwhile, responding to stimuli with purely spatial correlations, pairs of ganglion cells showed increased correlations consistent with a static, non-adapting receptive field and nonlinearity. We found that in response to spatio-temporally correlated stimuli, ganglion cells had faster temporal kernels and tended to have stronger surrounds. These properties of individual cells, along with gain changes that opposed changes in effective contrast at the ganglion cell input, largely explained the pattern of pairwise correlations across stimuli where receptive field measurements were possible.}, author = {Simmons, Kristina and Prentice, Jason and Tkačik, Gašper and Homann, Jan and Yee, Heather and Palmer, Stephanie and Nelson, Philip and Balasubramanian, Vijay}, publisher = {Dryad}, title = {{Data from: Transformation of stimulus correlations by the retina}}, doi = {10.5061/dryad.246qg}, year = {2014}, }