@article{9456, abstract = {The discovery of introns four decades ago was one of the most unexpected findings in molecular biology. Introns are sequences interrupting genes that must be removed as part of messenger RNA production. Genome sequencing projects have shown that most eukaryotic genes contain at least one intron, and frequently many. Comparison of these genomes reveals a history of long evolutionary periods during which few introns were gained, punctuated by episodes of rapid, extensive gain. However, although several detailed mechanisms for such episodic intron generation have been proposed, none has been empirically supported on a genomic scale. Here we show how short, non-autonomous DNA transposons independently generated hundreds to thousands of introns in the prasinophyte Micromonas pusilla and the pelagophyte Aureococcus anophagefferens. Each transposon carries one splice site. The other splice site is co-opted from the gene sequence that is duplicated upon transposon insertion, allowing perfect splicing out of the RNA. The distributions of sequences that can be co-opted are biased with respect to codons, and phasing of transposon-generated introns is similarly biased. These transposons insert between pre-existing nucleosomes, so that multiple nearby insertions generate nucleosome-sized intervening segments. Thus, transposon insertion and sequence co-option may explain the intron phase biases and prevalence of nucleosome-sized exons observed in eukaryotes. Overall, the two independent examples of proliferating elements illustrate a general DNA transposon mechanism that can plausibly account for episodes of rapid, extensive intron gain during eukaryotic evolution.}, author = {Huff, Jason T. and Zilberman, Daniel and Roy, Scott W.}, issn = {1476-4687}, journal = {Nature}, number = {7626}, pages = {533--536}, publisher = {Springer Nature }, title = {{Mechanism for DNA transposons to generate introns on genomic scales}}, doi = {10.1038/nature20110}, volume = {538}, year = {2016}, } @article{9473, abstract = {Cytosine DNA methylation regulates the expression of eukaryotic genes and transposons. Methylation is copied by methyltransferases after DNA replication, which results in faithful transmission of methylation patterns during cell division and, at least in flowering plants, across generations. Transgenerational inheritance is mediated by a small group of cells that includes gametes and their progenitors. However, methylation is usually analyzed in somatic tissues that do not contribute to the next generation, and the mechanisms of transgenerational inheritance are inferred from such studies. To gain a better understanding of how DNA methylation is inherited, we analyzed purified Arabidopsis thaliana sperm and vegetative cells-the cell types that comprise pollen-with mutations in the DRM, CMT2, and CMT3 methyltransferases. We find that DNA methylation dependency on these enzymes is similar in sperm, vegetative cells, and somatic tissues, although DRM activity extends into heterochromatin in vegetative cells, likely reflecting transcription of heterochromatic transposons in this cell type. We also show that lack of histone H1, which elevates heterochromatic DNA methylation in somatic tissues, does not have this effect in pollen. Instead, levels of CG methylation in wild-type sperm and vegetative cells, as well as in wild-type microspores from which both pollen cell types originate, are substantially higher than in wild-type somatic tissues and similar to those of H1-depleted roots. Our results demonstrate that the mechanisms of methylation maintenance are similar between pollen and somatic cells, but the efficiency of CG methylation is higher in pollen, allowing methylation patterns to be accurately inherited across generations.}, author = {Hsieh, Ping-Hung and He, Shengbo and Buttress, Toby and Gao, Hongbo and Couchman, Matthew and Fischer, Robert L. and Zilberman, Daniel and Feng, Xiaoqi}, issn = {1091-6490}, journal = {Proceedings of the National Academy of Sciences}, number = {52}, pages = {15132--15137}, publisher = {National Academy of Sciences}, title = {{Arabidopsis male sexual lineage exhibits more robust maintenance of CG methylation than somatic tissues}}, doi = {10.1073/pnas.1619074114}, volume = {113}, year = {2016}, } @article{9477, abstract = {Cytosine methylation is a DNA modification with important regulatory functions in eukaryotes. In flowering plants, sexual reproduction is accompanied by extensive DNA demethylation, which is required for proper gene expression in the endosperm, a nutritive extraembryonic seed tissue. Endosperm arises from a fusion of a sperm cell carried in the pollen and a female central cell. Endosperm DNA demethylation is observed specifically on the chromosomes inherited from the central cell in Arabidopsis thaliana, rice, and maize, and requires the DEMETER DNA demethylase in Arabidopsis. DEMETER is expressed in the central cell before fertilization, suggesting that endosperm demethylation patterns are inherited from the central cell. Down-regulation of the MET1 DNA methyltransferase has also been proposed to contribute to central cell demethylation. However, with the exception of three maize genes, central cell DNA methylation has not been directly measured, leaving the origin and mechanism of endosperm demethylation uncertain. Here, we report genome-wide analysis of DNA methylation in the central cells of Arabidopsis and rice—species that diverged 150 million years ago—as well as in rice egg cells. We find that DNA demethylation in both species is initiated in central cells, which requires DEMETER in Arabidopsis. However, we do not observe a global reduction of CG methylation that would be indicative of lowered MET1 activity; on the contrary, CG methylation efficiency is elevated in female gametes compared with nonsexual tissues. Our results demonstrate that locus-specific, active DNA demethylation in the central cell is the origin of maternal chromosome hypomethylation in the endosperm.}, author = {Park, Kyunghyuk and Kim, M. Yvonne and Vickers, Martin and Park, Jin-Sup and Hyun, Youbong and Okamoto, Takashi and Zilberman, Daniel and Fischer, Robert L. and Feng, Xiaoqi and Choi, Yeonhee and Scholten, Stefan}, issn = {1091-6490}, journal = {Proceedings of the National Academy of Sciences}, keywords = {Multidisciplinary}, number = {52}, pages = {15138--15143}, publisher = {National Academy of Sciences}, title = {{DNA demethylation is initiated in the central cells of Arabidopsis and rice}}, doi = {10.1073/pnas.1619047114}, volume = {113}, year = {2016}, } @inproceedings{948, abstract = {Experience constantly shapes neural circuits through a variety of plasticity mechanisms. While the functional roles of some plasticity mechanisms are well-understood, it remains unclear how changes in neural excitability contribute to learning. Here, we develop a normative interpretation of intrinsic plasticity (IP) as a key component of unsupervised learning. We introduce a novel generative mixture model that accounts for the class-specific statistics of stimulus intensities, and we derive a neural circuit that learns the input classes and their intensities. We will analytically show that inference and learning for our generative model can be achieved by a neural circuit with intensity-sensitive neurons equipped with a specific form of IP. Numerical experiments verify our analytical derivations and show robust behavior for artificial and natural stimuli. Our results link IP to non-trivial input statistics, in particular the statistics of stimulus intensities for classes to which a neuron is sensitive. More generally, our work paves the way toward new classification algorithms that are robust to intensity variations.}, author = {Monk, Travis and Savin, Cristina and Lücke, Jörg}, location = {Barcelona, Spaine}, pages = {4285 -- 4293}, publisher = {Neural Information Processing Systems Foundation}, title = {{Neurons equipped with intrinsic plasticity learn stimulus intensity statistics}}, volume = {29}, year = {2016}, } @article{9591, abstract = {We give several results showing that different discrete structures typically gain certain spanning substructures (in particular, Hamilton cycles) after a modest random perturbation. First, we prove that adding linearly many random edges to a dense k-uniform hypergraph ensures the (asymptotically almost sure) existence of a perfect matching or a loose Hamilton cycle. The proof involves an interesting application of Szemerédi's Regularity Lemma, which might be independently useful. We next prove that digraphs with certain strong expansion properties are pancyclic, and use this to show that adding a linear number of random edges typically makes a dense digraph pancyclic. Finally, we prove that perturbing a certain (minimum-degree-dependent) number of random edges in a tournament typically ensures the existence of multiple edge-disjoint Hamilton cycles. All our results are tight.}, author = {Krivelevich, Michael and Kwan, Matthew Alan and Sudakov, Benny}, issn = {1469-2163}, journal = {Combinatorics, Probability and Computing}, number = {6}, pages = {909--927}, publisher = {Cambridge University Press}, title = {{Cycles and matchings in randomly perturbed digraphs and hypergraphs}}, doi = {10.1017/s0963548316000079}, volume = {25}, year = {2016}, } @article{9654, abstract = {RNA polymerase I (Pol I) is a highly processive enzyme that transcribes ribosomal DNA (rDNA) and regulates growth of eukaryotic cells. Crystal structures of free Pol I from the yeast Saccharomyces cerevisiae have revealed dimers of the enzyme stabilized by a 'connector' element and an expanded cleft containing the active centre in an inactive conformation. The central bridge helix was unfolded and a Pol-I-specific 'expander' element occupied the DNA-template-binding site. The structure of Pol I in its active transcribing conformation has yet to be determined, whereas structures of Pol II and Pol III have been solved with bound DNA template and RNA transcript. Here we report structures of active transcribing Pol I from yeast solved by two different cryo-electron microscopy approaches. A single-particle structure at 3.8 Å resolution reveals a contracted active centre cleft with bound DNA and RNA, and a narrowed pore beneath the active site that no longer holds the RNA-cleavage-stimulating domain of subunit A12.2. A structure at 29 Å resolution that was determined from cryo-electron tomograms of Pol I enzymes transcribing cellular rDNA confirms contraction of the cleft and reveals that incoming and exiting rDNA enclose an angle of around 150°. The structures suggest a model for the regulation of transcription elongation in which contracted and expanded polymerase conformations are associated with active and inactive states, respectively.}, author = {Neyer, Simon and Kunz, Michael and Geiss, Christian and Hantsche, Merle and Hodirnau, Victor-Valentin and Seybert, Anja and Engel, Christoph and Scheffer, Margot P. and Cramer, Patrick and Frangakis, Achilleas S.}, issn = {1476-4687}, journal = {Nature}, number = {7634}, pages = {607--610}, publisher = {Springer Nature}, title = {{Structure of RNA polymerase I transcribing ribosomal DNA genes}}, doi = {10.1038/nature20561}, volume = {540}, year = {2016}, } @article{9681, abstract = {One of the most prominent consequences of the quantum nature of light atomic nuclei is that their kinetic energy does not follow a Maxwell–Boltzmann distribution. Deep inelastic neutron scattering (DINS) experiments can measure this effect. Thus, the nuclear quantum kinetic energy can be probed directly in both ordered and disordered samples. However, the relation between the quantum kinetic energy and the atomic environment is a very indirect one, and cross-validation with theoretical modeling is therefore urgently needed. Here, we use state of the art path integral molecular dynamics techniques to compute the kinetic energy of hydrogen and oxygen nuclei in liquid, solid, and gas-phase water close to the triple point, comparing three different interatomic potentials and validating our results against equilibrium isotope fractionation measurements. We will then show how accurate simulations can draw a link between extremely precise fractionation experiments and DINS, therefore establishing a reliable benchmark for future measurements and providing key insights to increase further the accuracy of interatomic potentials for water.}, author = {Cheng, Bingqing and Behler, Jörg and Ceriotti, Michele}, issn = {1948-7185}, journal = {The Journal of Physical Chemistry Letters}, number = {12}, pages = {2210--2215}, publisher = {American Chemical Society}, title = {{Nuclear quantum effects in water at the triple point: Using theory as a link between experiments}}, doi = {10.1021/acs.jpclett.6b00729}, volume = {7}, year = {2016}, } @misc{9704, abstract = {Emerging infectious diseases (EIDs) have contributed significantly to the current biodiversity crisis, leading to widespread epidemics and population loss. Owing to genetic variation in pathogen virulence, a complete understanding of species decline requires the accurate identification and characterization of EIDs. We explore this issue in the Western honeybee, where increasing mortality of populations in the Northern Hemisphere has caused major concern. Specifically, we investigate the importance of genetic identity of the main suspect in mortality, deformed wing virus (DWV), in driving honeybee loss. Using laboratory experiments and a systematic field survey, we demonstrate that an emerging DWV genotype (DWV-B) is more virulent than the established DWV genotype (DWV-A) and is widespread in the landscape. Furthermore, we show in a simple model that colonies infected with DWV-B collapse sooner than colonies infected with DWV-A. We also identify potential for rapid DWV evolution by revealing extensive genome-wide recombination in vivo. The emergence of DWV-B in naive honeybee populations, including via recombination with DWV-A, could be of significant ecological and economic importance. Our findings emphasize that knowledge of pathogen genetic identity and diversity is critical to understanding drivers of species decline.}, author = {Mcmahon, Dino and Natsopoulou, Myrsini and Doublet, Vincent and Fürst, Matthias and Weging, Silvio and Brown, Mark and Gogol Döring, Andreas and Paxton, Robert}, publisher = {Dryad}, title = {{Data from: Elevated virulence of an emerging viral genotype as a driver of honeybee loss}}, doi = {10.5061/dryad.cq7t1}, year = {2016}, } @misc{9710, abstract = {Much of quantitative genetics is based on the ‘infinitesimal model’, under which selection has a negligible effect on the genetic variance. This is typically justified by assuming a very large number of loci with additive effects. However, it applies even when genes interact, provided that the number of loci is large enough that selection on each of them is weak relative to random drift. In the long term, directional selection will change allele frequencies, but even then, the effects of epistasis on the ultimate change in trait mean due to selection may be modest. Stabilising selection can maintain many traits close to their optima, even when the underlying alleles are weakly selected. However, the number of traits that can be optimised is apparently limited to ~4Ne by the ‘drift load’, and this is hard to reconcile with the apparent complexity of many organisms. Just as for the mutation load, this limit can be evaded by a particular form of negative epistasis. A more robust limit is set by the variance in reproductive success. This suggests that selection accumulates information most efficiently in the infinitesimal regime, when selection on individual alleles is weak, and comparable with random drift. A review of evidence on selection strength suggests that although most variance in fitness may be because of alleles with large Nes, substantial amounts of adaptation may be because of alleles in the infinitesimal regime, in which epistasis has modest effects.}, author = {Barton, Nicholas H}, publisher = {Dryad}, title = {{Data from: How does epistasis influence the response to selection?}}, doi = {10.5061/dryad.s5s7r}, year = {2016}, } @misc{9720, abstract = {Summary: Declining populations of bee pollinators are a cause of concern, with major repercussions for biodiversity loss and food security. RNA viruses associated with honeybees represent a potential threat to other insect pollinators, but the extent of this threat is poorly understood. This study aims to attain a detailed understanding of the current and ongoing risk of emerging infectious disease (EID) transmission between managed and wild pollinator species across a wide range of RNA viruses. Within a structured large-scale national survey across 26 independent sites, we quantify the prevalence and pathogen loads of multiple RNA viruses in co-occurring managed honeybee (Apis mellifera) and wild bumblebee (Bombus spp.) populations. We then construct models that compare virus prevalence between wild and managed pollinators. Multiple RNA viruses associated with honeybees are widespread in sympatric wild bumblebee populations. Virus prevalence in honeybees is a significant predictor of virus prevalence in bumblebees, but we remain cautious in speculating over the principle direction of pathogen transmission. We demonstrate species-specific differences in prevalence, indicating significant variation in disease susceptibility or tolerance. Pathogen loads within individual bumblebees may be high and in the case of at least one RNA virus, prevalence is higher in wild bumblebees than in managed honeybee populations. Our findings indicate widespread transmission of RNA viruses between managed and wild bee pollinators, pointing to an interconnected network of potential disease pressures within and among pollinator species. In the context of the biodiversity crisis, our study emphasizes the importance of targeting a wide range of pathogens and defining host associations when considering potential drivers of population decline.}, author = {Mcmahon, Dino and Fürst, Matthias and Caspar, Jesicca and Theodorou, Panagiotis and Brown, Mark and Paxton, Robert}, publisher = {Dryad}, title = {{Data from: A sting in the spit: widespread cross-infection of multiple RNA viruses across wild and managed bees}}, doi = {10.5061/dryad.4b565}, year = {2016}, } @article{460, abstract = {NF-κB signaling is a central pathway of immunity and integrates signal transduction upon a wide array of inflammatory stimuli. Noncanonical NF-κB signaling is activated by a small subset of TNF family receptors and characterized by NF-κB2/p52 transcriptional activity. The medical relevance of this pathway has recently re-emerged from the discovery of primary immunodeficiency patients that have loss-of-function mutations in the MAP3K14 gene encoding NIK. Nevertheless, knowledge of protein interactions that regulate noncanonical NF-κB signaling is sparse. Here we report a detailed state-of-the-art mass spectrometry-based protein–protein interaction network including the noncanonical NF-κB signaling nodes TRAF2, TRAF3, IKKα, NIK, and NF-κB2/p100. The value of the data set was confirmed by the identification of interactions already known to regulate this pathway. In addition, a remarkable number of novel interactors were identified. We provide validation of the novel NIK and IKKα interactor FKBP8, which may regulate processes downstream of noncanonical NF-κB signaling. To understand perturbed noncanonical NF-κB signaling in the context of misregulated NIK in disease, we also provide a differential interactome of NIK mutants that cause immunodeficiency. Altogether, this data set not only provides critical insight into how protein–protein interactions can regulate immune signaling but also offers a novel resource on noncanonical NF-κB signaling.}, author = {Willmann, Katharina L and Roberto Sacco and Martins, Rui and Garncarz, Wojciech and Krolo, Ana and Knapp, Sylvia and Bennett, Keiryn L and Boztug, Kaan}, journal = {Journal of Proteome Research}, number = {9}, pages = {2900 -- 2909}, publisher = {American Chemical Society}, title = {{Expanding the interactome of the noncanonical NF-κB signaling pathway}}, doi = {10.1021/acs.jproteome.5b01004}, volume = {15}, year = {2016}, } @inproceedings{478, abstract = {Magic: the Gathering is a game about magical combat for any number of players. Formally it is a zero-sum, imperfect information stochastic game that consists of a potentially unbounded number of steps. We consider the problem of deciding if a move is legal in a given single step of Magic. We show that the problem is (a) coNP-complete in general; and (b) in P if either of two small sets of cards are not used. Our lower bound holds even for single-player Magic games. The significant aspects of our results are as follows: First, in most real-life game problems, the task of deciding whether a given move is legal in a single step is trivial, and the computationally hard task is to find the best sequence of legal moves in the presence of multiple players. In contrast, quite uniquely our hardness result holds for single step and with only one-player. Second, we establish efficient algorithms for important special cases of Magic.}, author = {Chatterjee, Krishnendu and Ibsen-Jensen, Rasmus}, location = {The Hague, Netherlands}, pages = {1432 -- 1439}, publisher = {IOS Press}, title = {{The complexity of deciding legality of a single step of magic: The gathering}}, doi = {10.3233/978-1-61499-672-9-1432}, volume = {285}, year = {2016}, } @inproceedings{479, abstract = {Clinical guidelines and decision support systems (DSS) play an important role in daily practices of medicine. Many text-based guidelines have been encoded for work-flow simulation of DSS to automate health care. During the collaboration with Carle hospital to develop a DSS, we identify that, for some complex and life-critical diseases, it is highly desirable to automatically rigorously verify some complex temporal properties in guidelines, which brings new challenges to current simulation based DSS with limited support of automatical formal verification and real-time data analysis. In this paper, we conduct the first study on applying runtime verification to cooperate with current DSS based on real-time data. Within the proposed technique, a user-friendly domain specific language, named DRTV, is designed to specify vital real-time data sampled by medical devices and temporal properties originated from clinical guidelines. Some interfaces are developed for data acquisition and communication. Then, for medical practice scenarios described in DRTV model, we will automatically generate event sequences and runtime property verifier automata. If a temporal property violates, real-time warnings will be produced by the formal verifier and passed to medical DSS. We have used DRTV to specify different kinds of medical care scenarios, and applied the proposed technique to assist existing DSS. As presented in experiment results, in terms of warning detection, it outperforms the only use of DSS or human inspection, and improves the quality of clinical health care of hospital}, author = {Jiang, Yu and Liu, Han and Kong, Hui and Wang, Rui and Hosseini, Mohamad and Sun, Jiaguang and Sha, Lui}, booktitle = {Proceedings of the 38th International Conference on Software Engineering Companion }, location = {Austin, TX, USA}, pages = {112 -- 121}, publisher = {IEEE}, title = {{Use runtime verification to improve the quality of medical care practice}}, doi = {10.1145/2889160.2889233}, year = {2016}, } @inproceedings{480, abstract = {Graph games provide the foundation for modeling and synthesizing reactive processes. In the synthesis of stochastic reactive processes, the traditional model is perfect-information stochastic games, where some transitions of the game graph are controlled by two adversarial players, and the other transitions are executed probabilistically. We consider such games where the objective is the conjunction of several quantitative objectives (specified as mean-payoff conditions), which we refer to as generalized mean-payoff objectives. The basic decision problem asks for the existence of a finite-memory strategy for a player that ensures the generalized mean-payoff objective be satisfied with a desired probability against all strategies of the opponent. A special case of the decision problem is the almost-sure problem where the desired probability is 1. Previous results presented a semi-decision procedure for -approximations of the almost-sure problem. In this work, we show that both the almost-sure problem as well as the general basic decision problem are coNP-complete, significantly improving the previous results. Moreover, we show that in the case of 1-player stochastic games, randomized memoryless strategies are sufficient and the problem can be solved in polynomial time. In contrast, in two-player stochastic games, we show that even with randomized strategies exponential memory is required in general, and present a matching exponential upper bound. We also study the basic decision problem with infinite-memory strategies and present computational complexity results for the problem. Our results are relevant in the synthesis of stochastic reactive systems with multiple quantitative requirements.}, author = {Chatterjee, Krishnendu and Doyen, Laurent}, location = {New York, NY, USA}, pages = {247 -- 256}, publisher = {IEEE}, title = {{Perfect-information stochastic games with generalized mean-payoff objectives}}, doi = {10.1145/2933575.2934513}, volume = {05-08-July-2016}, year = {2016}, } @inproceedings{482, abstract = {Nonlinear electro-optical conversion of microwave radiation into the optical telecommunication band is achieved within a crystalline whispering gallery mode resonator, reaching 0.1% photon number conversion efficiency with MHz bandwidth.}, author = {Rueda, Alfredo and Sedlmeir, Florian and Collodo, Michele and Vogl, Ulrich and Stiller, Birgit and Schunk, Gerhard and Strekalov, Dmitry and Marquardt, Christoph and Fink, Johannes M and Painter, Oskar and Leuchs, Gerd and Schwefel, Harald}, location = {Sydney, Australia}, publisher = {Optica Publishing Group}, title = {{Nonlinear single sideband microwave to optical conversion using an electro-optic WGM-resonator}}, doi = {10.1364/NP.2016.NTh3A.6}, year = {2016}, } @article{510, abstract = {The CLE (CLAVATA3/Embryo Surrounding Region-related) peptides are small secreted signaling peptides that are primarily involved in the regulation of stem cell homeostasis in different plant meristems. Particularly, the characterization of the CLE41-PXY/TDR signaling pathway has greatly advanced our understanding on the potential roles of CLE peptides in vascular development and wood formation. Nevertheless, our knowledge on this gene family in a tree species is limited. In a recent study, we reported on a systematically investigation of the CLE gene family in Populus trichocarpa . The potential roles of PtCLE genes were studied by comparative analysis and transcriptional pro fi ling. Among fi fty PtCLE members, many PtCLE proteins share identical CLE motifs or contain the same CLE motif as that of AtCLEs, while PtCLE genes exhibited either comparable or distinct expression patterns comparing to their Arabidopsis counterparts. These fi ndings indicate the existence of both functional conservation and functional divergence between PtCLEs and their AtCLE orthologues. Our results provide valuable resources for future functional investigations of these critical signaling molecules in woody plants. }, author = {Liu, Zhijun and Yang, Nan and Lv, Yanting and Pan, Lixia and Lv, Shuo and Han, Huibin and Wang, Guodong}, journal = {Plant Signaling & Behavior}, number = {6}, publisher = {Taylor & Francis}, title = {{The CLE gene family in Populus trichocarpa}}, doi = {10.1080/15592324.2016.1191734}, volume = {11}, year = {2016}, } @article{526, abstract = {Plants form new organs with patterned tissue organization throughout their lifespan. It is unknown whether this robust post-embryonic organ formation results from stereotypic dynamic processes, in which the arrangement of cells follows rigid rules. Here, we combine modeling with empirical observations of whole-organ development to identify the principles governing lateral root formation in Arabidopsis. Lateral roots derive from a small pool of founder cells in which some take a dominant role as seen by lineage tracing. The first division of the founders is asymmetric, tightly regulated, and determines the formation of a layered structure. Whereas the pattern of subsequent cell divisions is not stereotypic between different samples, it is characterized by a regular switch in division plane orientation. This switch is also necessary for the appearance of patterned layers as a result of the apical growth of the primordium. Our data suggest that lateral root morphogenesis is based on a limited set of rules. They determine cell growth and division orientation. The organ-level coupling of the cell behavior ensures the emergence of the lateral root's characteristic features. We propose that self-organizing, non-deterministic modes of development account for the robustness of plant organ morphogenesis.}, author = {Daniel von Wangenheim and Fangerau, Jens and Schmitz, Alexander and Smith, Richard S and Leitte, Heike and Stelzer, Ernst H and Maizel, Alexis}, journal = {Current Biology}, number = {4}, pages = {439 -- 449}, publisher = {Cell Press}, title = {{Rules and self-organizing properties of post-embryonic plant organ cell division patterns}}, doi = {10.1016/j.cub.2015.12.047}, volume = {26}, year = {2016}, } @misc{5445, abstract = {We consider the quantitative analysis problem for interprocedural control-flow graphs (ICFGs). The input consists of an ICFG, a positive weight function that assigns every transition a positive integer-valued number, and a labelling of the transitions (events) as good, bad, and neutral events. The weight function assigns to each transition a numerical value that represents ameasure of how good or bad an event is. The quantitative analysis problem asks whether there is a run of the ICFG where the ratio of the sum of the numerical weights of good events versus the sum of weights of bad events in the long-run is at least a given threshold (or equivalently, to compute the maximal ratio among all valid paths in the ICFG). The quantitative analysis problem for ICFGs can be solved in polynomial time, and we present an efficient and practical algorithm for the problem. We show that several problems relevant for static program analysis, such as estimating the worst-case execution time of a program or the average energy consumption of a mobile application, can be modeled in our framework. We have implemented our algorithm as a tool in the Java Soot framework. We demonstrate the effectiveness of our approach with two case studies. First, we show that our framework provides a sound approach (no false positives) for the analysis of inefficiently-used containers. Second, we show that our approach can also be used for static profiling of programs which reasons about methods that are frequently invoked. Our experimental results show that our tool scales to relatively large benchmarks, and discovers relevant and useful information that can be used to optimize performance of the programs. }, author = {Chatterjee, Krishnendu and Pavlogiannis, Andreas and Velner, Yaron}, issn = {2664-1690}, pages = {33}, publisher = {IST Austria}, title = {{Quantitative interprocedural analysis}}, doi = {10.15479/AT:IST-2016-523-v1-1}, year = {2016}, } @misc{5446, abstract = {We study the problem of developing efficient approaches for proving termination of recursive programs with one-dimensional arrays. Ranking functions serve as a sound and complete approach for proving termination of non-recursive programs without array operations. First, we generalize ranking functions to the notion of measure functions, and prove that measure functions (i) provide a sound method to prove termination of recursive programs (with one-dimensional arrays), and (ii) is both sound and complete over recursive programs without array operations. Our second contribution is the synthesis of measure functions of specific forms in polynomial time. More precisely, we prove that (i) polynomial measure functions over recursive programs can be synthesized in polynomial time through Farkas’ Lemma and Handelman’s Theorem, and (ii) measure functions involving logarithm and exponentiation can be synthesized in polynomial time through abstraction of logarithmic or exponential terms and Handelman’s Theorem. A key application of our method is the worst-case analysis of recursive programs. While previous methods obtain worst-case polynomial bounds of the form O(n^k), where k is an integer, our polynomial time methods can synthesize bounds of the form O(n log n), as well as O(n^x), where x is not an integer. We show the applicability of our automated technique to obtain worst-case complexity of classical recursive algorithms such as (i) Merge-Sort, the divideand- conquer algorithm for the Closest-Pair problem, where we obtain O(n log n) worst-case bound, and (ii) Karatsuba’s algorithm for polynomial multiplication and Strassen’s algorithm for matrix multiplication, where we obtain O(n^x) bound, where x is not an integer and close to the best-known bounds for the respective algorithms. Finally, we present experimental results to demonstrate the effectiveness of our approach.}, author = {Anonymous, 1 and Anonymous, 2 and Anonymous, 3}, issn = {2664-1690}, pages = {26}, publisher = {IST Austria}, title = {{Termination and worst-case analysis of recursive programs}}, year = {2016}, } @misc{5447, abstract = {We consider the problem of developing automated techniques to aid the average-case complexity analysis of programs. Several classical textbook algorithms have quite efficient average-case complexity, whereas the corresponding worst-case bounds are either inefficient (e.g., QUICK-SORT), or completely ineffective (e.g., COUPONCOLLECTOR). Since the main focus of average-case analysis is to obtain efficient bounds, we consider bounds that are either logarithmic, linear, or almost-linear (O(log n), O(n), O(n · log n), respectively, where n represents the size of the input). Our main contribution is a sound approach for deriving such average-case bounds for randomized recursive programs. Our approach is efficient (a simple linear-time algorithm), and it is based on (a) the analysis of recurrence relations induced by randomized algorithms, and (b) a guess-and-check technique. Our approach can infer the asymptotically optimal average-case bounds for classical randomized algorithms, including RANDOMIZED-SEARCH, QUICKSORT, QUICK-SELECT, COUPON-COLLECTOR, where the worstcase bounds are either inefficient (such as linear as compared to logarithmic of average-case, or quadratic as compared to linear or almost-linear of average-case), or ineffective. We have implemented our approach, and the experimental results show that we obtain the bounds efficiently for various classical algorithms.}, author = {Anonymous, 1 and Anonymous, 2 and Anonymous, 3}, issn = {2664-1690}, pages = {20}, publisher = {IST Austria}, title = {{Average-case analysis of programs: Automated recurrence analysis for almost-linear bounds}}, year = {2016}, }