[{"publication_status":"published","file":[{"date_updated":"2020-07-14T12:45:10Z","file_size":2580778,"creator":"system","date_created":"2018-12-12T10:07:58Z","file_name":"IST-2016-463-v1+1_journal.pgen.1005639.pdf","content_type":"application/pdf","access_level":"open_access","relation":"main_file","checksum":"a4e72fca5ccf40ddacf4d08c8e46b554","file_id":"4657"}],"language":[{"iso":"eng"}],"issue":"11","volume":11,"related_material":{"record":[{"relation":"research_data","status":"public","id":"9712"},{"relation":"dissertation_contains","id":"1131","status":"public"}]},"ec_funded":1,"abstract":[{"lang":"eng","text":"Evolution of gene regulation is crucial for our understanding of the phenotypic differences between species, populations and individuals. Sequence-specific binding of transcription factors to the regulatory regions on the DNA is a key regulatory mechanism that determines gene expression and hence heritable phenotypic variation. We use a biophysical model for directional selection on gene expression to estimate the rates of gain and loss of transcription factor binding sites (TFBS) in finite populations under both point and insertion/deletion mutations. Our results show that these rates are typically slow for a single TFBS in an isolated DNA region, unless the selection is extremely strong. These rates decrease drastically with increasing TFBS length or increasingly specific protein-DNA interactions, making the evolution of sites longer than ∼ 10 bp unlikely on typical eukaryotic speciation timescales. Similarly, evolution converges to the stationary distribution of binding sequences very slowly, making the equilibrium assumption questionable. The availability of longer regulatory sequences in which multiple binding sites can evolve simultaneously, the presence of “pre-sites” or partially decayed old sites in the initial sequence, and biophysical cooperativity between transcription factors, can all facilitate gain of TFBS and reconcile theoretical calculations with timescales inferred from comparative genomics."}],"oa_version":"Published Version","scopus_import":1,"month":"11","intvolume":" 11","date_updated":"2023-09-07T11:53:49Z","ddc":["576"],"department":[{"_id":"NiBa"},{"_id":"CaGu"},{"_id":"GaTk"}],"file_date_updated":"2020-07-14T12:45:10Z","_id":"1666","type":"journal_article","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"status":"public","pubrep_id":"463","has_accepted_license":"1","year":"2015","day":"06","publication":"PLoS Genetics","doi":"10.1371/journal.pgen.1005639","date_published":"2015-11-06T00:00:00Z","date_created":"2018-12-11T11:53:21Z","quality_controlled":"1","publisher":"Public Library of Science","oa":1,"citation":{"chicago":"Tugrul, Murat, Tiago Paixao, Nicholas H Barton, and Gašper Tkačik. “Dynamics of Transcription Factor Binding Site Evolution.” PLoS Genetics. Public Library of Science, 2015. https://doi.org/10.1371/journal.pgen.1005639.","ista":"Tugrul M, Paixao T, Barton NH, Tkačik G. 2015. Dynamics of transcription factor binding site evolution. PLoS Genetics. 11(11).","mla":"Tugrul, Murat, et al. “Dynamics of Transcription Factor Binding Site Evolution.” PLoS Genetics, vol. 11, no. 11, Public Library of Science, 2015, doi:10.1371/journal.pgen.1005639.","ama":"Tugrul M, Paixao T, Barton NH, Tkačik G. Dynamics of transcription factor binding site evolution. PLoS Genetics. 2015;11(11). doi:10.1371/journal.pgen.1005639","apa":"Tugrul, M., Paixao, T., Barton, N. H., & Tkačik, G. (2015). Dynamics of transcription factor binding site evolution. PLoS Genetics. Public Library of Science. https://doi.org/10.1371/journal.pgen.1005639","ieee":"M. Tugrul, T. Paixao, N. H. Barton, and G. Tkačik, “Dynamics of transcription factor binding site evolution,” PLoS Genetics, vol. 11, no. 11. Public Library of Science, 2015.","short":"M. Tugrul, T. Paixao, N.H. Barton, G. Tkačik, PLoS Genetics 11 (2015)."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publist_id":"5483","author":[{"first_name":"Murat","id":"37C323C6-F248-11E8-B48F-1D18A9856A87","full_name":"Tugrul, Murat","orcid":"0000-0002-8523-0758","last_name":"Tugrul"},{"full_name":"Paixao, Tiago","orcid":"0000-0003-2361-3953","last_name":"Paixao","id":"2C5658E6-F248-11E8-B48F-1D18A9856A87","first_name":"Tiago"},{"first_name":"Nicholas H","id":"4880FE40-F248-11E8-B48F-1D18A9856A87","full_name":"Barton, Nicholas H","orcid":"0000-0002-8548-5240","last_name":"Barton"},{"first_name":"Gasper","id":"3D494DCA-F248-11E8-B48F-1D18A9856A87","last_name":"Tkacik","full_name":"Tkacik, Gasper","orcid":"0000-0002-6699-1455"}],"title":"Dynamics of transcription factor binding site evolution","project":[{"call_identifier":"FP7","_id":"25B07788-B435-11E9-9278-68D0E5697425","grant_number":"250152","name":"Limits to selection in biology and in evolutionary computation"}]},{"title":"Complete composition operators for IOCO-testing theory","author":[{"full_name":"Beneš, Nikola","last_name":"Beneš","first_name":"Nikola"},{"first_name":"Przemyslaw","id":"49351290-F248-11E8-B48F-1D18A9856A87","full_name":"Daca, Przemyslaw","last_name":"Daca"},{"last_name":"Henzinger","full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A"},{"last_name":"Kretinsky","full_name":"Kretinsky, Jan","orcid":"0000-0002-8122-2881","id":"44CEF464-F248-11E8-B48F-1D18A9856A87","first_name":"Jan"},{"full_name":"Nickovic, Dejan","last_name":"Nickovic","first_name":"Dejan"}],"publist_id":"5676","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"mla":"Beneš, Nikola, et al. Complete Composition Operators for IOCO-Testing Theory. ACM, 2015, pp. 101–10, doi:10.1145/2737166.2737175.","apa":"Beneš, N., Daca, P., Henzinger, T. A., Kretinsky, J., & Nickovic, D. (2015). Complete composition operators for IOCO-testing theory (pp. 101–110). Presented at the CBSE: Component-Based Software Engineering , Montreal, QC, Canada: ACM. https://doi.org/10.1145/2737166.2737175","ama":"Beneš N, Daca P, Henzinger TA, Kretinsky J, Nickovic D. Complete composition operators for IOCO-testing theory. In: ACM; 2015:101-110. doi:10.1145/2737166.2737175","ieee":"N. Beneš, P. Daca, T. A. Henzinger, J. Kretinsky, and D. Nickovic, “Complete composition operators for IOCO-testing theory,” presented at the CBSE: Component-Based Software Engineering , Montreal, QC, Canada, 2015, pp. 101–110.","short":"N. Beneš, P. Daca, T.A. Henzinger, J. Kretinsky, D. Nickovic, in:, ACM, 2015, pp. 101–110.","chicago":"Beneš, Nikola, Przemyslaw Daca, Thomas A Henzinger, Jan Kretinsky, and Dejan Nickovic. “Complete Composition Operators for IOCO-Testing Theory,” 101–10. ACM, 2015. https://doi.org/10.1145/2737166.2737175.","ista":"Beneš N, Daca P, Henzinger TA, Kretinsky J, Nickovic D. 2015. Complete composition operators for IOCO-testing theory. CBSE: Component-Based Software Engineering , Proceedings of the 18th International ACM SIGSOFT Symposium on Component-Based Software Engineering , , 101–110."},"project":[{"call_identifier":"FP7","_id":"25EE3708-B435-11E9-9278-68D0E5697425","name":"Quantitative Reactive Modeling","grant_number":"267989"},{"call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23"},{"call_identifier":"FWF","_id":"25F42A32-B435-11E9-9278-68D0E5697425","grant_number":"Z211","name":"The Wittgenstein Prize"},{"name":"International IST Postdoc Fellowship Programme","grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"date_published":"2015-05-01T00:00:00Z","doi":"10.1145/2737166.2737175","date_created":"2018-12-11T11:52:24Z","page":"101 - 110","day":"01","has_accepted_license":"1","year":"2015","quality_controlled":"1","publisher":"ACM","oa":1,"acknowledgement":"This research was funded in part by the European Research Council (ERC) under grant agreement 267989 (QUAREM), by the Austrian Science Fund (FWF) projects S11402-N23(RiSE) and Z211-N23 (Wittgestein Award), by People Programme (Marie Curie Actions) of the European Union's Seventh Framework Programme (FP7/2007-2013) under REA grant agreement 291734, and by the ARTEMIS JU under grant agreement 295373 (nSafeCer). Jan Křetínský has been partially supported by the Czech Science Foundation, grant No. P202/12/G061. Nikola Beneš has been supported by the\r\nMEYS project No. CZ.1.07/2.3.00/30.0009 Employment of Newly Graduated Doctors of Science for Scientific Excellence.","department":[{"_id":"ToHe"},{"_id":"KrCh"}],"file_date_updated":"2020-07-14T12:44:59Z","ddc":["000"],"date_updated":"2023-09-07T11:58:33Z","status":"public","pubrep_id":"625","type":"conference","conference":{"start_date":"2015-05-04","location":"Montreal, QC, Canada","end_date":"2015-05-08","name":"CBSE: Component-Based Software Engineering "},"_id":"1502","related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"1155"}]},"ec_funded":1,"file":[{"date_updated":"2020-07-14T12:44:59Z","file_size":467561,"creator":"system","date_created":"2018-12-12T10:17:46Z","file_name":"IST-2016-625-v1+1_conf-cbse-BenesDHKN15.pdf","content_type":"application/pdf","access_level":"open_access","relation":"main_file","file_id":"5303","checksum":"c6ce681035c163a158751f240cb7d389"}],"language":[{"iso":"eng"}],"publication_identifier":{"isbn":["978-1-4503-3471-6"]},"publication_status":"published","month":"05","scopus_import":1,"alternative_title":["Proceedings of the 18th International ACM SIGSOFT Symposium on Component-Based Software Engineering "],"oa_version":"Submitted Version","abstract":[{"text":"We extend the theory of input-output conformance with operators for merge and quotient. The former is useful when testing against multiple requirements or views. The latter can be used to generate tests for patches of an already tested system. Both operators can combine systems with different action alphabets, which is usually the case when constructing complex systems and specifications from parts, for instance different views as well as newly defined functionality of a~previous version of the system.","lang":"eng"}]},{"oa_version":"Preprint","abstract":[{"text":"We consider Markov decision processes (MDPs) which are a standard model for probabilistic systems. We focus on qualitative properties for MDPs that can express that desired behaviors of the system arise almost-surely (with probability 1) or with positive probability. We introduce a new simulation relation to capture the refinement relation of MDPs with respect to qualitative properties, and present discrete graph algorithms with quadratic complexity to compute the simulation relation. We present an automated technique for assume-guarantee style reasoning for compositional analysis of two-player games by giving a counterexample guided abstraction-refinement approach to compute our new simulation relation. We show a tight link between two-player games and MDPs, and as a consequence the results for games are lifted to MDPs with qualitative properties. We have implemented our algorithms and show that the compositional analysis leads to significant improvements. ","lang":"eng"}],"intvolume":" 47","month":"10","main_file_link":[{"url":"https://arxiv.org/abs/1405.0835","open_access":"1"}],"scopus_import":1,"language":[{"iso":"eng"}],"publication_status":"published","ec_funded":1,"issue":"2","related_material":{"record":[{"status":"public","id":"1155","relation":"dissertation_contains"}]},"volume":47,"_id":"1501","status":"public","type":"journal_article","date_updated":"2023-09-07T11:58:33Z","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"acknowledgement":"The research was partly supported by Austrian Science Fund (FWF) Grant No. P23499- N23, FWF NFN Grant No. S11407-N23, FWF Grant S11403-N23 (RiSE), and FWF Grant Z211-N23 (Wittgenstein Award), ERC Start Grant (279307: Graph Games), Microsoft faculty fellows award, the ERC Advanced Grant QUAREM (Quantitative Reactive Modeling).","oa":1,"publisher":"Springer","quality_controlled":"1","publication":"Formal Methods in System Design","day":"01","year":"2015","date_created":"2018-12-11T11:52:23Z","date_published":"2015-10-01T00:00:00Z","doi":"10.1007/s10703-015-0235-2","page":"230 - 264","project":[{"_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"},{"name":"Quantitative Reactive Modeling","grant_number":"267989","call_identifier":"FP7","_id":"25EE3708-B435-11E9-9278-68D0E5697425"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"mla":"Chatterjee, Krishnendu, et al. “CEGAR for Compositional Analysis of Qualitative Properties in Markov Decision Processes.” Formal Methods in System Design, vol. 47, no. 2, Springer, 2015, pp. 230–64, doi:10.1007/s10703-015-0235-2.","ieee":"K. Chatterjee, M. Chmelik, and P. Daca, “CEGAR for compositional analysis of qualitative properties in Markov decision processes,” Formal Methods in System Design, vol. 47, no. 2. Springer, pp. 230–264, 2015.","short":"K. Chatterjee, M. Chmelik, P. Daca, Formal Methods in System Design 47 (2015) 230–264.","apa":"Chatterjee, K., Chmelik, M., & Daca, P. (2015). CEGAR for compositional analysis of qualitative properties in Markov decision processes. Formal Methods in System Design. Springer. https://doi.org/10.1007/s10703-015-0235-2","ama":"Chatterjee K, Chmelik M, Daca P. CEGAR for compositional analysis of qualitative properties in Markov decision processes. Formal Methods in System Design. 2015;47(2):230-264. doi:10.1007/s10703-015-0235-2","chicago":"Chatterjee, Krishnendu, Martin Chmelik, and Przemyslaw Daca. “CEGAR for Compositional Analysis of Qualitative Properties in Markov Decision Processes.” Formal Methods in System Design. Springer, 2015. https://doi.org/10.1007/s10703-015-0235-2.","ista":"Chatterjee K, Chmelik M, Daca P. 2015. CEGAR for compositional analysis of qualitative properties in Markov decision processes. Formal Methods in System Design. 47(2), 230–264."},"title":"CEGAR for compositional analysis of qualitative properties in Markov decision processes","author":[{"last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Chmelik, Martin","last_name":"Chmelik","id":"3624234E-F248-11E8-B48F-1D18A9856A87","first_name":"Martin"},{"full_name":"Daca, Przemyslaw","last_name":"Daca","first_name":"Przemyslaw","id":"49351290-F248-11E8-B48F-1D18A9856A87"}],"publist_id":"5677"},{"publisher":"ACM","quality_controlled":"1","oa":1,"acknowledgement":"We thank anonymous reviewers for helpful comments to improve the presentation of the paper.","doi":"10.1145/2676726.2676979","date_published":"2015-01-01T00:00:00Z","date_created":"2018-12-11T11:52:58Z","page":"97 - 109","day":"01","publication":"ACM SIGPLAN Notices","year":"2015","project":[{"grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"title":"Faster algorithms for algebraic path properties in recursive state machines with constant treewidth","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee"},{"id":"3B699956-F248-11E8-B48F-1D18A9856A87","first_name":"Rasmus","last_name":"Ibsen-Jensen","full_name":"Ibsen-Jensen, Rasmus","orcid":"0000-0003-4783-0389"},{"id":"49704004-F248-11E8-B48F-1D18A9856A87","first_name":"Andreas","last_name":"Pavlogiannis","orcid":"0000-0002-8943-0722","full_name":"Pavlogiannis, Andreas"},{"first_name":"Prateesh","full_name":"Goyal, Prateesh","last_name":"Goyal"}],"publist_id":"5565","external_id":{"arxiv":["1410.7724"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, Andreas Pavlogiannis, and Prateesh Goyal. “Faster Algorithms for Algebraic Path Properties in Recursive State Machines with Constant Treewidth.” ACM SIGPLAN Notices. ACM, 2015. https://doi.org/10.1145/2676726.2676979.","ista":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A, Goyal P. 2015. Faster algorithms for algebraic path properties in recursive state machines with constant treewidth. ACM SIGPLAN Notices. 50(1), 97–109.","mla":"Chatterjee, Krishnendu, et al. “Faster Algorithms for Algebraic Path Properties in Recursive State Machines with Constant Treewidth.” ACM SIGPLAN Notices, vol. 50, no. 1, ACM, 2015, pp. 97–109, doi:10.1145/2676726.2676979.","ama":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A, Goyal P. Faster algorithms for algebraic path properties in recursive state machines with constant treewidth. ACM SIGPLAN Notices. 2015;50(1):97-109. doi:10.1145/2676726.2676979","apa":"Chatterjee, K., Ibsen-Jensen, R., Pavlogiannis, A., & Goyal, P. (2015). Faster algorithms for algebraic path properties in recursive state machines with constant treewidth. ACM SIGPLAN Notices. Mumbai, India: ACM. https://doi.org/10.1145/2676726.2676979","short":"K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, P. Goyal, ACM SIGPLAN Notices 50 (2015) 97–109.","ieee":"K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, and P. Goyal, “Faster algorithms for algebraic path properties in recursive state machines with constant treewidth,” ACM SIGPLAN Notices, vol. 50, no. 1. ACM, pp. 97–109, 2015."},"month":"01","intvolume":" 50","scopus_import":1,"main_file_link":[{"url":"https://arxiv.org/abs/1410.7724","open_access":"1"}],"oa_version":"Preprint","abstract":[{"text":"Interprocedural analysis is at the heart of numerous applications in programming languages, such as alias analysis, constant propagation, etc. Recursive state machines (RSMs) are standard models for interprocedural analysis. We consider a general framework with RSMs where the transitions are labeled from a semiring, and path properties are algebraic with semiring operations. RSMs with algebraic path properties can model interprocedural dataflow analysis problems, the shortest path problem, the most probable path problem, etc. The traditional algorithms for interprocedural analysis focus on path properties where the starting point is fixed as the entry point of a specific method. In this work, we consider possible multiple queries as required in many applications such as in alias analysis. The study of multiple queries allows us to bring in a very important algorithmic distinction between the resource usage of the one-time preprocessing vs for each individual query. The second aspect that we consider is that the control flow graphs for most programs have constant treewidth. Our main contributions are simple and implementable algorithms that supportmultiple queries for algebraic path properties for RSMs that have constant treewidth. Our theoretical results show that our algorithms have small additional one-time preprocessing, but can answer subsequent queries significantly faster as compared to the current best-known solutions for several important problems, such as interprocedural reachability and shortest path. We provide a prototype implementation for interprocedural reachability and intraprocedural shortest path that gives a significant speed-up on several benchmarks.","lang":"eng"}],"issue":"1","related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"821"}]},"volume":50,"ec_funded":1,"language":[{"iso":"eng"}],"publication_status":"published","status":"public","type":"journal_article","conference":{"location":"Mumbai, India","end_date":"2015-01-17","start_date":"2015-01-15","name":"SIGPLAN: Symposium on Principles of Programming Languages"},"_id":"1602","department":[{"_id":"KrCh"}],"date_updated":"2023-09-07T12:01:58Z"},{"project":[{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23"},{"grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"title":"Quantitative interprocedural analysis","author":[{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Pavlogiannis","full_name":"Pavlogiannis, Andreas","orcid":"0000-0002-8943-0722","id":"49704004-F248-11E8-B48F-1D18A9856A87","first_name":"Andreas"},{"full_name":"Velner, Yaron","last_name":"Velner","first_name":"Yaron"}],"publist_id":"5563","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"chicago":"Chatterjee, Krishnendu, Andreas Pavlogiannis, and Yaron Velner. “Quantitative Interprocedural Analysis.” Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT . ACM, 2015. https://doi.org/10.1145/2676726.2676968.","ista":"Chatterjee K, Pavlogiannis A, Velner Y. 2015. Quantitative interprocedural analysis. Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT . 50(1), 539–551.","mla":"Chatterjee, Krishnendu, et al. “Quantitative Interprocedural Analysis.” Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT , vol. 50, no. 1, ACM, 2015, pp. 539–51, doi:10.1145/2676726.2676968.","ama":"Chatterjee K, Pavlogiannis A, Velner Y. Quantitative interprocedural analysis. Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT . 2015;50(1):539-551. doi:10.1145/2676726.2676968","apa":"Chatterjee, K., Pavlogiannis, A., & Velner, Y. (2015). Quantitative interprocedural analysis. Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT . Mumbai, India: ACM. https://doi.org/10.1145/2676726.2676968","ieee":"K. Chatterjee, A. Pavlogiannis, and Y. Velner, “Quantitative interprocedural analysis,” Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT , vol. 50, no. 1. ACM, pp. 539–551, 2015.","short":"K. Chatterjee, A. Pavlogiannis, Y. Velner, Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT 50 (2015) 539–551."},"publisher":"ACM","quality_controlled":"1","date_created":"2018-12-11T11:52:59Z","doi":"10.1145/2676726.2676968","date_published":"2015-01-01T00:00:00Z","page":"539 - 551","publication":"Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT ","day":"01","year":"2015","pubrep_id":"523","status":"public","conference":{"name":"SIGPLAN: Symposium on Principles of Programming Languages","start_date":"2015-01-15","location":"Mumbai, India","end_date":"2015-01-17"},"type":"journal_article","_id":"1604","department":[{"_id":"KrCh"}],"date_updated":"2023-09-07T12:01:59Z","intvolume":" 50","month":"01","scopus_import":1,"oa_version":"None","abstract":[{"lang":"eng","text":"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."}],"ec_funded":1,"related_material":{"record":[{"status":"public","id":"5445","relation":"earlier_version"},{"id":"821","status":"public","relation":"dissertation_contains"}]},"volume":50,"issue":"1","language":[{"iso":"eng"}],"publication_status":"published","publication_identifier":{"isbn":["978-1-4503-3300-9"]}},{"project":[{"grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23"},{"name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"citation":{"ista":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2015. Faster algorithms for quantitative verification in constant treewidth graphs. CAV: Computer Aided Verification, LNCS, vol. 9206, 140–157.","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis. “Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs,” 9206:140–57. Springer, 2015. https://doi.org/10.1007/978-3-319-21690-4_9.","apa":"Chatterjee, K., Ibsen-Jensen, R., & Pavlogiannis, A. (2015). Faster algorithms for quantitative verification in constant treewidth graphs (Vol. 9206, pp. 140–157). Presented at the CAV: Computer Aided Verification, San Francisco, CA, USA: Springer. https://doi.org/10.1007/978-3-319-21690-4_9","ama":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. Faster algorithms for quantitative verification in constant treewidth graphs. In: Vol 9206. Springer; 2015:140-157. doi:10.1007/978-3-319-21690-4_9","ieee":"K. Chatterjee, R. Ibsen-Jensen, and A. Pavlogiannis, “Faster algorithms for quantitative verification in constant treewidth graphs,” presented at the CAV: Computer Aided Verification, San Francisco, CA, USA, 2015, vol. 9206, pp. 140–157.","short":"K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, in:, Springer, 2015, pp. 140–157.","mla":"Chatterjee, Krishnendu, et al. Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs. Vol. 9206, Springer, 2015, pp. 140–57, doi:10.1007/978-3-319-21690-4_9."},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","publist_id":"5560","author":[{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"id":"3B699956-F248-11E8-B48F-1D18A9856A87","first_name":"Rasmus","full_name":"Ibsen-Jensen, Rasmus","orcid":"0000-0003-4783-0389","last_name":"Ibsen-Jensen"},{"first_name":"Andreas","id":"49704004-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8943-0722","full_name":"Pavlogiannis, Andreas","last_name":"Pavlogiannis"}],"title":"Faster algorithms for quantitative verification in constant treewidth graphs","acknowledgement":"The research was partly supported by Austrian Science Fund (FWF) Grant No P23499- N23, FWF NFN Grant No S11407-N23 (RiSE/SHiNE), ERC Start grant (279307: Graph Games), and Microsoft faculty fellows award.","oa":1,"quality_controlled":"1","publisher":"Springer","year":"2015","day":"16","page":"140 - 157","date_created":"2018-12-11T11:52:59Z","date_published":"2015-07-16T00:00:00Z","doi":"10.1007/978-3-319-21690-4_9","_id":"1607","conference":{"name":"CAV: Computer Aided Verification","end_date":"2015-07-24","location":"San Francisco, CA, USA","start_date":"2015-07-18"},"type":"conference","status":"public","date_updated":"2023-09-07T12:01:59Z","department":[{"_id":"KrCh"}],"abstract":[{"lang":"eng","text":"We consider the core algorithmic problems related to verification of systems with respect to three classical quantitative properties, namely, the mean-payoff property, the ratio property, and the minimum initial credit for energy property. The algorithmic problem given a graph and a quantitative property asks to compute the optimal value (the infimum value over all traces) from every node of the graph. We consider graphs with constant treewidth, and it is well-known that the control-flow graphs of most programs have constant treewidth. Let n denote the number of nodes of a graph, m the number of edges (for constant treewidth graphs m=O(n)) and W the largest absolute value of the weights. Our main theoretical results are as follows. First, for constant treewidth graphs we present an algorithm that approximates the mean-payoff value within a multiplicative factor of ϵ in time O(n⋅log(n/ϵ)) and linear space, as compared to the classical algorithms that require quadratic time. Second, for the ratio property we present an algorithm that for constant treewidth graphs works in time O(n⋅log(|a⋅b|))=O(n⋅log(n⋅W)), when the output is ab, as compared to the previously best known algorithm with running time O(n2⋅log(n⋅W)). Third, for the minimum initial credit problem we show that (i) for general graphs the problem can be solved in O(n2⋅m) time and the associated decision problem can be solved in O(n⋅m) time, improving the previous known O(n3⋅m⋅log(n⋅W)) and O(n2⋅m) bounds, respectively; and (ii) for constant treewidth graphs we present an algorithm that requires O(n⋅logn) time, improving the previous known O(n4⋅log(n⋅W)) bound. We have implemented some of our algorithms and show that they present a significant speedup on standard benchmarks."}],"oa_version":"Preprint","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1504.07384"}],"alternative_title":["LNCS"],"scopus_import":1,"intvolume":" 9206","month":"07","publication_status":"published","language":[{"iso":"eng"}],"ec_funded":1,"related_material":{"record":[{"relation":"earlier_version","id":"5430","status":"public"},{"status":"public","id":"5437","relation":"earlier_version"},{"relation":"dissertation_contains","status":"public","id":"821"}]},"volume":9206},{"department":[{"_id":"KrCh"}],"date_updated":"2023-09-07T12:01:59Z","conference":{"end_date":"2014-12-05","location":"Rome, Italy","start_date":"2014-12-02","name":"RTSS: Real-Time Systems Symposium"},"type":"conference","status":"public","_id":"1714","related_material":{"record":[{"id":"5423","status":"public","relation":"earlier_version"},{"status":"public","id":"821","relation":"dissertation_contains"}]},"volume":2015,"issue":"January","publication_status":"published","language":[{"iso":"eng"}],"scopus_import":1,"intvolume":" 2015","month":"01","abstract":[{"lang":"eng","text":"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 task set 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 Dover, that have been proposed in the past, for various task sets. Our experimental results reveal that none of these algorithms is universally optimal, in the sense that there are task sets where other schedulers provide better performance. Our framework is hence a very useful design tool for selecting optimal algorithms for a given application."}],"oa_version":"None","article_processing_charge":"No","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"first_name":"Andreas","id":"49704004-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8943-0722","full_name":"Pavlogiannis, Andreas","last_name":"Pavlogiannis"},{"first_name":"Alexander","last_name":"Kößler","full_name":"Kößler, Alexander"},{"full_name":"Schmid, Ulrich","last_name":"Schmid","first_name":"Ulrich"}],"publist_id":"5417","title":"A framework for automated competitive analysis of on-line scheduling of firm-deadline tasks","citation":{"ista":"Chatterjee K, Pavlogiannis A, Kößler A, Schmid U. 2015. A framework for automated competitive analysis of on-line scheduling of firm-deadline tasks. Real-Time Systems Symposium. RTSS: Real-Time Systems Symposium vol. 2015, 118–127.","chicago":"Chatterjee, Krishnendu, Andreas Pavlogiannis, Alexander Kößler, and Ulrich Schmid. “A Framework for Automated Competitive Analysis of On-Line Scheduling of Firm-Deadline Tasks.” In Real-Time Systems Symposium, 2015:118–27. IEEE, 2015. https://doi.org/10.1109/RTSS.2014.9.","apa":"Chatterjee, K., Pavlogiannis, A., Kößler, A., & Schmid, U. (2015). A framework for automated competitive analysis of on-line scheduling of firm-deadline tasks. In Real-Time Systems Symposium (Vol. 2015, pp. 118–127). Rome, Italy: IEEE. https://doi.org/10.1109/RTSS.2014.9","ama":"Chatterjee K, Pavlogiannis A, Kößler A, Schmid U. A framework for automated competitive analysis of on-line scheduling of firm-deadline tasks. In: Real-Time Systems Symposium. Vol 2015. IEEE; 2015:118-127. doi:10.1109/RTSS.2014.9","ieee":"K. Chatterjee, A. Pavlogiannis, A. Kößler, and U. Schmid, “A framework for automated competitive analysis of on-line scheduling of firm-deadline tasks,” in Real-Time Systems Symposium, Rome, Italy, 2015, vol. 2015, no. January, pp. 118–127.","short":"K. Chatterjee, A. Pavlogiannis, A. Kößler, U. Schmid, in:, Real-Time Systems Symposium, IEEE, 2015, pp. 118–127.","mla":"Chatterjee, Krishnendu, et al. “A Framework for Automated Competitive Analysis of On-Line Scheduling of Firm-Deadline Tasks.” Real-Time Systems Symposium, vol. 2015, no. January, IEEE, 2015, pp. 118–27, doi:10.1109/RTSS.2014.9."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"118 - 127","date_created":"2018-12-11T11:53:37Z","date_published":"2015-01-15T00:00:00Z","doi":"10.1109/RTSS.2014.9","year":"2015","publication":"Real-Time Systems Symposium","day":"15","publisher":"IEEE","quality_controlled":"1"},{"file_date_updated":"2020-07-14T12:45:07Z","department":[{"_id":"ChWo"}],"ddc":["000"],"date_updated":"2023-09-07T12:02:56Z","status":"public","pubrep_id":"609","type":"conference","conference":{"start_date":"2015-08-09","location":"Los Angeles, CA, United States","end_date":"2015-08-13","name":"SIGGRAPH: Special Interest Group on Computer Graphics and Interactive Techniques"},"_id":"1633","volume":34,"related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"839"}]},"issue":"4","ec_funded":1,"file":[{"relation":"main_file","access_level":"open_access","content_type":"application/pdf","file_id":"5131","checksum":"955aee971983f6b6152bcc1c9b4a7c20","creator":"system","file_size":20154270,"date_updated":"2020-07-14T12:45:07Z","file_name":"IST-2016-609-v1+1_FractureBEM.pdf","date_created":"2018-12-12T10:15:13Z"}],"language":[{"iso":"eng"}],"publication_status":"published","month":"07","intvolume":" 34","scopus_import":1,"oa_version":"Submitted Version","abstract":[{"text":"We present a method for simulating brittle fracture under the assumptions of quasi-static linear elastic fracture mechanics (LEFM). Using the boundary element method (BEM) and Lagrangian crack-fronts, we produce highly detailed fracture surfaces. The computational cost of the BEM is alleviated by using a low-resolution mesh and interpolating the resulting stress intensity factors when propagating the high-resolution crack-front.\r\n\r\nOur system produces physics-based fracture surfaces with high spatial and temporal resolution, taking spatial variation of material toughness and/or strength into account. It also allows for crack initiation to be handled separately from crack propagation, which is not only more reasonable from a physics perspective, but can also be used to control the simulation.\r\n\r\nSeparating the resolution of the crack-front from the resolution of the computational mesh increases the efficiency and therefore the amount of visual detail on the resulting fracture surfaces. The BEM also allows us to re-use previously computed blocks of the system matrix.","lang":"eng"}],"title":"High-resolution brittle fracture simulation with boundary elements","publist_id":"5522","author":[{"full_name":"Hahn, David","last_name":"Hahn","id":"357A6A66-F248-11E8-B48F-1D18A9856A87","first_name":"David"},{"id":"3C61F1D2-F248-11E8-B48F-1D18A9856A87","first_name":"Christopher J","orcid":"0000-0001-6646-5546","full_name":"Wojtan, Christopher J","last_name":"Wojtan"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"ista":"Hahn D, Wojtan C. 2015. High-resolution brittle fracture simulation with boundary elements. SIGGRAPH: Special Interest Group on Computer Graphics and Interactive Techniques vol. 34, 151.","chicago":"Hahn, David, and Chris Wojtan. “High-Resolution Brittle Fracture Simulation with Boundary Elements,” Vol. 34. ACM, 2015. https://doi.org/10.1145/2766896.","ieee":"D. Hahn and C. Wojtan, “High-resolution brittle fracture simulation with boundary elements,” presented at the SIGGRAPH: Special Interest Group on Computer Graphics and Interactive Techniques, Los Angeles, CA, United States, 2015, vol. 34, no. 4.","short":"D. Hahn, C. Wojtan, in:, ACM, 2015.","ama":"Hahn D, Wojtan C. High-resolution brittle fracture simulation with boundary elements. In: Vol 34. ACM; 2015. doi:10.1145/2766896","apa":"Hahn, D., & Wojtan, C. (2015). High-resolution brittle fracture simulation with boundary elements (Vol. 34). Presented at the SIGGRAPH: Special Interest Group on Computer Graphics and Interactive Techniques, Los Angeles, CA, United States: ACM. https://doi.org/10.1145/2766896","mla":"Hahn, David, and Chris Wojtan. High-Resolution Brittle Fracture Simulation with Boundary Elements. Vol. 34, no. 4, 151, ACM, 2015, doi:10.1145/2766896."},"project":[{"name":"Efficient Simulation of Natural Phenomena at Extremely Large Scales","grant_number":"638176","_id":"2533E772-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"article_number":"151","date_published":"2015-07-27T00:00:00Z","doi":"10.1145/2766896","date_created":"2018-12-11T11:53:09Z","day":"27","has_accepted_license":"1","year":"2015","publisher":"ACM","quality_controlled":"1","oa":1},{"language":[{"iso":"eng"}],"file":[{"checksum":"228d3edf40627d897b3875088a0ac51f","file_id":"5003","relation":"main_file","access_level":"open_access","content_type":"application/pdf","file_name":"IST-2016-484-v1+1_1-s2.0-S0092867415000094-main.pdf","date_created":"2018-12-12T10:13:21Z","creator":"system","file_size":4362653,"date_updated":"2020-07-14T12:45:01Z"}],"publication_status":"published","related_material":{"record":[{"id":"961","status":"public","relation":"dissertation_contains"}]},"volume":160,"issue":"4","oa_version":"Published Version","abstract":[{"text":"3D amoeboid cell migration is central to many developmental and disease-related processes such as cancer metastasis. Here, we identify a unique prototypic amoeboid cell migration mode in early zebrafish embryos, termed stable-bleb migration. Stable-bleb cells display an invariant polarized balloon-like shape with exceptional migration speed and persistence. Progenitor cells can be reversibly transformed into stable-bleb cells irrespective of their primary fate and motile characteristics by increasing myosin II activity through biochemical or mechanical stimuli. Using a combination of theory and experiments, we show that, in stable-bleb cells, cortical contractility fluctuations trigger a stochastic switch into amoeboid motility, and a positive feedback between cortical flows and gradients in contractility maintains stable-bleb cell polarization. We further show that rearward cortical flows drive stable-bleb cell migration in various adhesive and non-adhesive environments, unraveling a highly versatile amoeboid migration phenotype.","lang":"eng"}],"acknowledged_ssus":[{"_id":"SSU"}],"intvolume":" 160","month":"02","scopus_import":1,"ddc":["570"],"date_updated":"2023-09-07T12:05:08Z","file_date_updated":"2020-07-14T12:45:01Z","department":[{"_id":"CaHe"},{"_id":"MiSi"}],"_id":"1537","pubrep_id":"484","status":"public","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"type":"journal_article","publication":"Cell","day":"12","year":"2015","has_accepted_license":"1","date_created":"2018-12-11T11:52:35Z","doi":"10.1016/j.cell.2015.01.008","date_published":"2015-02-12T00:00:00Z","page":"673 - 685","acknowledgement":"We would like to thank R. Hausschild and E. Papusheva for technical assistance and the service facilities at the IST Austria for continuous support. The caRhoA plasmid was a kind gift of T. Kudoh and A. Takesono. We thank M. Piel and E. Paluch for exchanging unpublished data. ","oa":1,"quality_controlled":"1","publisher":"Cell Press","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","citation":{"mla":"Ruprecht, Verena, et al. “Cortical Contractility Triggers a Stochastic Switch to Fast Amoeboid Cell Motility.” Cell, vol. 160, no. 4, Cell Press, 2015, pp. 673–85, doi:10.1016/j.cell.2015.01.008.","apa":"Ruprecht, V., Wieser, S., Callan Jones, A., Smutny, M., Morita, H., Sako, K., … Heisenberg, C.-P. J. (2015). Cortical contractility triggers a stochastic switch to fast amoeboid cell motility. Cell. Cell Press. https://doi.org/10.1016/j.cell.2015.01.008","ama":"Ruprecht V, Wieser S, Callan Jones A, et al. Cortical contractility triggers a stochastic switch to fast amoeboid cell motility. Cell. 2015;160(4):673-685. doi:10.1016/j.cell.2015.01.008","ieee":"V. Ruprecht et al., “Cortical contractility triggers a stochastic switch to fast amoeboid cell motility,” Cell, vol. 160, no. 4. Cell Press, pp. 673–685, 2015.","short":"V. Ruprecht, S. Wieser, A. Callan Jones, M. Smutny, H. Morita, K. Sako, V. Barone, M. Ritsch Marte, M.K. Sixt, R. Voituriez, C.-P.J. Heisenberg, Cell 160 (2015) 673–685.","chicago":"Ruprecht, Verena, Stefan Wieser, Andrew Callan Jones, Michael Smutny, Hitoshi Morita, Keisuke Sako, Vanessa Barone, et al. “Cortical Contractility Triggers a Stochastic Switch to Fast Amoeboid Cell Motility.” Cell. Cell Press, 2015. https://doi.org/10.1016/j.cell.2015.01.008.","ista":"Ruprecht V, Wieser S, Callan Jones A, Smutny M, Morita H, Sako K, Barone V, Ritsch Marte M, Sixt MK, Voituriez R, Heisenberg C-PJ. 2015. Cortical contractility triggers a stochastic switch to fast amoeboid cell motility. Cell. 160(4), 673–685."},"title":"Cortical contractility triggers a stochastic switch to fast amoeboid cell motility","author":[{"orcid":"0000-0003-4088-8633","full_name":"Ruprecht, Verena","last_name":"Ruprecht","first_name":"Verena","id":"4D71A03A-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Stefan","id":"355AA5A0-F248-11E8-B48F-1D18A9856A87","full_name":"Wieser, Stefan","orcid":"0000-0002-2670-2217","last_name":"Wieser"},{"first_name":"Andrew","full_name":"Callan Jones, Andrew","last_name":"Callan Jones"},{"last_name":"Smutny","full_name":"Smutny, Michael","orcid":"0000-0002-5920-9090","first_name":"Michael","id":"3FE6E4E8-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Morita, Hitoshi","last_name":"Morita","first_name":"Hitoshi","id":"4C6E54C6-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Keisuke","id":"3BED66BE-F248-11E8-B48F-1D18A9856A87","last_name":"Sako","orcid":"0000-0002-6453-8075","full_name":"Sako, Keisuke"},{"first_name":"Vanessa","id":"419EECCC-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-2676-3367","full_name":"Barone, Vanessa","last_name":"Barone"},{"first_name":"Monika","full_name":"Ritsch Marte, Monika","last_name":"Ritsch Marte"},{"id":"41E9FBEA-F248-11E8-B48F-1D18A9856A87","first_name":"Michael K","last_name":"Sixt","orcid":"0000-0002-6620-9179","full_name":"Sixt, Michael K"},{"first_name":"Raphaël","last_name":"Voituriez","full_name":"Voituriez, Raphaël"},{"orcid":"0000-0002-0912-4566","full_name":"Heisenberg, Carl-Philipp J","last_name":"Heisenberg","id":"39427864-F248-11E8-B48F-1D18A9856A87","first_name":"Carl-Philipp J"}],"publist_id":"5634","project":[{"call_identifier":"FWF","_id":"2529486C-B435-11E9-9278-68D0E5697425","grant_number":"T 560-B17","name":"Cell- and Tissue Mechanics in Zebrafish Germ Layer Formation"},{"grant_number":"I 812-B12","name":"Cell Cortex and Germ Layer Formation in Zebrafish Gastrulation","call_identifier":"FWF","_id":"2527D5CC-B435-11E9-9278-68D0E5697425"}]},{"title":"PIN-dependent auxin transport: Action, regulation, and evolution","external_id":{"pmid":["25604445"]},"author":[{"first_name":"Maciek","id":"45F536D2-F248-11E8-B48F-1D18A9856A87","last_name":"Adamowski","orcid":"0000-0001-6463-5257","full_name":"Adamowski, Maciek"},{"id":"4159519E-F248-11E8-B48F-1D18A9856A87","first_name":"Jirí","last_name":"Friml","orcid":"0000-0002-8302-7596","full_name":"Friml, Jirí"}],"publist_id":"5580","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"chicago":"Adamowski, Maciek, and Jiří Friml. “PIN-Dependent Auxin Transport: Action, Regulation, and Evolution.” Plant Cell. American Society of Plant Biologists, 2015. https://doi.org/10.1105/tpc.114.134874.","ista":"Adamowski M, Friml J. 2015. PIN-dependent auxin transport: Action, regulation, and evolution. Plant Cell. 27(1), 20–32.","mla":"Adamowski, Maciek, and Jiří Friml. “PIN-Dependent Auxin Transport: Action, Regulation, and Evolution.” Plant Cell, vol. 27, no. 1, American Society of Plant Biologists, 2015, pp. 20–32, doi:10.1105/tpc.114.134874.","ama":"Adamowski M, Friml J. PIN-dependent auxin transport: Action, regulation, and evolution. Plant Cell. 2015;27(1):20-32. doi:10.1105/tpc.114.134874","apa":"Adamowski, M., & Friml, J. (2015). PIN-dependent auxin transport: Action, regulation, and evolution. Plant Cell. American Society of Plant Biologists. https://doi.org/10.1105/tpc.114.134874","ieee":"M. Adamowski and J. Friml, “PIN-dependent auxin transport: Action, regulation, and evolution,” Plant Cell, vol. 27, no. 1. American Society of Plant Biologists, pp. 20–32, 2015.","short":"M. Adamowski, J. Friml, Plant Cell 27 (2015) 20–32."},"oa":1,"quality_controlled":"1","publisher":"American Society of Plant Biologists","date_created":"2018-12-11T11:52:54Z","date_published":"2015-01-20T00:00:00Z","doi":"10.1105/tpc.114.134874","page":"20 - 32","publication":"Plant Cell","day":"20","year":"2015","status":"public","type":"journal_article","_id":"1591","department":[{"_id":"JiFr"}],"date_updated":"2023-09-07T12:06:09Z","intvolume":" 27","month":"01","main_file_link":[{"url":"http://www.ncbi.nlm.nih.gov/pmc/articles/PMC4330589/","open_access":"1"}],"scopus_import":1,"oa_version":"Submitted Version","pmid":1,"abstract":[{"lang":"eng","text":"Auxin participates in a multitude of developmental processes, as well as responses to environmental cues. Compared with other plant hormones, auxin exhibits a unique property, as it undergoes directional, cell-to-cell transport facilitated by plasma membrane-localized transport proteins. Among them, a prominent role has been ascribed to the PIN family of auxin efflux facilitators. PIN proteins direct polar auxin transport on account of their asymmetric subcellular localizations. In this review, we provide an overview of the multiple developmental roles of PIN proteins, including the atypical endoplasmic reticulum-localized members of the family, and look at the family from an evolutionary perspective. Next, we cover the cell biological and molecular aspects of PIN function, in particular the establishment of their polar subcellular localization. Hormonal and environmental inputs into the regulation of PIN action are summarized as well."}],"volume":27,"issue":"1","related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"938"}]},"language":[{"iso":"eng"}],"publication_status":"published"},{"article_number":"103301","project":[{"call_identifier":"FP7","_id":"258DCDE6-B435-11E9-9278-68D0E5697425","grant_number":"338804","name":"Random matrices, universality and disordered quantum systems"}],"citation":{"apa":"Alt, J. (2015). The local semicircle law for random matrices with a fourfold symmetry. Journal of Mathematical Physics. American Institute of Physics. https://doi.org/10.1063/1.4932606","ama":"Alt J. The local semicircle law for random matrices with a fourfold symmetry. Journal of Mathematical Physics. 2015;56(10). doi:10.1063/1.4932606","short":"J. Alt, Journal of Mathematical Physics 56 (2015).","ieee":"J. Alt, “The local semicircle law for random matrices with a fourfold symmetry,” Journal of Mathematical Physics, vol. 56, no. 10. American Institute of Physics, 2015.","mla":"Alt, Johannes. “The Local Semicircle Law for Random Matrices with a Fourfold Symmetry.” Journal of Mathematical Physics, vol. 56, no. 10, 103301, American Institute of Physics, 2015, doi:10.1063/1.4932606.","ista":"Alt J. 2015. The local semicircle law for random matrices with a fourfold symmetry. Journal of Mathematical Physics. 56(10), 103301.","chicago":"Alt, Johannes. “The Local Semicircle Law for Random Matrices with a Fourfold Symmetry.” Journal of Mathematical Physics. American Institute of Physics, 2015. https://doi.org/10.1063/1.4932606."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"full_name":"Alt, Johannes","last_name":"Alt","first_name":"Johannes","id":"36D3D8B6-F248-11E8-B48F-1D18A9856A87"}],"publist_id":"5472","title":"The local semicircle law for random matrices with a fourfold symmetry","publisher":"American Institute of Physics","quality_controlled":"1","oa":1,"year":"2015","day":"09","publication":"Journal of Mathematical Physics","doi":"10.1063/1.4932606","date_published":"2015-10-09T00:00:00Z","date_created":"2018-12-11T11:53:25Z","_id":"1677","type":"journal_article","status":"public","date_updated":"2023-09-07T12:38:08Z","department":[{"_id":"LaEr"}],"abstract":[{"text":"We consider real symmetric and complex Hermitian random matrices with the additional symmetry hxy = hN-y,N-x. The matrix elements are independent (up to the fourfold symmetry) and not necessarily identically distributed. This ensemble naturally arises as the Fourier transform of a Gaussian orthogonal ensemble. Italso occurs as the flip matrix model - an approximation of the two-dimensional Anderson model at small disorder. We show that the density of states converges to the Wigner semicircle law despite the new symmetry type. We also prove the local version of the semicircle law on the optimal scale.","lang":"eng"}],"oa_version":"Preprint","scopus_import":1,"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1506.04683"}],"month":"10","intvolume":" 56","publication_status":"published","language":[{"iso":"eng"}],"volume":56,"related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"149"}]},"issue":"10","ec_funded":1},{"project":[{"call_identifier":"FP7","_id":"25548C20-B435-11E9-9278-68D0E5697425","name":"Microbial Ion Channels for Synthetic Neurobiology","grant_number":"303564"},{"grant_number":"RGY0084/2012","name":"In situ real-time imaging of neurotransmitter signaling using designer optical sensors (HFSP Young Investigator)","_id":"255BFFFA-B435-11E9-9278-68D0E5697425"},{"_id":"255A6082-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"W1232-B24","name":"Molecular Drug Targets"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"ista":"Inglés Prieto Á, Gschaider-Reichhart E, Muellner M, Nowak M, Nijman S, Grusch M, Janovjak HL. 2015. Light-assisted small-molecule screening against protein kinases. Nature Chemical Biology. 11(12), 952–954.","chicago":"Inglés Prieto, Álvaro, Eva Gschaider-Reichhart, Markus Muellner, Matthias Nowak, Sebastian Nijman, Michael Grusch, and Harald L Janovjak. “Light-Assisted Small-Molecule Screening against Protein Kinases.” Nature Chemical Biology. Nature Publishing Group, 2015. https://doi.org/10.1038/nchembio.1933.","ieee":"Á. Inglés Prieto et al., “Light-assisted small-molecule screening against protein kinases,” Nature Chemical Biology, vol. 11, no. 12. Nature Publishing Group, pp. 952–954, 2015.","short":"Á. Inglés Prieto, E. Gschaider-Reichhart, M. Muellner, M. Nowak, S. Nijman, M. Grusch, H.L. Janovjak, Nature Chemical Biology 11 (2015) 952–954.","ama":"Inglés Prieto Á, Gschaider-Reichhart E, Muellner M, et al. Light-assisted small-molecule screening against protein kinases. Nature Chemical Biology. 2015;11(12):952-954. doi:10.1038/nchembio.1933","apa":"Inglés Prieto, Á., Gschaider-Reichhart, E., Muellner, M., Nowak, M., Nijman, S., Grusch, M., & Janovjak, H. L. (2015). Light-assisted small-molecule screening against protein kinases. Nature Chemical Biology. Nature Publishing Group. https://doi.org/10.1038/nchembio.1933","mla":"Inglés Prieto, Álvaro, et al. “Light-Assisted Small-Molecule Screening against Protein Kinases.” Nature Chemical Biology, vol. 11, no. 12, Nature Publishing Group, 2015, pp. 952–54, doi:10.1038/nchembio.1933."},"title":"Light-assisted small-molecule screening against protein kinases","publist_id":"5471","author":[{"full_name":"Inglés Prieto, Álvaro","orcid":"0000-0002-5409-8571","last_name":"Inglés Prieto","first_name":"Álvaro","id":"2A9DB292-F248-11E8-B48F-1D18A9856A87"},{"orcid":"0000-0002-7218-7738","full_name":"Gschaider-Reichhart, Eva","last_name":"Gschaider-Reichhart","id":"3FEE232A-F248-11E8-B48F-1D18A9856A87","first_name":"Eva"},{"first_name":"Markus","full_name":"Muellner, Markus","last_name":"Muellner"},{"full_name":"Nowak, Matthias","last_name":"Nowak","first_name":"Matthias","id":"30845DAA-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Nijman, Sebastian","last_name":"Nijman","first_name":"Sebastian"},{"first_name":"Michael","last_name":"Grusch","full_name":"Grusch, Michael"},{"last_name":"Janovjak","full_name":"Janovjak, Harald L","orcid":"0000-0002-8023-9315","first_name":"Harald L","id":"33BA6C30-F248-11E8-B48F-1D18A9856A87"}],"acknowledgement":"This work was supported by grants from the European Union Seventh Framework Programme (CIG-303564 to H.J. and ERC-StG-311166 to S.M.B.N.), the Human Frontier Science Program (RGY0084_2012 to H.J.) and the Herzfelder Foundation (to M.G.). A.I.-P. was supported by a Ramon Areces fellowship, and E.R. by the graduate program MolecularDrugTargets (Austrian Science Fund (FWF): W 1232) and a FemTech fellowship (3580812 Austrian Research Promotion Agency).","oa":1,"quality_controlled":"1","publisher":"Nature Publishing Group","publication":"Nature Chemical Biology","day":"12","year":"2015","has_accepted_license":"1","date_created":"2018-12-11T11:53:25Z","date_published":"2015-10-12T00:00:00Z","doi":"10.1038/nchembio.1933","page":"952 - 954","_id":"1678","pubrep_id":"837","status":"public","type":"journal_article","ddc":["571"],"date_updated":"2023-09-07T12:49:09Z","department":[{"_id":"HaJa"},{"_id":"LifeSc"}],"file_date_updated":"2020-07-14T12:45:12Z","oa_version":"Submitted Version","abstract":[{"text":"High-throughput live-cell screens are intricate elements of systems biology studies and drug discovery pipelines. Here, we demonstrate an optogenetics-assisted method that avoids the need for chemical activators and reporters, reduces the number of operational steps and increases information content in a cell-based small-molecule screen against human protein kinases, including an orphan receptor tyrosine kinase. This blueprint for all-optical screening can be adapted to many drug targets and cellular processes.","lang":"eng"}],"intvolume":" 11","month":"10","scopus_import":1,"language":[{"iso":"eng"}],"file":[{"date_updated":"2020-07-14T12:45:12Z","file_size":1308364,"creator":"system","date_created":"2018-12-12T10:10:51Z","file_name":"IST-2017-837-v1+1_ingles-prieto.pdf","content_type":"application/pdf","access_level":"open_access","relation":"main_file","file_id":"4842","checksum":"e9fb251dfcb7cd209b83f17867e61321"}],"publication_status":"published","ec_funded":1,"volume":11,"issue":"12","related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"418"}]}},{"abstract":[{"lang":"eng","text":"Gene expression is controlled primarily by interactions between transcription factor proteins (TFs) and the regulatory DNA sequence, a process that can be captured well by thermodynamic models of regulation. These models, however, neglect regulatory crosstalk: the possibility that noncognate TFs could initiate transcription, with potentially disastrous effects for the cell. Here, we estimate the importance of crosstalk, suggest that its avoidance strongly constrains equilibrium models of TF binding, and propose an alternative nonequilibrium scheme that implements kinetic proofreading to suppress erroneous initiation. This proposal is consistent with the observed covalent modifications of the transcriptional apparatus and predicts increased noise in gene expression as a trade-off for improved specificity. Using information theory, we quantify this trade-off to find when optimal proofreading architectures are favored over their equilibrium counterparts. Such architectures exhibit significant super-Poisson noise at low expression in steady state."}],"oa_version":"Preprint","scopus_import":1,"main_file_link":[{"url":"http://arxiv.org/abs/1504.05716","open_access":"1"}],"month":"12","intvolume":" 115","publication_status":"published","language":[{"iso":"eng"}],"related_material":{"record":[{"status":"public","id":"6473","relation":"part_of_dissertation"}]},"issue":"24","volume":115,"ec_funded":1,"_id":"1576","type":"journal_article","status":"public","date_updated":"2023-09-07T12:55:21Z","department":[{"_id":"GaTk"}],"quality_controlled":"1","publisher":"American Physical Society","oa":1,"year":"2015","day":"08","publication":"Physical Review Letters","doi":"10.1103/PhysRevLett.115.248101","date_published":"2015-12-08T00:00:00Z","date_created":"2018-12-11T11:52:49Z","article_number":"248101","project":[{"call_identifier":"FP7","_id":"25B07788-B435-11E9-9278-68D0E5697425","grant_number":"250152","name":"Limits to selection in biology and in evolutionary computation"}],"citation":{"mla":"Cepeda Humerez, Sarah A., et al. “Stochastic Proofreading Mechanism Alleviates Crosstalk in Transcriptional Regulation.” Physical Review Letters, vol. 115, no. 24, 248101, American Physical Society, 2015, doi:10.1103/PhysRevLett.115.248101.","ieee":"S. A. Cepeda Humerez, G. Rieckh, and G. Tkačik, “Stochastic proofreading mechanism alleviates crosstalk in transcriptional regulation,” Physical Review Letters, vol. 115, no. 24. American Physical Society, 2015.","short":"S.A. Cepeda Humerez, G. Rieckh, G. Tkačik, Physical Review Letters 115 (2015).","apa":"Cepeda Humerez, S. A., Rieckh, G., & Tkačik, G. (2015). Stochastic proofreading mechanism alleviates crosstalk in transcriptional regulation. Physical Review Letters. American Physical Society. https://doi.org/10.1103/PhysRevLett.115.248101","ama":"Cepeda Humerez SA, Rieckh G, Tkačik G. Stochastic proofreading mechanism alleviates crosstalk in transcriptional regulation. Physical Review Letters. 2015;115(24). doi:10.1103/PhysRevLett.115.248101","chicago":"Cepeda Humerez, Sarah A, Georg Rieckh, and Gašper Tkačik. “Stochastic Proofreading Mechanism Alleviates Crosstalk in Transcriptional Regulation.” Physical Review Letters. American Physical Society, 2015. https://doi.org/10.1103/PhysRevLett.115.248101.","ista":"Cepeda Humerez SA, Rieckh G, Tkačik G. 2015. Stochastic proofreading mechanism alleviates crosstalk in transcriptional regulation. Physical Review Letters. 115(24), 248101."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"id":"3DEE19A4-F248-11E8-B48F-1D18A9856A87","first_name":"Sarah A","full_name":"Cepeda Humerez, Sarah A","last_name":"Cepeda Humerez"},{"last_name":"Rieckh","full_name":"Rieckh, Georg","id":"34DA8BD6-F248-11E8-B48F-1D18A9856A87","first_name":"Georg"},{"id":"3D494DCA-F248-11E8-B48F-1D18A9856A87","first_name":"Gasper","last_name":"Tkacik","full_name":"Tkacik, Gasper","orcid":"0000-0002-6699-1455"}],"publist_id":"5595","title":"Stochastic proofreading mechanism alleviates crosstalk in transcriptional regulation"},{"acknowledgement":"We would like to thank A. Klyachko, V. Krushkal, S. Melikhov, M. Tancer, P. Teichner and anonymous referees for helpful discussions.","oa_version":"Preprint","abstract":[{"text":"We study conditions under which a finite simplicial complex $K$ can be mapped to $\\mathbb R^d$ without higher-multiplicity intersections. An almost $r$-embedding is a map $f: K\\to \\mathbb R^d$ such that the images of any $r$\r\npairwise disjoint simplices of $K$ do not have a common point. We show that if $r$ is not a prime power and $d\\geq 2r+1$, then there is a counterexample to the topological Tverberg conjecture, i.e., there is an almost $r$-embedding of\r\nthe $(d+1)(r-1)$-simplex in $\\mathbb R^d$. This improves on previous constructions of counterexamples (for $d\\geq 3r$) based on a series of papers by M. \\\"Ozaydin, M. Gromov, P. Blagojevi\\'c, F. Frick, G. Ziegler, and the second and fourth present authors. The counterexamples are obtained by proving the following algebraic criterion in codimension 2: If $r\\ge3$ and if $K$ is a finite $2(r-1)$-complex then there exists an almost $r$-embedding $K\\to \\mathbb R^{2r}$ if and only if there exists a general position PL map $f:K\\to \\mathbb R^{2r}$ such that the algebraic intersection number of the $f$-images of any $r$ pairwise disjoint simplices of $K$ is zero. This result can be restated in terms of cohomological obstructions or equivariant maps, and extends an analogous codimension 3 criterion by the second and fourth authors. As another application we classify ornaments $f:S^3 \\sqcup S^3\\sqcup S^3\\to \\mathbb R^5$ up to ornament\r\nconcordance. It follows from work of M. Freedman, V. Krushkal and P. Teichner that the analogous criterion for $r=2$ is false. We prove a lemma on singular higher-dimensional Borromean rings, yielding an elementary proof of the counterexample.","lang":"eng"}],"month":"11","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1511.03501"}],"oa":1,"language":[{"iso":"eng"}],"publication":"arXiv","day":"15","year":"2015","publication_status":"submitted","date_created":"2020-07-30T10:45:19Z","related_material":{"record":[{"status":"public","id":"9308","relation":"later_version"},{"relation":"later_version","status":"public","id":"10220"},{"relation":"dissertation_contains","id":"8156","status":"public"}]},"date_published":"2015-11-15T00:00:00Z","article_number":"1511.03501","_id":"8183","status":"public","type":"preprint","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2023-09-07T13:12:17Z","citation":{"short":"S. Avvakumov, I. Mabillard, A. Skopenkov, U. Wagner, ArXiv (n.d.).","ieee":"S. Avvakumov, I. Mabillard, A. Skopenkov, and U. Wagner, “Eliminating higher-multiplicity intersections, III. Codimension 2,” arXiv. .","ama":"Avvakumov S, Mabillard I, Skopenkov A, Wagner U. Eliminating higher-multiplicity intersections, III. Codimension 2. arXiv.","apa":"Avvakumov, S., Mabillard, I., Skopenkov, A., & Wagner, U. (n.d.). Eliminating higher-multiplicity intersections, III. Codimension 2. arXiv.","mla":"Avvakumov, Sergey, et al. “Eliminating Higher-Multiplicity Intersections, III. Codimension 2.” ArXiv, 1511.03501.","ista":"Avvakumov S, Mabillard I, Skopenkov A, Wagner U. Eliminating higher-multiplicity intersections, III. Codimension 2. arXiv, 1511.03501.","chicago":"Avvakumov, Sergey, Isaac Mabillard, A. Skopenkov, and Uli Wagner. “Eliminating Higher-Multiplicity Intersections, III. Codimension 2.” ArXiv, n.d."},"department":[{"_id":"UlWa"}],"title":"Eliminating higher-multiplicity intersections, III. Codimension 2","article_processing_charge":"No","external_id":{"arxiv":["1511.03501"]},"author":[{"last_name":"Avvakumov","full_name":"Avvakumov, Sergey","id":"3827DAC8-F248-11E8-B48F-1D18A9856A87","first_name":"Sergey"},{"first_name":"Isaac","id":"32BF9DAA-F248-11E8-B48F-1D18A9856A87","last_name":"Mabillard","full_name":"Mabillard, Isaac"},{"first_name":"A.","full_name":"Skopenkov, A.","last_name":"Skopenkov"},{"full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli"}]},{"_id":"5441","type":"technical_report","status":"public","pubrep_id":"340","citation":{"chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, Amir Kafshdar Goharshady, and Andreas Pavlogiannis. Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components. IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-340-v1-1.","ista":"Chatterjee K, Ibsen-Jensen R, Goharshady AK, Pavlogiannis A. 2015. Algorithms for algebraic path properties in concurrent systems of constant treewidth components, IST Austria, 24p.","mla":"Chatterjee, Krishnendu, et al. Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components. IST Austria, 2015, doi:10.15479/AT:IST-2015-340-v1-1.","short":"K. Chatterjee, R. Ibsen-Jensen, A.K. Goharshady, A. Pavlogiannis, Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components, IST Austria, 2015.","ieee":"K. Chatterjee, R. Ibsen-Jensen, A. K. Goharshady, and A. Pavlogiannis, Algorithms for algebraic path properties in concurrent systems of constant treewidth components. IST Austria, 2015.","apa":"Chatterjee, K., Ibsen-Jensen, R., Goharshady, A. K., & Pavlogiannis, A. (2015). Algorithms for algebraic path properties in concurrent systems of constant treewidth components. IST Austria. https://doi.org/10.15479/AT:IST-2015-340-v1-1","ama":"Chatterjee K, Ibsen-Jensen R, Goharshady AK, Pavlogiannis A. Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components. IST Austria; 2015. doi:10.15479/AT:IST-2015-340-v1-1"},"date_updated":"2023-09-19T14:36:19Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["000"],"author":[{"last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu"},{"last_name":"Ibsen-Jensen","full_name":"Ibsen-Jensen, Rasmus","orcid":"0000-0003-4783-0389","first_name":"Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Goharshady","full_name":"Goharshady, Amir","orcid":"0000-0003-1702-6584","first_name":"Amir","id":"391365CE-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Andreas","id":"49704004-F248-11E8-B48F-1D18A9856A87","full_name":"Pavlogiannis, Andreas","orcid":"0000-0002-8943-0722","last_name":"Pavlogiannis"}],"department":[{"_id":"KrCh"}],"file_date_updated":"2020-07-14T12:46:56Z","title":"Algorithms for algebraic path properties in concurrent systems of constant treewidth components","abstract":[{"lang":"eng","text":"We study algorithmic questions for concurrent systems where the transitions are labeled from a complete, closed semiring, and path properties are algebraic with semiring operations. The algebraic path properties can model dataflow analysis problems, the shortest path problem, and many other natural problems that arise in program analysis. We consider that each component of the concurrent system is a graph with constant treewidth, a property satisfied by the controlflow graphs of most programs. We allow for multiple possible queries, which arise naturally in demand driven dataflow analysis. The study of multiple queries allows us to consider the tradeoff between the resource usage of the one-time preprocessing and for each individual query. The traditional approach constructs the product graph of all components and applies the best-known graph algorithm on the product. In this approach, even the answer to a single query requires the transitive closure (i.e., the results of all possible queries), which provides no room for tradeoff between preprocessing and query time. Our main contributions are algorithms that significantly improve the worst-case running time of the traditional approach, and provide various tradeoffs depending on the number of queries. For example, in a concurrent system of two components, the traditional approach requires hexic time in the worst case for answering one query as well as computing the transitive closure, whereas we show that with one-time preprocessing in almost cubic time, each subsequent query can be answered in at most linear time, and even the transitive closure can be computed in almost quartic time. Furthermore, we establish conditional optimality results showing that the worst-case running time of our algorithms cannot be improved without achieving major breakthroughs in graph algorithms (i.e., improving the worst-case bound for the shortest path problem in general graphs). Preliminary experimental results show that our algorithms perform favorably on several benchmarks."}],"oa_version":"Published Version","publisher":"IST Austria","alternative_title":["IST Austria Technical Report"],"oa":1,"month":"07","has_accepted_license":"1","publication_identifier":{"issn":["2664-1690"]},"publication_status":"published","year":"2015","file":[{"checksum":"df383dc62c94d7b2ea639aba088a76c6","file_id":"5531","content_type":"application/pdf","access_level":"open_access","relation":"main_file","date_created":"2018-12-12T11:54:09Z","file_name":"IST-2015-340-v1+1_main.pdf","date_updated":"2020-07-14T12:46:56Z","file_size":861396,"creator":"system"}],"day":"11","language":[{"iso":"eng"}],"page":"24","date_published":"2015-07-11T00:00:00Z","doi":"10.15479/AT:IST-2015-340-v1-1","related_material":{"record":[{"relation":"later_version","id":"1437","status":"public"},{"id":"5442","status":"public","relation":"earlier_version"},{"relation":"later_version","id":"6009","status":"public"}]},"date_created":"2018-12-12T11:39:21Z"},{"scopus_import":1,"alternative_title":["IST Austria Technical Report"],"publisher":"IST Austria","oa":1,"month":"07","abstract":[{"lang":"eng","text":"We study algorithmic questions for concurrent systems where the transitions are labeled from a complete, closed semiring, and path properties are algebraic with semiring operations. The algebraic path properties can model dataflow analysis problems, the shortest path problem, and many other natural properties that arise in program analysis.\r\nWe consider that each component of the concurrent system is a graph with constant treewidth, and it is known that the controlflow graphs of most programs have constant treewidth. We allow for multiple possible queries, which arise naturally in demand driven dataflow analysis problems (e.g., alias analysis). The study of multiple queries allows us to consider the tradeoff between the resource usage of the \\emph{one-time} preprocessing and for \\emph{each individual} query. The traditional approaches construct the product graph of all components and apply the best-known graph algorithm on the product. In the traditional approach, even the answer to a single query requires the transitive closure computation (i.e., the results of all possible queries), which provides no room for tradeoff between preprocessing and query time.\r\n\r\nOur main contributions are algorithms that significantly improve the worst-case running time of the traditional approach, and provide various tradeoffs depending on the number of queries. For example, in a concurrent system of two components, the traditional approach requires hexic time in the worst case for answering one query as well as computing the transitive closure, whereas we show that with one-time preprocessing in almost cubic time, \r\neach subsequent query can be answered in at most linear time, and even the transitive closure can be computed in almost quartic time. Furthermore, we establish conditional optimality results that show that the worst-case running times of our algorithms cannot be improved without achieving major breakthroughs in graph algorithms (such as improving \r\nthe worst-case bounds for the shortest path problem in general graphs whose current best-known bound has not been improved in five decades). Finally, we provide a prototype implementation of our algorithms which significantly outperforms the existing algorithmic methods on several benchmarks."}],"oa_version":"Published Version","page":"22","related_material":{"record":[{"status":"public","id":"1437","relation":"later_version"},{"id":"5441","status":"public","relation":"later_version"},{"id":"6009","status":"public","relation":"later_version"}]},"date_published":"2015-07-14T00:00:00Z","date_created":"2018-12-12T11:39:21Z","has_accepted_license":"1","publication_identifier":{"issn":["2664-1690"]},"year":"2015","publication_status":"published","day":"14","file":[{"file_name":"IST-2015-343-v2+1_main.pdf","date_created":"2018-12-12T11:53:37Z","creator":"system","file_size":658747,"date_updated":"2020-07-14T12:46:57Z","file_id":"5498","checksum":"98fd936102f3e057fc321ef6d316001d","relation":"main_file","access_level":"open_access","content_type":"application/pdf"},{"date_created":"2019-04-16T12:36:08Z","file_name":"IST-2015-343-v2+2_anonymous.txt","date_updated":"2020-07-14T12:46:57Z","file_size":139,"creator":"dernst","file_id":"6316","checksum":"b31d09b1241b59c75e1f42dadf09d258","content_type":"text/plain","access_level":"closed","relation":"main_file"}],"language":[{"iso":"eng"}],"type":"technical_report","status":"public","pubrep_id":"344","_id":"5442","author":[{"last_name":"Anonymous","full_name":"Anonymous, 1","first_name":"1"},{"last_name":"Anonymous","full_name":"Anonymous, 2","first_name":"2"},{"full_name":"Anonymous, 3","last_name":"Anonymous","first_name":"3"},{"full_name":"Anonymous, 4","last_name":"Anonymous","first_name":"4"}],"title":"Algorithms for algebraic path properties in concurrent systems of constant treewidth components","file_date_updated":"2020-07-14T12:46:57Z","citation":{"mla":"Anonymous, 1, et al. Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components. IST Austria, 2015.","ama":"Anonymous 1, Anonymous 2, Anonymous 3, Anonymous 4. Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components. IST Austria; 2015.","apa":"Anonymous, 1, Anonymous, 2, Anonymous, 3, & Anonymous, 4. (2015). Algorithms for algebraic path properties in concurrent systems of constant treewidth components. IST Austria.","short":"1 Anonymous, 2 Anonymous, 3 Anonymous, 4 Anonymous, Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components, IST Austria, 2015.","ieee":"1 Anonymous, 2 Anonymous, 3 Anonymous, and 4 Anonymous, Algorithms for algebraic path properties in concurrent systems of constant treewidth components. IST Austria, 2015.","chicago":"Anonymous, 1, 2 Anonymous, 3 Anonymous, and 4 Anonymous. Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components. IST Austria, 2015.","ista":"Anonymous 1, Anonymous 2, Anonymous 3, Anonymous 4. 2015. Algorithms for algebraic path properties in concurrent systems of constant treewidth components, IST Austria, 22p."},"date_updated":"2023-09-19T14:36:19Z","ddc":["000"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"title":"Temporal logic control for stochastic linear systems using abstraction refinement of probabilistic games","department":[{"_id":"ToHe"},{"_id":"KrCh"}],"publist_id":"5456","author":[{"first_name":"Mária","full_name":"Svoreňová, Mária","last_name":"Svoreňová"},{"id":"44CEF464-F248-11E8-B48F-1D18A9856A87","first_name":"Jan","full_name":"Kretinsky, Jan","orcid":"0000-0002-8122-2881","last_name":"Kretinsky"},{"id":"3624234E-F248-11E8-B48F-1D18A9856A87","first_name":"Martin","full_name":"Chmelik, Martin","last_name":"Chmelik"},{"first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X"},{"full_name":"Cěrná, Ivana","last_name":"Cěrná","first_name":"Ivana"},{"first_name":"Cǎlin","full_name":"Belta, Cǎlin","last_name":"Belta"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2023-09-20T09:43:09Z","citation":{"short":"M. Svoreňová, J. Kretinsky, M. Chmelik, K. Chatterjee, I. Cěrná, C. Belta, in:, Proceedings of the 18th International Conference on Hybrid Systems: Computation and Control, ACM, 2015, pp. 259–268.","ieee":"M. Svoreňová, J. Kretinsky, M. Chmelik, K. Chatterjee, I. Cěrná, and C. Belta, “Temporal logic control for stochastic linear systems using abstraction refinement of probabilistic games,” in Proceedings of the 18th International Conference on Hybrid Systems: Computation and Control, Seattle, WA, United States, 2015, pp. 259–268.","apa":"Svoreňová, M., Kretinsky, J., Chmelik, M., Chatterjee, K., Cěrná, I., & Belta, C. (2015). Temporal logic control for stochastic linear systems using abstraction refinement of probabilistic games. In Proceedings of the 18th International Conference on Hybrid Systems: Computation and Control (pp. 259–268). Seattle, WA, United States: ACM. https://doi.org/10.1145/2728606.2728608","ama":"Svoreňová M, Kretinsky J, Chmelik M, Chatterjee K, Cěrná I, Belta C. Temporal logic control for stochastic linear systems using abstraction refinement of probabilistic games. In: Proceedings of the 18th International Conference on Hybrid Systems: Computation and Control. ACM; 2015:259-268. doi:10.1145/2728606.2728608","mla":"Svoreňová, Mária, et al. “Temporal Logic Control for Stochastic Linear Systems Using Abstraction Refinement of Probabilistic Games.” Proceedings of the 18th International Conference on Hybrid Systems: Computation and Control, ACM, 2015, pp. 259–68, doi:10.1145/2728606.2728608.","ista":"Svoreňová M, Kretinsky J, Chmelik M, Chatterjee K, Cěrná I, Belta C. 2015. Temporal logic control for stochastic linear systems using abstraction refinement of probabilistic games. Proceedings of the 18th International Conference on Hybrid Systems: Computation and Control. HSCC: Hybrid Systems - Computation and Control, 259–268.","chicago":"Svoreňová, Mária, Jan Kretinsky, Martin Chmelik, Krishnendu Chatterjee, Ivana Cěrná, and Cǎlin Belta. “Temporal Logic Control for Stochastic Linear Systems Using Abstraction Refinement of Probabilistic Games.” In Proceedings of the 18th International Conference on Hybrid Systems: Computation and Control, 259–68. ACM, 2015. https://doi.org/10.1145/2728606.2728608."},"project":[{"name":"International IST Postdoc Fellowship Programme","grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"},{"call_identifier":"FP7","_id":"25EE3708-B435-11E9-9278-68D0E5697425","name":"Quantitative Reactive Modeling","grant_number":"267989"},{"call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307"},{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23"},{"call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425","name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23"},{"grant_number":"S11407","name":"Game Theory","_id":"25863FF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"}],"status":"public","conference":{"name":"HSCC: Hybrid Systems - Computation and Control","location":"Seattle, WA, United States","end_date":"2015-04-16","start_date":"2015-04-14"},"type":"conference","_id":"1689","ec_funded":1,"date_created":"2018-12-11T11:53:29Z","related_material":{"record":[{"relation":"later_version","status":"public","id":"1407"}]},"doi":"10.1145/2728606.2728608","date_published":"2015-04-14T00:00:00Z","page":"259 - 268","publication":"Proceedings of the 18th International Conference on Hybrid Systems: Computation and Control","language":[{"iso":"eng"}],"day":"14","year":"2015","publication_status":"published","month":"04","oa":1,"main_file_link":[{"url":"http://arxiv.org/abs/1410.5387","open_access":"1"}],"publisher":"ACM","scopus_import":1,"oa_version":"Preprint","abstract":[{"lang":"eng","text":"We consider the problem of computing the set of initial states of a dynamical system such that there exists a control strategy to ensure that the trajectories satisfy a temporal logic specification with probability 1 (almost-surely). We focus on discrete-time, stochastic linear dynamics and specifications given as formulas of the Generalized Reactivity(1) fragment of Linear Temporal Logic over linear predicates in the states of the system. We propose a solution based on iterative abstraction-refinement, and turn-based 2-player probabilistic games. While the theoretical guarantee of our algorithm after any finite number of iterations is only a partial solution, we show that if our algorithm terminates, then the result is the set of satisfying initial states. Moreover, for any (partial) solution our algorithm synthesizes witness control strategies to ensure almost-sure satisfaction of the temporal logic specification. We demonstrate our approach on an illustrative case study."}]},{"ec_funded":1,"related_material":{"record":[{"status":"public","id":"1130","relation":"dissertation_contains"},{"id":"1338","status":"public","relation":"later_version"}]},"volume":9207,"publication_status":"published","language":[{"iso":"eng"}],"file":[{"file_size":481922,"date_updated":"2020-07-14T12:45:13Z","creator":"system","file_name":"IST-2015-336-v1+1_long_version.pdf","date_created":"2018-12-12T10:08:53Z","content_type":"application/pdf","relation":"main_file","access_level":"local","file_id":"4715","checksum":"6ff58ac220e2f20cb001ba35d4924495"}],"alternative_title":["LNCS"],"scopus_import":1,"intvolume":" 9207","month":"07","abstract":[{"text":"We present a computer-aided programming approach to concurrency. The approach allows programmers to program assuming a friendly, non-preemptive scheduler, and our synthesis procedure inserts synchronization to ensure that the final program works even with a preemptive scheduler. The correctness specification is implicit, inferred from the non-preemptive behavior. Let us consider sequences of calls that the program makes to an external interface. The specification requires that any such sequence produced under a preemptive scheduler should be included in the set of such sequences produced under a non-preemptive scheduler. The solution is based on a finitary abstraction, an algorithm for bounded language inclusion modulo an independence relation, and rules for inserting synchronization. We apply the approach to device-driver programming, where the driver threads call the software interface of the device and the API provided by the operating system. Our experiments demonstrate that our synthesis method is precise and efficient, and, since it does not require explicit specifications, is more practical than the conventional approach based on user-provided assertions.","lang":"eng"}],"oa_version":"Submitted Version","file_date_updated":"2020-07-14T12:45:13Z","department":[{"_id":"ToHe"}],"date_updated":"2023-09-20T11:13:50Z","ddc":["000"],"conference":{"name":"CAV: Computer Aided Verification","start_date":"2015-07-18","end_date":"2015-07-24","location":"San Francisco, CA, United States"},"type":"conference","pubrep_id":"336","status":"public","_id":"1729","series_title":"Lecture Notes in Computer Science","page":"180 - 197","date_created":"2018-12-11T11:53:42Z","doi":"10.1007/978-3-319-21668-3_11","date_published":"2015-07-01T00:00:00Z","year":"2015","has_accepted_license":"1","day":"01","publisher":"Springer","quality_controlled":"1","author":[{"first_name":"Pavol","id":"4DCBEFFE-F248-11E8-B48F-1D18A9856A87","full_name":"Cerny, Pavol","last_name":"Cerny"},{"last_name":"Clarke","full_name":"Clarke, Edmund","first_name":"Edmund"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A","orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A","last_name":"Henzinger"},{"first_name":"Arjun","id":"3B51CAC4-F248-11E8-B48F-1D18A9856A87","last_name":"Radhakrishna","full_name":"Radhakrishna, Arjun"},{"first_name":"Leonid","full_name":"Ryzhyk, Leonid","last_name":"Ryzhyk"},{"first_name":"Roopsha","id":"3D2AAC08-F248-11E8-B48F-1D18A9856A87","full_name":"Samanta, Roopsha","last_name":"Samanta"},{"id":"3D6E8F2C-F248-11E8-B48F-1D18A9856A87","first_name":"Thorsten","full_name":"Tarrach, Thorsten","orcid":"0000-0003-4409-8487","last_name":"Tarrach"}],"publist_id":"5398","title":"From non-preemptive to preemptive scheduling using synchronization synthesis","citation":{"ista":"Cerny P, Clarke E, Henzinger TA, Radhakrishna A, Ryzhyk L, Samanta R, Tarrach T. 2015. From non-preemptive to preemptive scheduling using synchronization synthesis. 9207, 180–197.","chicago":"Cerny, Pavol, Edmund Clarke, Thomas A Henzinger, Arjun Radhakrishna, Leonid Ryzhyk, Roopsha Samanta, and Thorsten Tarrach. “From Non-Preemptive to Preemptive Scheduling Using Synchronization Synthesis.” Lecture Notes in Computer Science. Springer, 2015. https://doi.org/10.1007/978-3-319-21668-3_11.","short":"P. Cerny, E. Clarke, T.A. Henzinger, A. Radhakrishna, L. Ryzhyk, R. Samanta, T. Tarrach, 9207 (2015) 180–197.","ieee":"P. Cerny et al., “From non-preemptive to preemptive scheduling using synchronization synthesis,” vol. 9207. Springer, pp. 180–197, 2015.","ama":"Cerny P, Clarke E, Henzinger TA, et al. From non-preemptive to preemptive scheduling using synchronization synthesis. 2015;9207:180-197. doi:10.1007/978-3-319-21668-3_11","apa":"Cerny, P., Clarke, E., Henzinger, T. A., Radhakrishna, A., Ryzhyk, L., Samanta, R., & Tarrach, T. (2015). From non-preemptive to preemptive scheduling using synchronization synthesis. Presented at the CAV: Computer Aided Verification, San Francisco, CA, United States: Springer. https://doi.org/10.1007/978-3-319-21668-3_11","mla":"Cerny, Pavol, et al. From Non-Preemptive to Preemptive Scheduling Using Synchronization Synthesis. Vol. 9207, Springer, 2015, pp. 180–97, doi:10.1007/978-3-319-21668-3_11."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","project":[{"name":"Quantitative Reactive Modeling","grant_number":"267989","_id":"25EE3708-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"},{"grant_number":"Z211","name":"The Wittgenstein Prize","_id":"25F42A32-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23"}]},{"related_material":{"record":[{"relation":"later_version","id":"1351","status":"public"}]},"volume":9035,"ec_funded":1,"language":[{"iso":"eng"}],"publication_status":"published","month":"04","intvolume":" 9035","scopus_import":1,"alternative_title":["LNCS"],"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1410.7704"}],"oa_version":"Preprint","abstract":[{"lang":"eng","text":"The behaviour of gene regulatory networks (GRNs) is typically analysed using simulation-based statistical testing-like methods. In this paper, we demonstrate that we can replace this approach by a formal verification-like method that gives higher assurance and scalability. We focus on Wagner’s weighted GRN model with varying weights, which is used in evolutionary biology. In the model, weight parameters represent the gene interaction strength that may change due to genetic mutations. For a property of interest, we synthesise the constraints over the parameter space that represent the set of GRNs satisfying the property. We experimentally show that our parameter synthesis procedure computes the mutational robustness of GRNs –an important problem of interest in evolutionary biology– more efficiently than the classical simulation method. We specify the property in linear temporal logics. We employ symbolic bounded model checking and SMT solving to compute the space of GRNs that satisfy the property, which amounts to synthesizing a set of linear constraints on the weights."}],"department":[{"_id":"ToHe"},{"_id":"CaGu"},{"_id":"NiBa"}],"date_updated":"2023-09-20T11:06:03Z","status":"public","type":"conference","conference":{"name":"TACAS: Tools and Algorithms for the Construction and Analysis of Systems","start_date":"2015-04-11","location":"London, United Kingdom","end_date":"2015-04-18"},"_id":"1835","series_title":"Lecture Notes in Computer Science","date_published":"2015-04-01T00:00:00Z","doi":"10.1007/978-3-662-46681-0_47","date_created":"2018-12-11T11:54:16Z","page":"469 - 483","day":"01","year":"2015","quality_controlled":"1","publisher":"Springer","oa":1,"acknowledgement":"SNSF Early Postdoc.Mobility Fellowship, the grant number P2EZP2 148797.\r\n","title":"Model checking gene regulatory networks","author":[{"first_name":"Mirco","id":"3444EA5E-F248-11E8-B48F-1D18A9856A87","last_name":"Giacobbe","orcid":"0000-0001-8180-0904","full_name":"Giacobbe, Mirco"},{"first_name":"Calin C","id":"47F8433E-F248-11E8-B48F-1D18A9856A87","last_name":"Guet","full_name":"Guet, Calin C","orcid":"0000-0001-6220-2052"},{"full_name":"Gupta, Ashutosh","last_name":"Gupta","first_name":"Ashutosh","id":"335E5684-F248-11E8-B48F-1D18A9856A87"},{"orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A","last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A"},{"first_name":"Tiago","id":"2C5658E6-F248-11E8-B48F-1D18A9856A87","last_name":"Paixao","orcid":"0000-0003-2361-3953","full_name":"Paixao, Tiago"},{"first_name":"Tatjana","id":"3D5811FC-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9041-0905","full_name":"Petrov, Tatjana","last_name":"Petrov"}],"publist_id":"5267","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"apa":"Giacobbe, M., Guet, C. C., Gupta, A., Henzinger, T. A., Paixao, T., & Petrov, T. (2015). Model checking gene regulatory networks. Presented at the TACAS: Tools and Algorithms for the Construction and Analysis of Systems, London, United Kingdom: Springer. https://doi.org/10.1007/978-3-662-46681-0_47","ama":"Giacobbe M, Guet CC, Gupta A, Henzinger TA, Paixao T, Petrov T. Model checking gene regulatory networks. 2015;9035:469-483. doi:10.1007/978-3-662-46681-0_47","short":"M. Giacobbe, C.C. Guet, A. Gupta, T.A. Henzinger, T. Paixao, T. Petrov, 9035 (2015) 469–483.","ieee":"M. Giacobbe, C. C. Guet, A. Gupta, T. A. Henzinger, T. Paixao, and T. Petrov, “Model checking gene regulatory networks,” vol. 9035. Springer, pp. 469–483, 2015.","mla":"Giacobbe, Mirco, et al. Model Checking Gene Regulatory Networks. Vol. 9035, Springer, 2015, pp. 469–83, doi:10.1007/978-3-662-46681-0_47.","ista":"Giacobbe M, Guet CC, Gupta A, Henzinger TA, Paixao T, Petrov T. 2015. Model checking gene regulatory networks. 9035, 469–483.","chicago":"Giacobbe, Mirco, Calin C Guet, Ashutosh Gupta, Thomas A Henzinger, Tiago Paixao, and Tatjana Petrov. “Model Checking Gene Regulatory Networks.” Lecture Notes in Computer Science. Springer, 2015. https://doi.org/10.1007/978-3-662-46681-0_47."},"project":[{"call_identifier":"FP7","_id":"25EE3708-B435-11E9-9278-68D0E5697425","name":"Quantitative Reactive Modeling","grant_number":"267989"},{"call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23","name":"Rigorous Systems Engineering"},{"name":"The Wittgenstein Prize","grant_number":"Z211","_id":"25F42A32-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"name":"Speed of Adaptation in Population Genetics and Evolutionary Computation","grant_number":"618091","call_identifier":"FP7","_id":"25B1EC9E-B435-11E9-9278-68D0E5697425"},{"grant_number":"250152","name":"Limits to selection in biology and in evolutionary computation","call_identifier":"FP7","_id":"25B07788-B435-11E9-9278-68D0E5697425"},{"name":"International IST Postdoc Fellowship Programme","grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}]},{"project":[{"call_identifier":"FP7","_id":"25716A02-B435-11E9-9278-68D0E5697425","name":"Polarity and subcellular dynamics in plants","grant_number":"282300"}],"citation":{"mla":"Michalko, Jaroslav, et al. “Embryo-Lethal Phenotypes in Early Abp1 Mutants Are Due to Disruption of the Neighboring BSM Gene.” F1000 Research , vol. 4, F1000 Research, 2015, doi:10.12688/f1000research.7143.1.","ama":"Michalko J, Lukacisinova M, Bollenbach MT, Friml J. Embryo-lethal phenotypes in early abp1 mutants are due to disruption of the neighboring BSM gene. F1000 Research . 2015;4. doi:10.12688/f1000research.7143.1","apa":"Michalko, J., Lukacisinova, M., Bollenbach, M. T., & Friml, J. (2015). Embryo-lethal phenotypes in early abp1 mutants are due to disruption of the neighboring BSM gene. F1000 Research . F1000 Research. https://doi.org/10.12688/f1000research.7143.1","ieee":"J. Michalko, M. Lukacisinova, M. T. Bollenbach, and J. Friml, “Embryo-lethal phenotypes in early abp1 mutants are due to disruption of the neighboring BSM gene,” F1000 Research , vol. 4. F1000 Research, 2015.","short":"J. Michalko, M. Lukacisinova, M.T. Bollenbach, J. Friml, F1000 Research 4 (2015).","chicago":"Michalko, Jaroslav, Marta Lukacisinova, Mark Tobias Bollenbach, and Jiří Friml. “Embryo-Lethal Phenotypes in Early Abp1 Mutants Are Due to Disruption of the Neighboring BSM Gene.” F1000 Research . F1000 Research, 2015. https://doi.org/10.12688/f1000research.7143.1.","ista":"Michalko J, Lukacisinova M, Bollenbach MT, Friml J. 2015. Embryo-lethal phenotypes in early abp1 mutants are due to disruption of the neighboring BSM gene. F1000 Research . 4."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","publist_id":"5668","author":[{"id":"483727CA-F248-11E8-B48F-1D18A9856A87","first_name":"Jaroslav","full_name":"Michalko, Jaroslav","last_name":"Michalko"},{"last_name":"Dravecka","orcid":"0000-0002-2519-8004","full_name":"Dravecka, Marta","first_name":"Marta","id":"4342E402-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Tobias","id":"3E6DB97A-F248-11E8-B48F-1D18A9856A87","full_name":"Bollenbach, Tobias","orcid":"0000-0003-4398-476X","last_name":"Bollenbach"},{"orcid":"0000-0002-8302-7596","full_name":"Friml, Jirí","last_name":"Friml","first_name":"Jirí","id":"4159519E-F248-11E8-B48F-1D18A9856A87"}],"title":"Embryo-lethal phenotypes in early abp1 mutants are due to disruption of the neighboring BSM gene","acknowledgement":"This work was supported by ERC Independent Research grant (ERC-2011-StG-20101109-PSDP to JF). JM internship was supported by the grant “Action Austria – Slovakia”.\r\nData associated with the article are available under the terms of the Creative Commons Zero \"No rights reserved\" data waiver (CC0 1.0 Public domain dedication). \r\n\r\nData availability: \r\nF1000Research: Dataset 1. Dataset 1, 10.5256/f1000research.7143.d104552\r\n\r\nF1000Research: Dataset 2. Dataset 2, 10.5256/f1000research.7143.d104553\r\n\r\nF1000Research: Dataset 3. Dataset 3, 10.5256/f1000research.7143.d104554","oa":1,"quality_controlled":"1","publisher":"F1000 Research","year":"2015","has_accepted_license":"1","publication":"F1000 Research ","day":"01","date_created":"2018-12-11T11:52:26Z","doi":"10.12688/f1000research.7143.1","date_published":"2015-10-01T00:00:00Z","_id":"1509","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"type":"journal_article","pubrep_id":"497","status":"public","date_updated":"2023-10-10T14:10:24Z","ddc":["570"],"department":[{"_id":"JiFr"},{"_id":"ToBo"}],"file_date_updated":"2020-07-14T12:44:59Z","abstract":[{"lang":"eng","text":"The Auxin Binding Protein1 (ABP1) has been identified based on its ability to bind auxin with high affinity and studied for a long time as a prime candidate for the extracellular auxin receptor responsible for mediating in particular the fast non-transcriptional auxin responses. However, the contradiction between the embryo-lethal phenotypes of the originally described Arabidopsis T-DNA insertional knock-out alleles (abp1-1 and abp1-1s) and the wild type-like phenotypes of other recently described loss-of-function alleles (abp1-c1 and abp1-TD1) questions the biological importance of ABP1 and relevance of the previous genetic studies. Here we show that there is no hidden copy of the ABP1 gene in the Arabidopsis genome but the embryo-lethal phenotypes of abp1-1 and abp1-1s alleles are very similar to the knock-out phenotypes of the neighboring gene, BELAYA SMERT (BSM). Furthermore, the allelic complementation test between bsm and abp1 alleles shows that the embryo-lethality in the abp1-1 and abp1-1s alleles is caused by the off-target disruption of the BSM locus by the T-DNA insertions. This clarifies the controversy of different phenotypes among published abp1 knock-out alleles and asks for reflections on the developmental role of ABP1."}],"oa_version":"Published Version","scopus_import":"1","intvolume":" 4","month":"10","publication_status":"published","language":[{"iso":"eng"}],"file":[{"date_updated":"2020-07-14T12:44:59Z","file_size":4414248,"creator":"system","date_created":"2018-12-12T10:16:12Z","file_name":"IST-2016-497-v1+1_10.12688_f1000research.7143.1_20151102.pdf","content_type":"application/pdf","access_level":"open_access","relation":"main_file","checksum":"8beae5cbe988e1060265ae7de2ee8306","file_id":"5198"}],"ec_funded":1,"volume":4}]