TY - CONF AB - Cyber-physical systems (CPS) and the Internet-of-Things (IoT) result in a tremendous amount of generated, measured and recorded time-series data. Extracting temporal segments that encode patterns with useful information out of these huge amounts of data is an extremely difficult problem. We propose shape expressions as a declarative formalism for specifying, querying and extracting sophisticated temporal patterns from possibly noisy data. Shape expressions are regular expressions with arbitrary (linear, exponential, sinusoidal, etc.) shapes with parameters as atomic predicates and additional constraints on these parameters. We equip shape expressions with a novel noisy semantics that combines regular expression matching semantics with statistical regression. We characterize essential properties of the formalism and propose an efficient approximate shape expression matching procedure. We demonstrate the wide applicability of this technique on two case studies. AU - Ničković, Dejan AU - Qin, Xin AU - Ferrere, Thomas AU - Mateis, Cristinel AU - Deshmukh, Jyotirmoy ID - 7159 SN - 0302-9743 T2 - 19th International Conference on Runtime Verification TI - Shape expressions for specifying and extracting signal features VL - 11757 ER - TY - CONF AB - A probabilistic vector addition system with states (pVASS) is a finite state Markov process augmented with non-negative integer counters that can be incremented or decremented during each state transition, blocking any behaviour that would cause a counter to decrease below zero. The pVASS can be used as abstractions of probabilistic programs with many decidable properties. The use of pVASS as abstractions requires the presence of nondeterminism in the model. In this paper, we develop techniques for checking fast termination of pVASS with nondeterminism. That is, for every initial configuration of size n, we consider the worst expected number of transitions needed to reach a configuration with some counter negative (the expected termination time). We show that the problem whether the asymptotic expected termination time is linear is decidable in polynomial time for a certain natural class of pVASS with nondeterminism. Furthermore, we show the following dichotomy: if the asymptotic expected termination time is not linear, then it is at least quadratic, i.e., in Ω(n2). AU - Brázdil, Tomás AU - Chatterjee, Krishnendu AU - Kucera, Antonín AU - Novotný, Petr AU - Velan, Dominik ID - 7183 SN - 03029743 T2 - International Symposium on Automated Technology for Verification and Analysis TI - Deciding fast termination for probabilistic VASS with nondeterminism VL - 11781 ER - TY - JOUR AB - During infection pathogens secrete small molecules, termed effectors, to manipulate and control the interaction with their specific hosts. Both the pathogen and the plant are under high selective pressure to rapidly adapt and co-evolve in what is usually referred to as molecular arms race. Components of the host’s immune system form a network that processes information about molecules with a foreign origin and damage-associated signals, integrating them with developmental and abiotic cues to adapt the plant’s responses. Both in the case of nucleotide-binding leucine-rich repeat receptors and leucine-rich repeat receptor kinases interaction networks have been extensively characterized. However, little is known on whether pathogenic effectors form complexes to overcome plant immunity and promote disease. Ustilago maydis, a biotrophic fungal pathogen that infects maize plants, produces effectors that target hubs in the immune network of the host cell. Here we assess the capability of U. maydis effector candidates to interact with each other, which may play a crucial role during the infection process. Using a systematic yeast-two-hybrid approach and based on a preliminary pooled screen, we selected 63 putative effectors for one-on-one matings with a library of nearly 300 effector candidates. We found that 126 of these effector candidates interacted either with themselves or other predicted effectors. Although the functional relevance of the observed interactions remains elusive, we propose that the observed abundance in complex formation between effectors adds an additional level of complexity to effector research and should be taken into consideration when studying effector evolution and function. Based on this fundamental finding, we suggest various scenarios which could evolutionarily drive the formation and stabilization of an effector interactome. AU - Alcântara, André AU - Bosch, Jason AU - Nazari, Fahimeh AU - Hoffmann, Gesa AU - Gallei, Michelle C AU - Uhse, Simon AU - Darino, Martin A. AU - Olukayode, Toluwase AU - Reumann, Daniel AU - Baggaley, Laura AU - Djamei, Armin ID - 7182 IS - 11 JF - Frontiers in Plant Science TI - Systematic Y2H screening reveals extensive effector-complex formation VL - 10 ER - TY - JOUR AB - Arabidopsis PIN2 protein directs transport of the phytohormone auxin from the root tip into the root elongation zone. Variation in hormone transport, which depends on a delicate interplay between PIN2 sorting to and from polar plasma membrane domains, determines root growth. By employing a constitutively degraded version of PIN2, we identify brassinolides as antagonists of PIN2 endocytosis. This response does not require de novo protein synthesis, but involves early events in canonical brassinolide signaling. Brassinolide-controlled adjustments in PIN2 sorting and intracellular distribution governs formation of a lateral PIN2 gradient in gravistimulated roots, coinciding with adjustments in auxin signaling and directional root growth. Strikingly, simulations indicate that PIN2 gradient formation is no prerequisite for root bending but rather dampens asymmetric auxin flow and signaling. Crosstalk between brassinolide signaling and endocytic PIN2 sorting, thus, appears essential for determining the rate of gravity-induced root curvature via attenuation of differential cell elongation. AU - Retzer, Katarzyna AU - Akhmanova, Maria AU - Konstantinova, Nataliia AU - Malínská, Kateřina AU - Leitner, Johannes AU - Petrášek, Jan AU - Luschnig, Christian ID - 7180 JF - Nature Communications TI - Brassinosteroid signaling delimits root gravitropism via sorting of the Arabidopsis PIN2 auxin transporter VL - 10 ER - TY - JOUR AB - Multiple sequence alignments (MSAs) are used for structural1,2 and evolutionary predictions1,2, but the complexity of aligning large datasets requires the use of approximate solutions3, including the progressive algorithm4. Progressive MSA methods start by aligning the most similar sequences and subsequently incorporate the remaining sequences, from leaf-to-root, based on a guide-tree. Their accuracy declines substantially as the number of sequences is scaled up5. We introduce a regressive algorithm that enables MSA of up to 1.4 million sequences on a standard workstation and substantially improves accuracy on datasets larger than 10,000 sequences. Our regressive algorithm works the other way around to the progressive algorithm and begins by aligning the most dissimilar sequences. It uses an efficient divide-and-conquer strategy to run third-party alignment methods in linear time, regardless of their original complexity. Our approach will enable analyses of extremely large genomic datasets such as the recently announced Earth BioGenome Project, which comprises 1.5 million eukaryotic genomes6. AU - Garriga, Edgar AU - Di Tommaso, Paolo AU - Magis, Cedrik AU - Erb, Ionas AU - Mansouri, Leila AU - Baltzis, Athanasios AU - Laayouni, Hafid AU - Kondrashov, Fyodor AU - Floden, Evan AU - Notredame, Cedric ID - 7181 IS - 12 JF - Nature Biotechnology SN - 10870156 TI - Large multiple sequence alignments with a root-to-leaf regressive method VL - 37 ER -