@article{7106, abstract = {PIN-FORMED (PIN) transporters mediate directional, intercellular movement of the phytohormone auxin in land plants. To elucidate the evolutionary origins of this developmentally crucial mechanism, we analysed the single PIN homologue of a simple green alga Klebsormidium flaccidum. KfPIN functions as a plasma membrane-localized auxin exporter in land plants and heterologous models. While its role in algae remains unclear, PIN-driven auxin export is probably an ancient and conserved trait within streptophytes.}, author = {Skokan, Roman and Medvecká, Eva and Viaene, Tom and Vosolsobě, Stanislav and Zwiewka, Marta and Müller, Karel and Skůpa, Petr and Karady, Michal and Zhang, Yuzhou and Janacek, Dorina P. and Hammes, Ulrich Z. and Ljung, Karin and Nodzyński, Tomasz and Petrášek, Jan and Friml, Jiří}, issn = {2055-0278}, journal = {Nature Plants}, number = {11}, pages = {1114--1119}, publisher = {Springer Nature}, title = {{PIN-driven auxin transport emerged early in streptophyte evolution}}, doi = {10.1038/s41477-019-0542-5}, volume = {5}, year = {2019}, } @article{7105, abstract = {Cell migration is hypothesized to involve a cycle of behaviours beginning with leading edge extension. However, recent evidence suggests that the leading edge may be dispensable for migration, raising the question of what actually controls cell directionality. Here, we exploit the embryonic migration of Drosophila macrophages to bridge the different temporal scales of the behaviours controlling motility. This approach reveals that edge fluctuations during random motility are not persistent and are weakly correlated with motion. In contrast, flow of the actin network behind the leading edge is highly persistent. Quantification of actin flow structure during migration reveals a stable organization and asymmetry in the cell-wide flowfield that strongly correlates with cell directionality. This organization is regulated by a gradient of actin network compression and destruction, which is controlled by myosin contraction and cofilin-mediated disassembly. It is this stable actin-flow polarity, which integrates rapid fluctuations of the leading edge, that controls inherent cellular persistence.}, author = {Yolland, Lawrence and Burki, Mubarik and Marcotti, Stefania and Luchici, Andrei and Kenny, Fiona N. and Davis, John Robert and Serna-Morales, Eduardo and Müller, Jan and Sixt, Michael K and Davidson, Andrew and Wood, Will and Schumacher, Linus J. and Endres, Robert G. and Miodownik, Mark and Stramer, Brian M.}, issn = {1476-4679}, journal = {Nature Cell Biology}, number = {11}, pages = {1370--1381}, publisher = {Springer Nature}, title = {{Persistent and polarized global actin flow is essential for directionality during cell migration}}, doi = {10.1038/s41556-019-0411-5}, volume = {21}, year = {2019}, } @article{7109, abstract = {We show how to construct temporal testers for the logic MITL, a prominent linear-time logic for real-time systems. A temporal tester is a transducer that inputs a signal holding the Boolean value of atomic propositions and outputs the truth value of a formula along time. Here we consider testers over continuous-time Boolean signals that use clock variables to enforce duration constraints, as in timed automata. We first rewrite the MITL formula into a “simple” formula using a limited set of temporal modalities. We then build testers for these specific modalities and show how to compose testers for simple formulae into complex ones. Temporal testers can be turned into acceptors, yielding a compositional translation from MITL to timed automata. This construction is much simpler than previously known and remains asymptotically optimal. It supports both past and future operators and can easily be extended.}, author = {Ferrere, Thomas and Maler, Oded and Ničković, Dejan and Pnueli, Amir}, issn = {0004-5411}, journal = {Journal of the ACM}, number = {3}, publisher = {ACM}, title = {{From real-time logic to timed automata}}, doi = {10.1145/3286976}, volume = {66}, year = {2019}, } @article{7108, abstract = {We prove that for every d ≥ 2, deciding if a pure, d-dimensional, simplicial complex is shellable is NP-hard, hence NP-complete. This resolves a question raised, e.g., by Danaraj and Klee in 1978. Our reduction also yields that for every d ≥ 2 and k ≥ 0, deciding if a pure, d-dimensional, simplicial complex is k-decomposable is NP-hard. For d ≥ 3, both problems remain NP-hard when restricted to contractible pure d-dimensional complexes. Another simple corollary of our result is that it is NP-hard to decide whether a given poset is CL-shellable.}, author = {Goaoc, Xavier and Patak, Pavel and Patakova, Zuzana and Tancer, Martin and Wagner, Uli}, issn = {0004-5411}, journal = {Journal of the ACM}, number = {3}, publisher = {ACM}, title = {{Shellability is NP-complete}}, doi = {10.1145/3314024}, volume = {66}, year = {2019}, } @inproceedings{7147, abstract = {The expression of a gene is characterised by its transcription factors and the function processing them. If the transcription factors are not affected by gene products, the regulating function is often represented as a combinational logic circuit, where the outputs (product) are determined by current input values (transcription factors) only, and are hence independent on their relative arrival times. However, the simultaneous arrival of transcription factors (TFs) in genetic circuits is a strong assumption, given that the processes of transcription and translation of a gene into a protein introduce intrinsic time delays and that there is no global synchronisation among the arrival times of different molecular species at molecular targets. In this paper, we construct an experimentally implementable genetic circuit with two inputs and a single output, such that, in presence of small delays in input arrival, the circuit exhibits qualitatively distinct observable phenotypes. In particular, these phenotypes are long lived transients: they all converge to a single value, but so slowly, that they seem stable for an extended time period, longer than typical experiment duration. We used rule-based language to prototype our circuit, and we implemented a search for finding the parameter combinations raising the phenotypes of interest. The behaviour of our prototype circuit has wide implications. First, it suggests that GRNs can exploit event timing to create phenotypes. Second, it opens the possibility that GRNs are using event timing to react to stimuli and memorise events, without explicit feedback in regulation. From the modelling perspective, our prototype circuit demonstrates the critical importance of analysing the transient dynamics at the promoter binding sites of the DNA, before applying rapid equilibrium assumptions.}, author = {Guet, Calin C and Henzinger, Thomas A and Igler, Claudia and Petrov, Tatjana and Sezgin, Ali}, booktitle = {17th International Conference on Computational Methods in Systems Biology}, isbn = {9783030313036}, issn = {1611-3349}, location = {Trieste, Italy}, pages = {155--187}, publisher = {Springer Nature}, title = {{Transient memory in gene regulation}}, doi = {10.1007/978-3-030-31304-3_9}, volume = {11773}, year = {2019}, } @inproceedings{7136, abstract = {It is well established that the notion of min-entropy fails to satisfy the \emph{chain rule} of the form H(X,Y)=H(X|Y)+H(Y), known for Shannon Entropy. Such a property would help to analyze how min-entropy is split among smaller blocks. Problems of this kind arise for example when constructing extractors and dispersers. We show that any sequence of variables exhibits a very strong strong block-source structure (conditional distributions of blocks are nearly flat) when we \emph{spoil few correlated bits}. This implies, conditioned on the spoiled bits, that \emph{splitting-recombination properties} hold. In particular, we have many nice properties that min-entropy doesn't obey in general, for example strong chain rules, "information can't hurt" inequalities, equivalences of average and worst-case conditional entropy definitions and others. Quantitatively, for any sequence X1,…,Xt of random variables over an alphabet X we prove that, when conditioned on m=t⋅O(loglog|X|+loglog(1/ϵ)+logt) bits of auxiliary information, all conditional distributions of the form Xi|X