On the discrepancy of jittered sampling - Pausinger, Florian; Steinerberger, Stefan (Journal of Complexity)
We study the discrepancy of jittered sampling sets: such a set P⊂ [0,1]d is generated for fixed m∈ℕ by partitioning [0,1]d into md axis aligned cubes of equal measure and placing a random point inside each of the N=md cubes. We prove that, for N sufficiently large, 1/10 d/N1/2+1/2d ≤EDN∗(P)≤ √d(log N) 1/2/N1/2+1/2d, where the upper bound with an unspecified constant Cd was proven earlier by Beck. Our proof makes crucial use of the sharp Dvoretzky-Kiefer-Wolfowitz inequality and a suitably taylored Bernstein inequality; we have reasons to believe that the upper bound has the sharp scaling in N. Additional heuristics suggest that jittered sampling should be able to improve known bounds on the inverse of the star-discrepancy in the regime N≳dd. We also prove a partition principle showing that every partition of [0,1]d combined with a jittered sampling construction gives rise to a set whose expected squared L2-discrepancy is smaller than that of purely random points.

The external field dependence of the BCS critical temperature - Frank, Rupert; Hainzl, Christian; Seiringer, Robert; Solovej, Jan (Communications in Mathematical Physics)
We consider the Bardeen–Cooper–Schrieffer free energy functional for particles interacting via a two-body potential on a microscopic scale and in the presence of weak external fields varying on a macroscopic scale. We study the influence of the external fields on the critical temperature. We show that in the limit where the ratio between the microscopic and macroscopic scale tends to zero, the next to leading order of the critical temperature is determined by the lowest eigenvalue of the linearization of the Ginzburg–Landau equation.

Fractional Hardy–Lieb–Thirring and related Inequalities for interacting systems - Lundholm, Douglas; Nam, Phan; Portmann, Fabian (Archive for Rational Mechanics and Analysis)
We prove analogues of the Lieb–Thirring and Hardy–Lieb–Thirring inequalities for many-body quantum systems with fractional kinetic operators and homogeneous interaction potentials, where no anti-symmetry on the wave functions is assumed. These many-body inequalities imply interesting one-body interpolation inequalities, and we show that the corresponding one- and many-body inequalities are actually equivalent in certain cases.

Spread of pedigree versus genetic ancestry in spatially distributed populations - Kelleher, Jerome; Etheridge, Alison; Véber, Amandine; Barton, Nicholas H (Theoretical Population Biology)
Ancestral processes are fundamental to modern population genetics and spatial structure has been the subject of intense interest for many years. Despite this interest, almost nothing is known about the distribution of the locations of pedigree or genetic ancestors. Using both spatially continuous and stepping-stone models, we show that the distribution of pedigree ancestors approaches a travelling wave, for which we develop two alternative approximations. The speed and width of the wave are sensitive to the local details of the model. After a short time, genetic ancestors spread far more slowly than pedigree ancestors, ultimately diffusing out with radius ## rather than spreading at constant speed. In contrast to the wave of pedigree ancestors, the spread of genetic ancestry is insensitive to the local details of the models.

A forward genetic screen for new regulators of auxin mediated degradation of auxin transport proteins in Arabidopsis thaliana - Zemová, Radka; Zwiewka, Marta; Bielach, Agnieszka; Robert, Hélène; Friml, Jirí (Journal of Plant Growth Regulation)
The plant hormone auxin (indole-3-acetic acid) is a major regulator of plant growth and development including embryo and root patterning, lateral organ formation and growth responses to environmental stimuli. Auxin is directionally transported from cell to cell by the action of specific auxin influx [AUXIN-RESISTANT1 (AUX1)] and efflux [PIN-FORMED (PIN)] transport regulators, whose polar, subcellular localizations are aligned with the direction of the auxin flow. Auxin itself regulates its own transport by modulation of the expression and subcellular localization of the auxin transporters. Increased auxin levels promote the transcription of PIN2 and AUX1 genes as well as stabilize PIN proteins at the plasma membrane, whereas prolonged auxin exposure increases the turnover of PIN proteins and their degradation in the vacuole. In this study, we applied a forward genetic approach, to identify molecular components playing a role in the auxin-mediated degradation. We generated EMS-mutagenized Arabidopsis PIN2::PIN2:GFP, AUX1::AUX1:YFP eir1aux1 populations and designed a screen for mutants with persistently strong fluorescent signals of the tagged PIN2 and AUX1 after prolonged treatment with the synthetic auxin 2,4-dichlorophenoxyacetic acid (2,4-D). This approach yielded novel auxin degradation mutants defective in trafficking and degradation of PIN2 and AUX1 proteins and established a role for auxin-mediated degradation in plant development.

Practical round-optimal blind signatures in the standard model from weaker assumptions - Fuchsbauer, Georg; Hanser, Christian; Kamath Hosdurg, Chethan; Slamanig, Daniel
At Crypto 2015 Fuchsbauer, Hanser and Slamanig (FHS) presented the first standard-model construction of efficient roundoptimal blind signatures that does not require complexity leveraging. It is conceptually simple and builds on the primitive of structure-preserving signatures on equivalence classes (SPS-EQ). FHS prove the unforgeability of their scheme assuming EUF-CMA security of the SPS-EQ scheme and hardness of a version of the DH inversion problem. Blindness under adversarially chosen keys is proven under an interactive variant of the DDH assumption. We propose a variant of their scheme whose blindness can be proven under a non-interactive assumption, namely a variant of the bilinear DDH assumption. We moreover prove its unforgeability assuming only unforgeability of the underlying SPS-EQ but no additional assumptions as needed for the FHS scheme.

New realizations of somewhere statistically binding hashing and positional accumulators - Okamoto, Tatsuaki; Pietrzak, Krzysztof Z; Waters, Brent; Wichs, Daniel
A somewhere statistically binding (SSB) hash, introduced by Hubáček and Wichs (ITCS ’15), can be used to hash a long string x to a short digest y = H hk (x) using a public hashing-key hk. Furthermore, there is a way to set up the hash key hk to make it statistically binding on some arbitrary hidden position i, meaning that: (1) the digest y completely determines the i’th bit (or symbol) of x so that all pre-images of y have the same value in the i’th position, (2) it is computationally infeasible to distinguish the position i on which hk is statistically binding from any other position i’. Lastly, the hash should have a local opening property analogous to Merkle-Tree hashing, meaning that given x and y = H hk (x) it should be possible to create a short proof π that certifies the value of the i’th bit (or symbol) of x without having to provide the entire input x. A similar primitive called a positional accumulator, introduced by Koppula, Lewko and Waters (STOC ’15) further supports dynamic updates of the hashed value. These tools, which are interesting in their own right, also serve as one of the main technical components in several recent works building advanced applications from indistinguishability obfuscation (iO). The prior constructions of SSB hashing and positional accumulators required fully homomorphic encryption (FHE) and iO respectively. In this work, we give new constructions of these tools based on well studied number-theoretic assumptions such as DDH, Phi-Hiding and DCR, as well as a general construction from lossy/injective functions.

Adaptive moment closure for parameter inference of biochemical reaction networks - Schilling, Christian; Bogomolov, Sergiy; Henzinger, Thomas A; Podelski, Andreas; Ruess, Jakob (Biosystems)
Continuous-time Markov chain (CTMC) models have become a central tool for understanding the dynamics of complex reaction networks and the importance of stochasticity in the underlying biochemical processes. When such models are employed to answer questions in applications, in order to ensure that the model provides a sufficiently accurate representation of the real system, it is of vital importance that the model parameters are inferred from real measured data. This, however, is often a formidable task and all of the existing methods fail in one case or the other, usually because the underlying CTMC model is high-dimensional and computationally difficult to analyze. The parameter inference methods that tend to scale best in the dimension of the CTMC are based on so-called moment closure approximations. However, there exists a large number of different moment closure approximations and it is typically hard to say a priori which of the approximations is the most suitable for the inference procedure. Here, we propose a moment-based parameter inference method that automatically chooses the most appropriate moment closure method. Accordingly, contrary to existing methods, the user is not required to be experienced in moment closure techniques. In addition to that, our method adaptively changes the approximation during the parameter inference to ensure that always the best approximation is used, even in cases where different approximations are best in different regions of the parameter space. © 2016 Elsevier Ireland Ltd

Guided search for hybrid systems based on coarse-grained space abstractions - Bogomolov, Sergiy; Donzé, Alexandre; Frehse, Goran; Grosu, Radu; Johnson, Taylor; Ladan, Hamed; Podelski, Andreas; Wehrle, Martin (International Journal on Software Tools for Technology Transfer)
Hybrid systems represent an important and powerful formalism for modeling real-world applications such as embedded systems. A verification tool like SpaceEx is based on the exploration of a symbolic search space (the region space). As a verification tool, it is typically optimized towards proving the absence of errors. In some settings, e.g., when the verification tool is employed in a feedback-directed design cycle, one would like to have the option to call a version that is optimized towards finding an error trajectory in the region space. A recent approach in this direction is based on guided search. Guided search relies on a cost function that indicates which states are promising to be explored, and preferably explores more promising states first. In this paper, we propose an abstraction-based cost function based on coarse-grained space abstractions for guiding the reachability analysis. For this purpose, a suitable abstraction technique that exploits the flexible granularity of modern reachability analysis algorithms is introduced. The new cost function is an effective extension of pattern database approaches that have been successfully applied in other areas. The approach has been implemented in the SpaceEx model checker. The evaluation shows its practical potential.

Optimal geospatial allocation of volunteers for crisis management - Pielorz, Jasmin; Lampert, Christoph
Volunteer supporters play an important role in modern crisis and disaster management. In the times of mobile Internet devices, help from thousands of volunteers can be requested within a short time span, thus relieving professional helpers from minor chores or geographically spread-out tasks. However, the simultaneous availability of many volunteers also poses new problems. In particular, the volunteer efforts must be well coordinated, or otherwise situations might emerge in which too many idle volunteers at one location become more of a burden than a relief to the professionals. In this work, we study the task of optimally assigning volunteers to selected locations, e.g. in order to perform regular measurements, to report on damage, or to distribute information or resources to the population in a crisis situation. We formulate the assignment tasks as an optimization problem and propose an effective and efficient solution procedure. Experiments on real data of the Team Österreich, consisting of over 36,000 Austrian volunteers, show the effectiveness and efficiency of our approach.

On the closure of relational models - Klimova, Anna; Rudas, Tamás (Journal of Multivariate Analysis)
Relational models for contingency tables are generalizations of log-linear models, allowing effects associated with arbitrary subsets of cells in the table, and not necessarily containing the overall effect, that is, a common parameter in every cell. Similarly to log-linear models, relational models can be extended to non-negative distributions, but the extension requires more complex methods. An extended relational model is defined as an algebraic variety, and it turns out to be the closure of the original model with respect to the Bregman divergence. In the extended relational model, the MLE of the cell parameters always exists and is unique, but some of its properties may be different from those of the MLE under log-linear models. The MLE can be computed using a generalized iterative scaling procedure based on Bregman projections.

Extremal eigenvalues and eigenvectors of deformed Wigner matrices - Lee, Jioon; Schnelli, Kevin (Probability Theory and Related Fields)
We consider random matrices of the form H=W+λV, λ∈ℝ+, where W is a real symmetric or complex Hermitian Wigner matrix of size N and V is a real bounded diagonal random matrix of size N with i.i.d.\ entries that are independent of W. We assume subexponential decay for the matrix entries of W and we choose λ∼1, so that the eigenvalues of W and λV are typically of the same order. Further, we assume that the density of the entries of V is supported on a single interval and is convex near the edges of its support. In this paper we prove that there is λ+∈ℝ+ such that the largest eigenvalues of H are in the limit of large N determined by the order statistics of V for λ>λ+. In particular, the largest eigenvalue of H has a Weibull distribution in the limit N→∞ if λ>λ+. Moreover, for N sufficiently large, we show that the eigenvectors associated to the largest eigenvalues are partially localized for λ>λ+, while they are completely delocalized for λ<λ+. Similar results hold for the lowest eigenvalues.

Untangling two systems of noncrossing curves - Matoušek, Jiří; Sedgwick, Eric; Tancer, Martin; Wagner, Uli (Israel Journal of Mathematics)
We consider two systems (α1, …, αm) and (β1, …,βn) of simple curves drawn on a compact two-dimensional surface M with boundary. Each αi and each βj is either an arc meeting the boundary of M at its two endpoints, or a closed curve. The αi are pairwise disjoint except for possibly sharing endpoints, and similarly for the βj. We want to “untangle” the βj from the ai by a self-homeomorphism of M; more precisely, we seek a homeomorphism φ:M→M fixing the boundary of M pointwise such that the total number of crossings of the ai with the φ(βj) is as small as possible. This problem is motivated by an application in the algorithmic theory of embeddings and 3-manifolds. We prove that if M is planar, i.e., a sphere with h ≥ 0 boundary components (“holes”), then O(mn) crossings can be achieved (independently of h), which is asymptotically tight, as an easy lower bound shows. In general, for an arbitrary (orientable or nonorientable) surface M with h holes and of (orientable or nonorientable) genus g ≥ 0, we obtain an O((m + n)4) upper bound, again independent of h and g. The proofs rely, among other things, on a result concerning simultaneous planar drawings of graphs by Erten and Kobourov.

A counterexample to the chain rule for conditional HILL entropy - Krenn, Stephan; Pietrzak, Krzysztof Z; Wadia, Akshay; Wichs, Daniel (Computational Complexity)
Most entropy notions H(.) like Shannon or min-entropy satisfy a chain rule stating that for random variables X,Z, and A we have H(X|Z,A)≥H(X|Z)−|A|. That is, by conditioning on A the entropy of X can decrease by at most the bitlength |A| of A. Such chain rules are known to hold for some computational entropy notions like Yao’s and unpredictability-entropy. For HILL entropy, the computational analogue of min-entropy, the chain rule is of special interest and has found many applications, including leakage-resilient cryptography, deterministic encryption, and memory delegation. These applications rely on restricted special cases of the chain rule. Whether the chain rule for conditional HILL entropy holds in general was an open problem for which we give a strong negative answer: we construct joint distributions (X,Z,A), where A is a distribution over a single bit, such that the HILL entropy H HILL (X|Z) is large but H HILL (X|Z,A) is basically zero. Our counterexample just makes the minimal assumption that NP⊈P/poly. Under the stronger assumption that injective one-way function exist, we can make all the distributions efficiently samplable. Finally, we show that some more sophisticated cryptographic objects like lossy functions can be used to sample a distribution constituting a counterexample to the chain rule making only a single invocation to the underlying object.

The complexity of deciding legality of a single step of magic: The gathering - Chatterjee, Krishnendu; Ibsen-Jensen, Rasmus
Magic: the Gathering is a game about magical combat for any number of players. Formally it is a zero-sum, imperfect information stochastic game that consists of a potentially unbounded number of steps. We consider the problem of deciding if a move is legal in a given single step of Magic. We show that the problem is (a) coNP-complete in general; and (b) in P if either of two small sets of cards are not used. Our lower bound holds even for single-player Magic games. The significant aspects of our results are as follows: First, in most real-life game problems, the task of deciding whether a given move is legal in a single step is trivial, and the computationally hard task is to find the best sequence of legal moves in the presence of multiple players. In contrast, quite uniquely our hardness result holds for single step and with only one-player. Second, we establish efficient algorithms for important special cases of Magic.

Use runtime verification to improve the quality of medical care practice - Jiang, Yu; Liu, Han; Kong, Hui; Wang, Rui; Hosseini, Mohamad; Sun, Jiaguang; Sha, Lui (Proceedings of the 38th International Conference on Software Engineering Companion)
Clinical guidelines and decision support systems (DSS) play an important role in daily practices of medicine. Many text-based guidelines have been encoded for work-flow simulation of DSS to automate health care. During the collaboration with Carle hospital to develop a DSS, we identify that, for some complex and life-critical diseases, it is highly desirable to automatically rigorously verify some complex temporal properties in guidelines, which brings new challenges to current simulation based DSS with limited support of automatical formal verification and real-time data analysis. In this paper, we conduct the first study on applying runtime verification to cooperate with current DSS based on real-time data. Within the proposed technique, a user-friendly domain specific language, named DRTV, is designed to specify vital real-time data sampled by medical devices and temporal properties originated from clinical guidelines. Some interfaces are developed for data acquisition and communication. Then, for medical practice scenarios described in DRTV model, we will automatically generate event sequences and runtime property verifier automata. If a temporal property violates, real-time warnings will be produced by the formal verifier and passed to medical DSS. We have used DRTV to specify different kinds of medical care scenarios, and applied the proposed technique to assist existing DSS. As presented in experiment results, in terms of warning detection, it outperforms the only use of DSS or human inspection, and improves the quality of clinical health care of hospital

Perfect-information stochastic games with generalized mean-payoff objectives - Chatterjee, Krishnendu; Doyen, Laurent
Graph games provide the foundation for modeling and synthesizing reactive processes. In the synthesis of stochastic reactive processes, the traditional model is perfect-information stochastic games, where some transitions of the game graph are controlled by two adversarial players, and the other transitions are executed probabilistically. We consider such games where the objective is the conjunction of several quantitative objectives (specified as mean-payoff conditions), which we refer to as generalized mean-payoff objectives. The basic decision problem asks for the existence of a finite-memory strategy for a player that ensures the generalized mean-payoff objective be satisfied with a desired probability against all strategies of the opponent. A special case of the decision problem is the almost-sure problem where the desired probability is 1. Previous results presented a semi-decision procedure for -approximations of the almost-sure problem. In this work, we show that both the almost-sure problem as well as the general basic decision problem are coNP-complete, significantly improving the previous results. Moreover, we show that in the case of 1-player stochastic games, randomized memoryless strategies are sufficient and the problem can be solved in polynomial time. In contrast, in two-player stochastic games, we show that even with randomized strategies exponential memory is required in general, and present a matching exponential upper bound. We also study the basic decision problem with infinite-memory strategies and present computational complexity results for the problem. Our results are relevant in the synthesis of stochastic reactive systems with multiple quantitative requirements.

Finding non-orientable surfaces in 3-manifolds - Burton, Benjamin; De Mesmay, Arnaud N; Wagner, Uli
We investigate the complexity of finding an embedded non-orientable surface of Euler genus g in a triangulated 3-manifold. This problem occurs both as a natural question in low-dimensional topology, and as a first non-trivial instance of embeddability of complexes into 3-manifolds. We prove that the problem is NP-hard, thus adding to the relatively few hardness results that are currently known in 3-manifold topology. In addition, we show that the problem lies in NP when the Euler genus g is odd, and we give an explicit algorithm in this case.

What is decidable about partially observable Markov decision processes with ω-regular objectives - Chatterjee, Krishnendu; Chmelik, Martin; Tracol, Mathieu (Journal of Computer and System Sciences)
We consider partially observable Markov decision processes (POMDPs) with ω-regular conditions specified as parity objectives. The class of ω-regular languages provides a robust specification language to express properties in verification, and parity objectives are canonical forms to express them. The qualitative analysis problem given a POMDP and a parity objective asks whether there is a strategy to ensure that the objective is satisfied with probability 1 (resp. positive probability). While the qualitative analysis problems are undecidable even for special cases of parity objectives, we establish decidability (with optimal complexity) for POMDPs with all parity objectives under finite-memory strategies. We establish optimal (exponential) memory bounds and EXPTIME-completeness of the qualitative analysis problems under finite-memory strategies for POMDPs with parity objectives. We also present a practical approach, where we design heuristics to deal with the exponential complexity, and have applied our implementation on a number of POMDP examples.

Optimal cost almost-sure reachability in POMDPs - Chatterjee, Krishnendu; Chmelik, Martin; Gupta, Raghav; Kanodia, Ayush (Artificial Intelligence)
We consider partially observable Markov decision processes (POMDPs) with a set of target states and an integer cost associated with every transition. The optimization objective we study asks to minimize the expected total cost of reaching a state in the target set, while ensuring that the target set is reached almost surely (with probability 1). We show that for integer costs approximating the optimal cost is undecidable. For positive costs, our results are as follows: (i) we establish matching lower and upper bounds for the optimal cost, both double exponential in the POMDP state space size; (ii) we show that the problem of approximating the optimal cost is decidable and present approximation algorithms developing on the existing algorithms for POMDPs with finite-horizon objectives. While the worst-case running time of our algorithm is double exponential, we also present efficient stopping criteria for the algorithm and show experimentally that it performs well in many examples of interest.

Quantitative interprocedural analysis - Chatterjee, Krishnendu; Pavlogiannis, Andreas; Velner, Yaron
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.

A symbolic SAT based algorithm for almost sure reachability with small strategies in pomdps - Chatterjee, Krishnendu; Chmelik, Martin; Davies, Jessica (Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence)
POMDPs are standard models for probabilistic planning problems, where an agent interacts with an uncertain environment. We study the problem of almost-sure reachability, where given a set of target states, the question is to decide whether there is a policy to ensure that the target set is reached with probability 1 (almost-surely). While in general the problem is EXPTIMEcomplete, in many practical cases policies with a small amount of memory suffice. Moreover, the existing solution to the problem is explicit, which first requires to construct explicitly an exponential reduction to a belief-support MDP. In this work, we first study the existence of observation-stationary strategies, which is NP-complete, and then small-memory strategies. We present a symbolic algorithm by an efficient encoding to SAT and using a SAT solver for the problem. We report experimental results demonstrating the scalability of our symbolic (SAT-based) approach. © 2016, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

Amplification on undirected population structures: Comets beat stars - Pavlogiannis, Andreas; Tkadlec, Josef; Chatterjee, Krishnendu; Nowak, Martin
The fixation probability is the probability that a new mutant introduced in a homogeneous population eventually takes over the entire population. The fixation probability is a fundamental quantity of natural selection, and known to depend on the population structure. Amplifiers of natural selection are population structures which increase the fixation probability of advantageous mutants, as compared to the baseline case of well-mixed populations. In this work we focus on symmetric population structures represented as undirected graphs. In the regime of undirected graphs, the strongest amplifier known has been the Star graph, and the existence of undirected graphs with stronger amplification properties has remained open for over a decade. In this work we present the Comet and Comet-swarm families of undirected graphs. We show that for a range of fitness values of the mutants, the Comet and Comet-swarm graphs have fixation probability strictly larger than the fixation probability of the Star graph, for fixed population size and at the limit of large populations, respectively.

Termination and worst-case analysis of recursive programs - Anonymous, 1; Anonymous, 2; Anonymous, 3
We study the problem of developing efficient approaches for proving termination of recursive programs with one-dimensional arrays. Ranking functions serve as a sound and complete approach for proving termination of non-recursive programs without array operations. First, we generalize ranking functions to the notion of measure functions, and prove that measure functions (i) provide a sound method to prove termination of recursive programs (with one-dimensional arrays), and (ii) is both sound and complete over recursive programs without array operations. Our second contribution is the synthesis of measure functions of specific forms in polynomial time. More precisely, we prove that (i) polynomial measure functions over recursive programs can be synthesized in polynomial time through Farkas’ Lemma and Handelman’s Theorem, and (ii) measure functions involving logarithm and exponentiation can be synthesized in polynomial time through abstraction of logarithmic or exponential terms and Handelman’s Theorem. A key application of our method is the worst-case analysis of recursive programs. While previous methods obtain worst-case polynomial bounds of the form O(n^k), where k is an integer, our polynomial time methods can synthesize bounds of the form O(n log n), as well as O(n^x), where x is not an integer. We show the applicability of our automated technique to obtain worst-case complexity of classical recursive algorithms such as (i) Merge-Sort, the divideand- conquer algorithm for the Closest-Pair problem, where we obtain O(n log n) worst-case bound, and (ii) Karatsuba’s algorithm for polynomial multiplication and Strassen’s algorithm for matrix multiplication, where we obtain O(n^x) bound, where x is not an integer and close to the best-known bounds for the respective algorithms. Finally, we present experimental results to demonstrate the effectiveness of our approach.

Average-case analysis of programs: Automated recurrence analysis for almost-linear bounds - Anonymous, 1; Anonymous, 2; Anonymous, 3
We consider the problem of developing automated techniques to aid the average-case complexity analysis of programs. Several classical textbook algorithms have quite efficient average-case complexity, whereas the corresponding worst-case bounds are either inefficient (e.g., QUICK-SORT), or completely ineffective (e.g., COUPONCOLLECTOR). Since the main focus of average-case analysis is to obtain efficient bounds, we consider bounds that are either logarithmic, linear, or almost-linear (O(log n), O(n), O(n · log n), respectively, where n represents the size of the input). Our main contribution is a sound approach for deriving such average-case bounds for randomized recursive programs. Our approach is efficient (a simple linear-time algorithm), and it is based on (a) the analysis of recurrence relations induced by randomized algorithms, and (b) a guess-and-check technique. Our approach can infer the asymptotically optimal average-case bounds for classical randomized algorithms, including RANDOMIZED-SEARCH, QUICKSORT, QUICK-SELECT, COUPON-COLLECTOR, where the worstcase bounds are either inefficient (such as linear as compared to logarithmic of average-case, or quadratic as compared to linear or almost-linear of average-case), or ineffective. We have implemented our approach, and the experimental results show that we obtain the bounds efficiently for various classical algorithms.

Arbitrarily strong amplifiers of natural selection - Pavlogiannis, Andreas; Tkadlec, Josef; Chatterjee, Krishnendu; Nowak, Martin

Strong amplifiers of natural selection - Pavlogiannis, Andreas; Tkadlec, Josef; Chatterjee, Krishnendu; Nowak, Martin

Data-centric dynamic partial order reduction - Anonymous, 1; Anonymous, 2; Anonymous, 3; Anonymous, 4
We present a new dynamic partial-order reduction method for stateless model checking of concurrent programs. A common approach for exploring program behaviors relies on enumerating the traces of the program, without storing the visited states (aka stateless exploration). As the number of distinct traces grows exponentially, dynamic partial-order reduction (DPOR) techniques have been successfully used to partition the space of traces into equivalence classes (Mazurkiewicz partitioning), with the goal of exploring only few representative traces from each class. We introduce a new equivalence on traces under sequential consistency semantics, which we call the observation equivalence. Two traces are observationally equivalent if every read event observes the same write event in both traces. While the traditional Mazurkiewicz equivalence is control-centric, our new definition is data-centric. We show that our observation equivalence is coarser than the Mazurkiewicz equivalence, and in many cases even exponentially coarser. We devise a DPOR exploration of the trace space, called data-centric DPOR, based on the observation equivalence. 1. For acyclic architectures, our algorithm is guaranteed to explore exactly one representative trace from each observation class, while spending polynomial time per class. Hence, our algorithm is optimal wrt the observation equivalence, and in several cases explores exponentially fewer traces than any enumerative method based on the Mazurkiewicz equivalence. 2. For cyclic architectures, we consider an equivalence between traces which is finer than the observation equivalence; but coarser than the Mazurkiewicz equivalence, and in some cases is exponentially coarser. Our data-centric DPOR algorithm remains optimal under this trace equivalence. Finally, we perform a basic experimental comparison between the existing Mazurkiewicz-based DPOR and our data-centric DPOR on a set of academic benchmarks. Our results show a significant reduction in both running time and the number of explored equivalence classes.

Self-organized control of an tendon driven arm by differential extrinsic plasticity - Martius, Georg S; Hostettler, Rafael; Knoll, Alois; Der, Ralf (Proceedings of the Artificial Life Conference 2016)
With the accelerated development of robot technologies, optimal control becomes one of the central themes of research. In traditional approaches, the controller, by its internal functionality, finds appropriate actions on the basis of the history of sensor values, guided by the goals, intentions, objectives, learning schemes, and so forth. The idea is that the controller controls the world---the body plus its environment---as reliably as possible. This paper focuses on new lines of self-organization for developmental robotics. We apply the recently developed differential extrinsic synaptic plasticity to a muscle-tendon driven arm-shoulder system from the Myorobotics toolkit. In the experiments, we observe a vast variety of self-organized behavior patterns: when left alone, the arm realizes pseudo-random sequences of different poses. By applying physical forces, the system can be entrained into definite motion patterns like wiping a table. Most interestingly, after attaching an object, the controller gets in a functional resonance with the object's internal dynamics, starting to shake spontaneously bottles half-filled with water or sensitively driving an attached pendulum into a circular mode. When attached to the crank of a wheel the neural system independently discovers how to rotate it. In this way, the robot discovers affordances of objects its body is interacting with.

Error-robust modes of the retinal population code - Prentice, Jason; Marre, Olivier; Ioffe, Mark; Loback, Adrianna; Tkacik, Gasper; Berry, Michael (PLoS Computational Biology)
Across the nervous system, certain population spiking patterns are observed far more frequently than others. A hypothesis about this structure is that these collective activity patterns function as population codewords–collective modes–carrying information distinct from that of any single cell. We investigate this phenomenon in recordings of ∼150 retinal ganglion cells, the retina’s output. We develop a novel statistical model that decomposes the population response into modes; it predicts the distribution of spiking activity in the ganglion cell population with high accuracy. We found that the modes represent localized features of the visual stimulus that are distinct from the features represented by single neurons. Modes form clusters of activity states that are readily discriminated from one another. When we repeated the same visual stimulus, we found that the same mode was robustly elicited. These results suggest that retinal ganglion cells’ collective signaling is endowed with a form of error-correcting code–a principle that may hold in brain areas beyond retina.

Data from: A sting in the spit: widespread cross-infection of multiple RNA viruses across wild and managed bees - Mcmahon, Dino; Fürst, Matthias; Caspar, Jesicca; Theodorou, Panagiotis; Brown, Mark; Paxton, Robert
Summary: Declining populations of bee pollinators are a cause of concern, with major repercussions for biodiversity loss and food security. RNA viruses associated with honeybees represent a potential threat to other insect pollinators, but the extent of this threat is poorly understood. This study aims to attain a detailed understanding of the current and ongoing risk of emerging infectious disease (EID) transmission between managed and wild pollinator species across a wide range of RNA viruses. Within a structured large-scale national survey across 26 independent sites, we quantify the prevalence and pathogen loads of multiple RNA viruses in co-occurring managed honeybee (Apis mellifera) and wild bumblebee (Bombus spp.) populations. We then construct models that compare virus prevalence between wild and managed pollinators. Multiple RNA viruses associated with honeybees are widespread in sympatric wild bumblebee populations. Virus prevalence in honeybees is a significant predictor of virus prevalence in bumblebees, but we remain cautious in speculating over the principle direction of pathogen transmission. We demonstrate species-specific differences in prevalence, indicating significant variation in disease susceptibility or tolerance. Pathogen loads within individual bumblebees may be high and in the case of at least one RNA virus, prevalence is higher in wild bumblebees than in managed honeybee populations. Our findings indicate widespread transmission of RNA viruses between managed and wild bee pollinators, pointing to an interconnected network of potential disease pressures within and among pollinator species. In the context of the biodiversity crisis, our study emphasizes the importance of targeting a wide range of pathogens and defining host associations when considering potential drivers of population decline.

Shedding light on the grey zone of speciation along a continuum of genomic divergence - Roux, Camille; Fraisse, Christelle; Romiguier, Jonathan; Anciaux, Youann; Galtier, Nicolas; Bierne, Nicolas (PLoS Biology)
Speciation results from the progressive accumulation of mutations that decrease the probability of mating between parental populations or reduce the fitness of hybrids—the so-called species barriers. The speciation genomic literature, however, is mainly a collection of case studies, each with its own approach and specificities, such that a global view of the gradual process of evolution from one to two species is currently lacking. Of primary importance is the prevalence of gene flow between diverging entities, which is central in most species concepts and has been widely discussed in recent years. Here, we explore the continuum of speciation thanks to a comparative analysis of genomic data from 61 pairs of populations/species of animals with variable levels of divergence. Gene flow between diverging gene pools is assessed under an approximate Bayesian computation (ABC) framework. We show that the intermediate "grey zone" of speciation, in which taxonomy is often controversial, spans from 0.5% to 2% of net synonymous divergence, irrespective of species life history traits or ecology. Thanks to appropriate modeling of among-locus variation in genetic drift and introgression rate, we clarify the status of the majority of ambiguous cases and uncover a number of cryptic species. Our analysis also reveals the high incidence in animals of semi-isolated species (when some but not all loci are affected by barriers to gene flow) and highlights the intrinsic difficulty, both statistical and conceptual, of delineating species in the grey zone of speciation.

Beyond the hypercube evolutionary accessibility of fitness landscapes with realistic mutational networks - Zagórski, Marcin P; Burda, Zdzisław; Wacław, Bartłomiej (PLoS Computational Biology)
Evolutionary pathways describe trajectories of biological evolution in the space of different variants of organisms (genotypes). The probability of existence and the number of evolutionary pathways that lead from a given genotype to a better-adapted genotype are important measures of accessibility of local fitness optima and the reproducibility of evolution. Both quantities have been studied in simple mathematical models where genotypes are represented as binary sequences of two types of basic units, and the network of permitted mutations between the genotypes is a hypercube graph. However, it is unclear how these results translate to the biologically relevant case in which genotypes are represented by sequences of more than two units, for example four nucleotides (DNA) or 20 amino acids (proteins), and the mutational graph is not the hypercube. Here we investigate accessibility of the best-adapted genotype in the general case of K > 2 units. Using computer generated and experimental fitness landscapes we show that accessibility of the global fitness maximum increases with K and can be much higher than for binary sequences. The increase in accessibility comes from the increase in the number of indirect trajectories exploited by evolution for higher K. As one of the consequences, the fraction of genotypes that are accessible increases by three orders of magnitude when the number of units K increases from 2 to 16 for landscapes of size N ∼ 106genotypes. This suggests that evolution can follow many different trajectories on such landscapes and the reconstruction of evolutionary pathways from experimental data might be an extremely difficult task.

Experimental game instructions - Hilbe, Christian; Hagel, Kristin; Milinski, Manfred
In the beginning of our experiment, subjects were asked to read a few pages on their computer screens that would explain the rules of the subsequent game. Here, we provide these instructions, translated from German.

Simulation study to test the robustness of ABC in face of recent times of divergence - Roux, Camille; Fraisse, Christelle; Romiguier, Jonathan; Anciaux, Youann; Galtier, Nicolas; Bierne, Nicolas

Accessions of surveyed individuals, geographic locations and summary statistics - Roux, Camille; Fraisse, Christelle; Romiguier, Jonathan; Anciaux, Youann; Galtier, Nicolas; Bierne, Nicolas

ZIP-archived directory containing all data and computer programs - Zagórski, Marcin P; Burda, Zdzisław; Wacław, Bartłomiej

Neurons equipped with intrinsic plasticity learn stimulus intensity statistics - Monk, Travis; Savin, Cristina; Lücke, Jörg
Experience constantly shapes neural circuits through a variety of plasticity mechanisms. While the functional roles of some plasticity mechanisms are well-understood, it remains unclear how changes in neural excitability contribute to learning. Here, we develop a normative interpretation of intrinsic plasticity (IP) as a key component of unsupervised learning. We introduce a novel generative mixture model that accounts for the class-specific statistics of stimulus intensities, and we derive a neural circuit that learns the input classes and their intensities. We will analytically show that inference and learning for our generative model can be achieved by a neural circuit with intensity-sensitive neurons equipped with a specific form of IP. Numerical experiments verify our analytical derivations and show robust behavior for artificial and natural stimuli. Our results link IP to non-trivial input statistics, in particular the statistics of stimulus intensities for classes to which a neuron is sensitive. More generally, our work paves the way toward new classification algorithms that are robust to intensity variations.

Elevated virulence of an emerging viral genotype as a driver of honeybee loss - Mcmahon, Dino; Natsopoulou, Myrsini; Doublet, Vincent; Fürst, Matthias; Weging, Silvio; Brown, Mark; Gogol Döring, Andreas; Paxton, Robert (Proceedings of the Royal Society of London Series B Biological Sciences)
Emerging infectious diseases (EIDs) have contributed significantly to the current biodiversity crisis, leading to widespread epidemics and population loss. Owing to genetic variation in pathogen virulence, a complete understanding of species decline requires the accurate identification and characterization of EIDs. We explore this issue in the Western honeybee, where increasing mortality of populations in the Northern Hemisphere has caused major concern. Specifically, we investigate the importance of genetic identity of the main suspect in mortality, deformed wing virus (DWV), in driving honeybee loss. Using laboratory experiments and a systematic field survey, we demonstrate that an emerging DWV genotype (DWV-B) is more virulent than the established DWV genotype (DWV-A) and is widespread in the landscape. Furthermore, we show in a simple model that colonies infected with DWV-B collapse sooner than colonies infected with DWV-A. We also identify potential for rapid DWV evolution by revealing extensive genome-wide recombination in vivo. The emergence of DWV-B in naive honeybee populations, including via recombination with DWV-A, could be of significant ecological and economic importance. Our findings emphasize that knowledge of pathogen genetic identity and diversity is critical to understanding drivers of species decline.

Data from: Elevated virulence of an emerging viral genotype as a driver of honeybee loss - Mcmahon, Dino; Natsopoulou, Myrsini; Doublet, Vincent; Fürst, Matthias; Weging, Silvio; Brown, Mark; Gogol Döring, Andreas; Paxton, Robert
Emerging infectious diseases (EIDs) have contributed significantly to the current biodiversity crisis, leading to widespread epidemics and population loss. Owing to genetic variation in pathogen virulence, a complete understanding of species decline requires the accurate identification and characterization of EIDs. We explore this issue in the Western honeybee, where increasing mortality of populations in the Northern Hemisphere has caused major concern. Specifically, we investigate the importance of genetic identity of the main suspect in mortality, deformed wing virus (DWV), in driving honeybee loss. Using laboratory experiments and a systematic field survey, we demonstrate that an emerging DWV genotype (DWV-B) is more virulent than the established DWV genotype (DWV-A) and is widespread in the landscape. Furthermore, we show in a simple model that colonies infected with DWV-B collapse sooner than colonies infected with DWV-A. We also identify potential for rapid DWV evolution by revealing extensive genome-wide recombination in vivo. The emergence of DWV-B in naive honeybee populations, including via recombination with DWV-A, could be of significant ecological and economic importance. Our findings emphasize that knowledge of pathogen genetic identity and diversity is critical to understanding drivers of species decline.

Asymmetric power boosts extortion in an economic experiment - Hilbe, Christian; Hagel, Kristin; Milinski, Manfred (PLoS One)
Direct reciprocity is a major mechanism for the evolution of cooperation. Several classical studies have suggested that humans should quickly learn to adopt reciprocal strategies to establish mutual cooperation in repeated interactions. On the other hand, the recently discovered theory of ZD strategies has found that subjects who use extortionate strategies are able to exploit and subdue cooperators. Although such extortioners have been predicted to succeed in any population of adaptive opponents, theoretical follow-up studies questioned whether extortion can evolve in reality. However, most of these studies presumed that individuals have similar strategic possibilities and comparable outside options, whereas asymmetries are ubiquitous in real world applications. Here we show with a model and an economic experiment that extortionate strategies readily emerge once subjects differ in their strategic power. Our experiment combines a repeated social dilemma with asymmetric partner choice. In our main treatment there is one randomly chosen group member who is unilaterally allowed to exchange one of the other group members after every ten rounds of the social dilemma. We find that this asymmetric replacement opportunity generally promotes cooperation, but often the resulting payoff distribution reflects the underlying power structure. Almost half of the subjects in a better strategic position turn into extortioners, who quickly proceed to exploit their peers. By adapting their cooperation probabilities consistent with ZD theory, extortioners force their co-players to cooperate without being similarly cooperative themselves. Comparison to non-extortionate players under the same conditions indicates a substantial net gain to extortion. Our results thus highlight how power asymmetries can endanger mutually beneficial interactions, and transform them into exploitative relationships. In particular, our results indicate that the extortionate strategies predicted from ZD theory could play a more prominent role in our daily interactions than previously thought.

Beyond the French flag model: Exploiting spatial and gene regulatory interactions for positional information - Hillenbrand, Patrick; Gerland, Ulrich; Tkacik, Gasper (PLoS One)
A crucial step in the early development of multicellular organisms involves the establishment of spatial patterns of gene expression which later direct proliferating cells to take on different cell fates. These patterns enable the cells to infer their global position within a tissue or an organism by reading out local gene expression levels. The patterning system is thus said to encode positional information, a concept that was formalized recently in the framework of information theory. Here we introduce a toy model of patterning in one spatial dimension, which can be seen as an extension of Wolpert's paradigmatic "French Flag" model, to patterning by several interacting, spatially coupled genes subject to intrinsic and extrinsic noise. Our model, a variant of an Ising spin system, allows us to systematically explore expression patterns that optimally encode positional information. We find that optimal patterning systems use positional cues, as in the French Flag model, together with gene-gene interactions to generate combinatorial codes for position which we call "Counter" patterns. Counter patterns can also be stabilized against noise and variations in system size or morphogen dosage by longer-range spatial interactions of the type invoked in the Turing model. The simple setup proposed here qualitatively captures many of the experimentally observed properties of biological patterning systems and allows them to be studied in a single, theoretically consistent framework.

Genetic manipulation of glycogen allocation affects replicative lifespan in E coli - Boehm, Alex; Arnoldini, Markus; Bergmiller, Tobias; Röösli, Thomas; Bigosch, Colette; Ackermann, Martin (PLoS Genetics)
In bacteria, replicative aging manifests as a difference in growth or survival between the two cells emerging from division. One cell can be regarded as an aging mother with a decreased potential for future survival and division, the other as a rejuvenated daughter. Here, we aimed at investigating some of the processes involved in aging in the bacterium Escherichia coli, where the two types of cells can be distinguished by the age of their cell poles. We found that certain changes in the regulation of the carbohydrate metabolism can affect aging. A mutation in the carbon storage regulator gene, csrA, leads to a dramatically shorter replicative lifespan; csrA mutants stop dividing once their pole exceeds an age of about five divisions. These old-pole cells accumulate glycogen at their old cell poles; after their last division, they do not contain a chromosome, presumably because of spatial exclusion by the glycogen aggregates. The new-pole daughters produced by these aging mothers are born young; they only express the deleterious phenotype once their pole is old. These results demonstrate how manipulations of nutrient allocation can lead to the exclusion of the chromosome and limit replicative lifespan in E. coli, and illustrate how mutations can have phenotypic effects that are specific for cells with old poles. This raises the question how bacteria can avoid the accumulation of such mutations in their genomes over evolutionary times, and how they can achieve the long replicative lifespans that have recently been reported.

Computation of positional information in an Ising model - Hillenbrand, Patrick; Gerland, Ulrich; Tkačik, Gašper
The effect of noise in the input field on an Ising model is approximated. Furthermore, methods to compute positional information in an Ising model by transfer matrices and Monte Carlo sampling are outlined.

Quantification of the growth rate reduction as a consequence of age-specific mortality - Boehm, Alex; Arnoldini, Markus; Bergmiller, Tobias; Röösli, Thomas; Bigosch, Colette; Ackermann, Martin

Error bound on an estimator of position - Hillenbrand, Patrick; Gerland, Ulrich; Tkačik, Gašper
A lower bound on the error of a positional estimator with limited positional information is derived.

Computation of positional information in a discrete morphogen field - Hillenbrand, Patrick; Gerland, Ulrich; Tkačik, Gašper
The positional information in a discrete morphogen field with Gaussian noise is computed.

Experimental data - Hilbe, Christian; Hagel, Kristin; Milinski, Manfred
The raw data file containing the experimental decisions of all our study subjects.

Rangefinder: A semisynthetic FRET sensor design algorithm - Mitchell, Joshua; Whitfield, Jason; Zhang, William; Henneberger, Christian; Janovjak, Harald L; O'Mara, Megan; Jackson, Colin (ACS SENSORS)
Optical sensors based on the phenomenon of Förster resonance energy transfer (FRET) are powerful tools that have advanced the study of small molecules in biological systems. However, sensor construction is not trivial and often requires multiple rounds of engineering or an ability to screen large numbers of variants. A method that would allow the accurate rational design of FRET sensors would expedite the production of biologically useful sensors. Here, we present Rangefinder, a computational algorithm that allows rapid in silico screening of dye attachment sites in a ligand-binding protein for the conjugation of a dye molecule to act as a Förster acceptor for a fused fluorescent protein. We present three ratiometric fluorescent sensors designed with Rangefinder, including a maltose sensor with a dynamic range of >300% and the first sensors for the most abundant sialic acid in human cells, N-acetylneuraminic acid. Provided a ligand-binding protein exists, it is our expectation that this model will facilitate the design of an optical sensor for any small molecule of interest.

High performance computing at IST Austria: Modelling the human hippocampus - Schlögl, Alois; Stadlbauer, Stephan (AHPC16 - Austrian HPC Meeting 2016)

Dynamic resource allocation games - Avni, Guy; Henzinger, Thomas A; Kupferman, Orna
In resource allocation games, selfish players share resources that are needed in order to fulfill their objectives. The cost of using a resource depends on the load on it. In the traditional setting, the players make their choices concurrently and in one-shot. That is, a strategy for a player is a subset of the resources. We introduce and study dynamic resource allocation games. In this setting, the game proceeds in phases. In each phase each player chooses one resource. A scheduler dictates the order in which the players proceed in a phase, possibly scheduling several players to proceed concurrently. The game ends when each player has collected a set of resources that fulfills his objective. The cost for each player then depends on this set as well as on the load on the resources in it – we consider both congestion and cost-sharing games. We argue that the dynamic setting is the suitable setting for many applications in practice. We study the stability of dynamic resource allocation games, where the appropriate notion of stability is that of subgame perfect equilibrium, study the inefficiency incurred due to selfish behavior, and also study problems that are particular to the dynamic setting, like constraints on the order in which resources can be chosen or the problem of finding a scheduler that achieves stability.

Adaptation to parasites and costs of parasite resistance in mutator and nonmutator bacteria - Wielgoss, Sébastien; Bergmiller, Tobias; Bischofberger, Anna M.; Hall, Alex R. (Molecular Biology and Evolution)
Parasitism creates selection for resistance mechanisms in host populations and is hypothesized to promote increased host evolvability. However, the influence of these traits on host evolution when parasites are no longer present is unclear. We used experimental evolution and whole-genome sequencing of Escherichia coli to determine the effects of past and present exposure to parasitic viruses (phages) on the spread of mutator alleles, resistance, and bacterial competitive fitness. We found that mutator alleles spread rapidly during adaptation to any of four different phage species, and this pattern was even more pronounced with multiple phages present simultaneously. However, hypermutability did not detectably accelerate adaptation in the absence of phages and recovery of fitness costs associated with resistance. Several lineages evolved phage resistance through elevated mucoidy, and during subsequent evolution in phage-free conditions they rapidly reverted to nonmucoid, phage-susceptible phenotypes. Genome sequencing revealed that this phenotypic reversion was achieved by additional genetic changes rather than by genotypic reversion of the initial resistance mutations. Insertion sequence (IS) elements played a key role in both the acquisition of resistance and adaptation in the absence of parasites; unlike single nucleotide polymorphisms, IS insertions were not more frequent in mutator lineages. Our results provide a genetic explanation for rapid reversion of mucoidy, a phenotype observed in other bacterial species including human pathogens. Moreover, this demonstrates that the types of genetic change underlying adaptation to fitness costs, and consequently the impact of evolvability mechanisms such as increased point-mutation rates, depend critically on the mechanism of resistance.

Immunogold protein localization on grid-glued freeze-fracture replicas - Harada, Harumi; Shigemoto, Ryuichi (High-Resolution Imaging of Cellular Proteins)
Immunogold labeling of freeze-fracture replicas has recently been used for high-resolution visualization of protein localization in electron microscopy. This method has higher labeling efficiency than conventional immunogold methods for membrane molecules allowing precise quantitative measurements. However, one of the limitations of freeze-fracture replica immunolabeling is difficulty in keeping structural orientation and identifying labeled profiles in complex tissues like brain. The difficulty is partly due to fragmentation of freeze-fracture replica preparations during labeling procedures and limited morphological clues on the replica surface. To overcome these issues, we introduce here a grid-glued replica method combined with SEM observation. This method allows histological staining before dissolving the tissue and easy handling of replicas during immunogold labeling, and keeps the whole replica surface intact without fragmentation. The procedure described here is also useful for matched double-replica analysis allowing further identification of labeled profiles in corresponding P-face and E-face.

Selective barriers to horizontal gene transfer - Acar, Hande
Horizontal gene transfer (HGT), the lateral acquisition of genes across existing species boundaries, is a major evolutionary force shaping microbial genomes that facilitates adaptation to new environments as well as resistance to antimicrobial drugs. As such, understanding the mechanisms and constraints that determine the outcomes of HGT events is crucial to understand the dynamics of HGT and to design better strategies to overcome the challenges that originate from it. Following the insertion and expression of a newly transferred gene, the success of an HGT event will depend on the fitness effect it has on the recipient (host) cell. Therefore, predicting the impact of HGT on the genetic composition of a population critically depends on the distribution of fitness effects (DFE) of horizontally transferred genes. However, to date, we have little knowledge of the DFE of newly transferred genes, and hence little is known about the shape and scale of this distribution. It is particularly important to better understand the selective barriers that determine the fitness effects of newly transferred genes. In spite of substantial bioinformatics efforts to identify horizontally transferred genes and selective barriers, a systematic experimental approach to elucidate the roles of different selective barriers in defining the fate of a transfer event has largely been absent. Similarly, although the fact that environment might alter the fitness effect of a horizontally transferred gene may seem obvious, little attention has been given to it in a systematic experimental manner. In this study, we developed a systematic experimental approach that consists of transferring 44 arbitrarily selected Salmonella typhimurium orthologous genes into an Escherichia coli host, and estimating the fitness effects of these transferred genes at a constant expression level by performing competition assays against the wild type. In chapter 2, we performed one-to-one competition assays between a mutant strain carrying a transferred gene and the wild type strain. By using flow cytometry we estimated selection coefficients for the transferred genes with a precision level of 10-3,and obtained the DFE of horizontally transferred genes. We then investigated if these fitness effects could be predicted by any of the intrinsic properties of the genes, namely, functional category, degree of complexity (protein-protein interactions), GC content, codon usage and length. Our analyses revealed that the functional category and length of the genes act as potential selective barriers. Finally, using the same procedure with the endogenous E. coli orthologs of these 44 genes, we demonstrated that gene dosage is the most prominent selective barrier to HGT. In chapter 3, using the same set of genes we investigated the role of environment on the success of HGT events. Under six different environments with different levels of stress we performed more complex competition assays, where we mixed all 44 mutant strains carrying transferred genes with the wild type strain. To estimate the fitness effects of genes relative to wild type we used next generation sequencing. We found that the DFEs of horizontally transferred genes are highly dependent on the environment, with abundant gene–by-environment interactions. Furthermore, we demonstrated a relationship between average fitness effect of a gene across all environments and its environmental variance, and thus its predictability. Finally, in spite of the fitness effects of genes being highly environment-dependent, we still observed a common shape of DFEs across all tested environments.

Approximation and convergence of the intrinsic volume - Edelsbrunner, Herbert; Pausinger, Florian (Advances in Mathematics)
We introduce a modification of the classic notion of intrinsic volume using persistence moments of height functions. Evaluating the modified first intrinsic volume on digital approximations of a compact body with smoothly embedded boundary in Rn, we prove convergence to the first intrinsic volume of the body as the resolution of the approximation improves. We have weaker results for the other modified intrinsic volumes, proving they converge to the corresponding intrinsic volumes of the n-dimensional unit ball.

Studying the complexities of transcriptional regulation - Rieckh, Georg
The process of gene expression is central to the modern understanding of how cellular systems function. In this process, a special kind of regulatory proteins, called transcription factors, are important to determine how much protein is produced from a given gene. As biological information is transmitted from transcription factor concentration to mRNA levels to amounts of protein, various sources of noise arise and pose limits to the fidelity of intracellular signaling. This thesis concerns itself with several aspects of stochastic gene expression: (i) the mathematical description of complex promoters responsible for the stochastic production of biomolecules, (ii) fundamental limits to information processing the cell faces due to the interference from multiple fluctuating signals, (iii) how the presence of gene expression noise influences the evolution of regulatory sequences, (iv) and tools for the experimental study of origins and consequences of cell-cell heterogeneity, including an application to bacterial stress response systems.

Optical functionalization of human class A orphan G-protein coupled receptors - Morri, Maurizio

Quantitative analysis of haptotactic cell migration - Schwarz, Jan
Directed cell migration is a hallmark feature, present in almost all multi-cellular organisms. Despite its importance, basic questions regarding force transduction or directional sensing are still heavily investigated. Directed migration of cells guided by immobilized guidance cues - haptotaxis - occurs in key-processes, such as embryonic development and immunity (Middleton et al., 1997; Nguyen et al., 2000; Thiery, 1984; Weber et al., 2013). Immobilized guidance cues comprise adhesive ligands, such as collagen and fibronectin (Barczyk et al., 2009), or chemokines - the main guidance cues for migratory leukocytes (Middleton et al., 1997; Weber et al., 2013). While adhesive ligands serve as attachment sites guiding cell migration (Carter, 1965), chemokines instruct haptotactic migration by inducing adhesion to adhesive ligands and directional guidance (Rot and Andrian, 2004; Schumann et al., 2010). Quantitative analysis of the cellular response to immobilized guidance cues requires in vitro assays that foster cell migration, offer accurate control of the immobilized cues on a subcellular scale and in the ideal case closely reproduce in vivo conditions. The exploration of haptotactic cell migration through design and employment of such assays represents the main focus of this work. Dendritic cells (DCs) are leukocytes, which after encountering danger signals such as pathogens in peripheral organs instruct naïve T-cells and consequently the adaptive immune response in the lymph node (Mellman and Steinman, 2001). To reach the lymph node from the periphery, DCs follow haptotactic gradients of the chemokine CCL21 towards lymphatic vessels (Weber et al., 2013). Questions about how DCs interpret haptotactic CCL21 gradients have not yet been addressed. The main reason for this is the lack of an assay that offers diverse haptotactic environments, hence allowing the study of DC migration as a response to different signals of immobilized guidance cue. In this work, we developed an in vitro assay that enables us to quantitatively assess DC haptotaxis, by combining precisely controllable chemokine photo-patterning with physically confining migration conditions. With this tool at hand, we studied the influence of CCL21 gradient properties and concentration on DC haptotaxis. We found that haptotactic gradient sensing depends on the absolute CCL21 concentration in combination with the local steepness of the gradient. Our analysis suggests that the directionality of migrating DCs is governed by the signal-to-noise ratio of CCL21 binding to its receptor CCR7. Moreover, the haptotactic CCL21 gradient formed in vivo provides an optimal shape for DCs to recognize haptotactic guidance cue. By reconstitution of the CCL21 gradient in vitro we were also able to study the influence of CCR7 signal termination on DC haptotaxis. To this end, we used DCs lacking the G-protein coupled receptor kinase GRK6, which is responsible for CCL21 induced CCR7 receptor phosphorylation and desensitization (Zidar et al., 2009). We found that CCR7 desensitization by GRK6 is crucial for maintenance of haptotactic CCL21 gradient sensing in vitro and confirm those observations in vivo. In the context of the organism, immobilized haptotactic guidance cues often coincide and compete with soluble chemotactic guidance cues. During wound healing, fibroblasts are exposed and influenced by adhesive cues and soluble factors at the same time (Wu et al., 2012; Wynn, 2008). Similarly, migrating DCs are exposed to both, soluble chemokines (CCL19 and truncated CCL21) inducing chemotactic behavior as well as the immobilized CCL21. To quantitatively assess these complex coinciding immobilized and soluble guidance cues, we implemented our chemokine photo-patterning technique in a microfluidic system allowing for chemotactic gradient generation. To validate the assay, we observed DC migration in competing CCL19/CCL21 environments. Adhesiveness guided haptotaxis has been studied intensively over the last century. However, quantitative studies leading to conceptual models are largely missing, again due to the lack of a precisely controllable in vitro assay. A requirement for such an in vitro assay is that it must prevent any uncontrolled cell adhesion. This can be accomplished by stable passivation of the surface. In addition, controlled adhesion must be sustainable, quantifiable and dose dependent in order to create homogenous gradients. Therefore, we developed a novel covalent photo-patterning technique satisfying all these needs. In combination with a sustainable poly-vinyl alcohol (PVA) surface coating we were able to generate gradients of adhesive cue to direct cell migration. This approach allowed us to characterize the haptotactic migratory behavior of zebrafish keratocytes in vitro. Furthermore, defined patterns of adhesive cue allowed us to control for cell shape and growth on a subcellular scale.

Theoretical foundations of multi-task lifelong learning - Pentina, Anastasia
Traditionally machine learning has been focusing on the problem of solving a single task in isolation. While being quite well understood, this approach disregards an important aspect of human learning: when facing a new problem, humans are able to exploit knowledge acquired from previously learned tasks. Intuitively, access to several problems simultaneously or sequentially could also be advantageous for a machine learning system, especially if these tasks are closely related. Indeed, results of many empirical studies have provided justification for this intuition. However, theoretical justifications of this idea are rather limited. The focus of this thesis is to expand the understanding of potential benefits of information transfer between several related learning problems. We provide theoretical analysis for three scenarios of multi-task learning - multiple kernel learning, sequential learning and active task selection. We also provide a PAC-Bayesian perspective on lifelong learning and investigate how the task generation process influences the generalization guarantees in this scenario. In addition, we show how some of the obtained theoretical results can be used to derive principled multi-task and lifelong learning algorithms and illustrate their performance on various synthetic and real-world datasets.

Algorithms for partially observable markov decision processes - Chmelik, Martin
We study partially observable Markov decision processes (POMDPs) with objectives used in verification and artificial intelligence. The qualitative analysis problem given a POMDP and an objective asks whether there is a strategy (policy) to ensure that the objective is satisfied almost surely (with probability 1), resp. with positive probability (with probability greater than 0). For POMDPs with limit-average payoff, where a reward value in the interval [0,1] is associated to every transition, and the payoff of an infinite path is the long-run average of the rewards, we consider two types of path constraints: (i) a quantitative limit-average constraint defines the set of paths where the payoff is at least a given threshold L1 = 1. Our main results for qualitative limit-average constraint under almost-sure winning are as follows: (i) the problem of deciding the existence of a finite-memory controller is EXPTIME-complete; and (ii) the problem of deciding the existence of an infinite-memory controller is undecidable. For quantitative limit-average constraints we show that the problem of deciding the existence of a finite-memory controller is undecidable. We present a prototype implementation of our EXPTIME algorithm. For POMDPs with w-regular conditions specified as parity objectives, while the qualitative analysis problems are known to be undecidable even for very special case of parity objectives, we establish decidability (with optimal complexity) of the qualitative analysis problems for POMDPs with parity objectives under finite-memory strategies. We establish optimal (exponential) memory bounds and EXPTIME-completeness of the qualitative analysis problems under finite-memory strategies for POMDPs with parity objectives. Based on our theoretical algorithms we also present a practical approach, where we design heuristics to deal with the exponential complexity, and have applied our implementation on a number of well-known POMDP examples for robotics applications. For POMDPs with a set of target states and an integer cost associated with every transition, we study the optimization objective that asks to minimize the expected total cost of reaching a state in the target set, while ensuring that the target set is reached almost surely. We show that for general integer costs approximating the optimal cost is undecidable. For positive costs, our results are as follows: (i) we establish matching lower and upper bounds for the optimal cost, both double and exponential in the POMDP state space size; (ii) we show that the problem of approximating the optimal cost is decidable and present approximation algorithms that extend existing algorithms for POMDPs with finite-horizon objectives. We show experimentally that it performs well in many examples of interest. We study more deeply the problem of almost-sure reachability, where given a set of target states, the question is to decide whether there is a strategy to ensure that the target set is reached almost surely. While in general the problem EXPTIME-complete, in many practical cases strategies with a small amount of memory suffice. Moreover, the existing solution to the problem is explicit, which first requires to construct explicitly an exponential reduction to a belief-support MDP. We first study the existence of observation-stationary strategies, which is NP-complete, and then small-memory strategies. We present a symbolic algorithm by an efficient encoding to SAT and using a SAT solver for the problem. We report experimental results demonstrating the scalability of our symbolic (SAT-based) approach. Decentralized POMDPs (DEC-POMDPs) extend POMDPs to a multi-agent setting, where several agents operate in an uncertain environment independently to achieve a joint objective. In this work we consider Goal DEC-POMDPs, where given a set of target states, the objective is to ensure that the target set is reached with minimal cost. We consider the indefinite-horizon (infinite-horizon with either discounted-sum, or undiscounted-sum, where absorbing goal states have zero-cost) problem. We present a new and novel method to solve the problem that extends methods for finite-horizon DEC-POMDPs and the real-time dynamic programming approach for POMDPs. We present experimental results on several examples, and show that our approach presents promising results. In the end we present a short summary of a few other results related to verification of MDPs and POMDPs.

Eliminating higher-multiplicity intersections: an r-fold Whitney trick for the topological Tverberg conjecture - Mabillard, Isaac
Motivated by topological Tverberg-type problems in topological combinatorics and by classical results about embeddings (maps without double points), we study the question whether a finite simplicial complex K can be mapped into Rd without triple, quadruple, or, more generally, r-fold points (image points with at least r distinct preimages), for a given multiplicity r ≤ 2. In particular, we are interested in maps f : K → Rd that have no global r -fold intersection points, i.e., no r -fold points with preimages in r pairwise disjoint simplices of K , and we seek necessary and sufficient conditions for the existence of such maps. We present higher-multiplicity analogues of several classical results for embeddings, in particular of the completeness of the Van Kampen obstruction for embeddability of k -dimensional complexes into R2k , k ≥ 3. Speciffically, we show that under suitable restrictions on the dimensions(viz., if dimK = (r ≥ 1)k and d = rk \ for some k ≥ 3), a well-known deleted product criterion (DPC ) is not only necessary but also sufficient for the existence of maps without global r -fold points. Our main technical tool is a higher-multiplicity version of the classical Whitney trick , by which pairs of isolated r -fold points of opposite sign can be eliminated by local modiffications of the map, assuming codimension d – dimK ≥ 3. An important guiding idea for our work was that suffciency of the DPC, together with an old result of Özaydin's on the existence of equivariant maps, might yield an approach to disproving the remaining open cases of the the long-standing topological Tverberg conjecture , i.e., to construct maps from the N -simplex σN to Rd without r-Tverberg points when r not a prime power and N = (d + 1)(r – 1). Unfortunately, our proof of the sufficiency of the DPC requires codimension d – dimK ≥ 3, which is not satisfied for K = σN . In 2015, Frick [16] found a very elegant way to overcome this \codimension 3 obstacle" and to construct the first counterexamples to the topological Tverberg conjecture for all parameters(d; r ) with d ≥ 3r + 1 and r not a prime power, by a reduction1 to a suitable lower-dimensional skeleton, for which the codimension 3 restriction is satisfied and maps without r -Tverberg points exist by Özaydin's result and sufficiency of the DPC. In this thesis, we present a different construction (which does not use the constraint method) that yields counterexamples for d ≥ 3r , r not a prime power.

Symmetric spike timing-dependent plasticity at CA3–CA3 synapses optimizes storage and recall in autoassociative networks - Mishra, Rajiv Kumar; Kim, Sooyun; Guzmán, José; Jonas, Peter M (Nature Communications)
CA3–CA3 recurrent excitatory synapses are thought to play a key role in memory storage and pattern completion. Whether the plasticity properties of these synapses are consistent with their proposed network functions remains unclear. Here, we examine the properties of spike timing-dependent plasticity (STDP) at CA3–CA3 synapses. Low-frequency pairing of excitatory postsynaptic potentials (EPSPs) and action potentials (APs) induces long-term potentiation (LTP), independent of temporal order. The STDP curve is symmetric and broad (half-width ~150 ms). Consistent with these STDP induction properties, AP–EPSP sequences lead to supralinear summation of spine [Ca2+] transients. Furthermore, afterdepolarizations (ADPs) following APs efficiently propagate into dendrites of CA3 pyramidal neurons, and EPSPs summate with dendritic ADPs. In autoassociative network models, storage and recall are more robust with symmetric than with asymmetric STDP rules. Thus, a specialized STDP induction rule allows reliable storage and recall of information in the hippocampal CA3 network.

Synaptic plasticity rules at CA3-CA3 recurrent synapses in hippocampus - Mishra, Rajiv Kumar
CA3 pyramidal neurons are thought to pay a key role in memory storage and pattern completion by activity-dependent synaptic plasticity between CA3-CA3 recurrent excitatory synapses. To examine the induction rules of synaptic plasticity at CA3-CA3 synapses, we performed whole-cell patch-clamp recordings in acute hippocampal slices from rats (postnatal 21-24 days) at room temperature. Compound excitatory postsynaptic potentials (ESPSs) were recorded by tract stimulation in stratum oriens in the presence of 10 µM gabazine. High-frequency stimulation (HFS) induced N-methyl-D-aspartate (NMDA) receptor-dependent long-term potentiation (LTP). Although LTP by HFS did not requier postsynaptic spikes, it was blocked by Na+-channel blockers suggesting that local active processes (e.g.) dendritic spikes) may contribute to LTP induction without requirement of a somatic action potential (AP). We next examined the properties of spike timing-dependent plasticity (STDP) at CA3-CA3 synapses. Unexpectedly, low-frequency pairing of EPSPs and backpropagated action potentialy (bAPs) induced LTP, independent of temporal order. The STDP curve was symmetric and broad, with a half-width of ~150 ms. Consistent with these specific STDP induction properties, post-presynaptic sequences led to a supralinear summation of spine [Ca2+] transients. Furthermore, in autoassociative network models, storage and recall was substantially more robust with symmetric than with asymmetric STDP rules. In conclusion, we found associative forms of LTP at CA3-CA3 recurrent collateral synapses with distinct induction rules. LTP induced by HFS may be associated with dendritic spikes. In contrast, low frequency pairing of pre- and postsynaptic activity induced LTP only if EPSP-AP were temporally very close. Together, these induction mechanisms of synaptiic plasticity may contribute to memory storage in the CA3-CA3 microcircuit at different ranges of activity.

Evolutionary proccesses in variable emvironments - Novak, Sebastian
Natural environments are never constant but subject to spatial and temporal change on all scales, increasingly so due to human activity. Hence, it is crucial to understand the impact of environmental variation on evolutionary processes. In this thesis, I present three topics that share the common theme of environmental variation, yet illustrate its effect from different perspectives. First, I show how a temporally fluctuating environment gives rise to second-order selection on a modifier for stress-induced mutagenesis. Without fluctuations, when populations are adapted to their environment, mutation rates are minimized. I argue that a stress-induced mutator mechanism may only be maintained if the population is repeatedly subjected to diverse environmental challenges, and I outline implications of the presented results to antibiotic treatment strategies. Second, I discuss my work on the evolution of dispersal. Besides reproducing known results about the effect of heterogeneous habitats on dispersal, it identifies spatial changes in dispersal type frequencies as a source for selection for increased propensities to disperse. This concept contains effects of relatedness that are known to promote dispersal, and I explain how it identifies other forces selecting for dispersal and puts them on a common scale. Third, I analyse genetic variances of phenotypic traits under multivariate stabilizing selection. For the case of constant environments, I generalize known formulae of equilibrium variances to multiple traits and discuss how the genetic variance of a focal trait is influenced by selection on background traits. I conclude by presenting ideas and preliminary work aiming at including environmental fluctuations in the form of moving trait optima into the model.

Automatic synthesis of synchronisation primitives for concurrent programs - Tarrach, Thorsten
In this thesis we present a computer-aided programming approach to concurrency. Our approach helps the programmer by automatically fixing concurrency-related bugs, i.e. bugs that occur when the program is executed using an aggressive preemptive scheduler, but not when using a non-preemptive (cooperative) scheduler. Bugs are program behaviours that are incorrect w.r.t. a specification. We consider both user-provided explicit specifications in the form of assertion statements in the code as well as an implicit specification. The implicit specification is inferred from the non-preemptive behaviour. Let us consider sequences of calls that the program makes to an external interface. The implicit specification requires that any such sequence produced under a preemptive scheduler should be included in the set of sequences produced under a non-preemptive scheduler. We consider several semantics-preserving fixes that go beyond atomic sections typically explored in the synchronisation synthesis literature. Our synthesis is able to place locks, barriers and wait-signal statements and last, but not least reorder independent statements. The latter may be useful if a thread is released to early, e.g., before some initialisation is completed. We guarantee that our synthesis does not introduce deadlocks and that the synchronisation inserted is optimal w.r.t. a given objective function. We dub our solution trace-based synchronisation synthesis and it is loosely based on counterexample-guided inductive synthesis (CEGIS). The synthesis works by discovering a trace that is incorrect w.r.t. the specification and identifying ordering constraints crucial to trigger the specification violation. Synchronisation may be placed immediately (greedy approach) or delayed until all incorrect traces are found (non-greedy approach). For the non-greedy approach we construct a set of global constraints over synchronisation placements. Each model of the global constraints set corresponds to a correctness-ensuring synchronisation placement. The placement that is optimal w.r.t. the given objective function is chosen as the synchronisation solution. We evaluate our approach on a number of realistic (albeit simplified) Linux device-driver benchmarks. The benchmarks are versions of the drivers with known concurrency-related bugs. For the experiments with an explicit specification we added assertions that would detect the bugs in the experiments. Device drivers lend themselves to implicit specification, where the device and the operating system are the external interfaces. Our experiments demonstrate that our synthesis method is precise and efficient. We implemented objective functions for coarse-grained and fine-grained locking and observed that different synchronisation placements are produced for our experiments, favouring e.g. a minimal number of synchronisation operations or maximum concurrency.

Linear distances between Markov chains - Daca, Przemyslaw; Henzinger, Thomas A; Kretinsky, Jan; Petrov, Tatjana
We introduce a general class of distances (metrics) between Markov chains, which are based on linear behaviour. This class encompasses distances given topologically (such as the total variation distance or trace distance) as well as by temporal logics or automata. We investigate which of the distances can be approximated by observing the systems, i.e. by black-box testing or simulation, and we provide both negative and positive results.

Faster statistical model checking for unbounded temporal properties - Daca, Przemyslaw; Henzinger, Thomas A; Kretinsky, Jan; Petrov, Tatjana
We present a new algorithm for the statistical model checking of Markov chains with respect to unbounded temporal properties, including full linear temporal logic. The main idea is that we monitor each simulation run on the fly, in order to detect quickly if a bottom strongly connected component is entered with high probability, in which case the simulation run can be terminated early. As a result, our simulation runs are often much shorter than required by termination bounds that are computed a priori for a desired level of confidence on a large state space. In comparison to previous algorithms for statistical model checking our method is not only faster in many cases but also requires less information about the system, namely, only the minimum transition probability that occurs in the Markov chain. In addition, our method can be generalised to unbounded quantitative properties such as mean-payoff bounds.

Abstraction-driven concolic testing - Daca, Przemyslaw; Gupta, Ashutosh; Henzinger, Thomas A
Concolic testing is a promising method for generating test suites for large programs. However, it suffers from the path-explosion problem and often fails to find tests that cover difficult-to-reach parts of programs. In contrast, model checkers based on counterexample-guided abstraction refinement explore programs exhaustively, while failing to scale on large programs with precision. In this paper, we present a novel method that iteratively combines concolic testing and model checking to find a test suite for a given coverage criterion. If concolic testing fails to cover some test goals, then the model checker refines its program abstraction to prove more paths infeasible, which reduces the search space for concolic testing. We have implemented our method on top of the concolictesting tool Crest and the model checker CpaChecker. We evaluated our tool on a collection of programs and a category of SvComp benchmarks. In our experiments, we observed an improvement in branch coverage compared to Crest from 48% to 63% in the best case, and from 66% to 71% on average.

Array folds logic - Daca, Przemyslaw; Henzinger, Thomas A; Kupriyanov, Andrey
We present an extension to the quantifier-free theory of integer arrays which allows us to express counting. The properties expressible in Array Folds Logic (AFL) include statements such as "the first array cell contains the array length," and "the array contains equally many minimal and maximal elements." These properties cannot be expressed in quantified fragments of the theory of arrays, nor in the theory of concatenation. Using reduction to counter machines, we show that the satisfiability problem of AFL is PSPACE-complete, and with a natural restriction the complexity decreases to NP. We also show that adding either universal quantifiers or concatenation leads to undecidability. AFL contains terms that fold a function over an array. We demonstrate that folding, a well-known concept from functional languages, allows us to concisely summarize loops that count over arrays, which occurs frequently in real-life programs. We provide a tool that can discharge proof obligations in AFL, and we demonstrate on practical examples that our decision procedure can solve a broad range of problems in symbolic testing and program verification.

Bacterial autoimmunity due to a restriction-modification system - Pleska, Maros; Qian, Long; Okura, Reiko; Bergmiller, Tobias; Wakamoto, Yuichi; Kussell, Edo; Guet, Calin C (Current Biology)
Restriction-modification (RM) systems represent a minimal and ubiquitous biological system of self/non-self discrimination in prokaryotes [1], which protects hosts from exogenous DNA [2]. The mechanism is based on the balance between methyltransferase (M) and cognate restriction endonuclease (R). M tags endogenous DNA as self by methylating short specific DNA sequences called restriction sites, whereas R recognizes unmethylated restriction sites as non-self and introduces a double-stranded DNA break [3]. Restriction sites are significantly underrepresented in prokaryotic genomes [4-7], suggesting that the discrimination mechanism is imperfect and occasionally leads to autoimmunity due to self-DNA cleavage (self-restriction) [8]. Furthermore, RM systems can promote DNA recombination [9] and contribute to genetic variation in microbial populations, thus facilitating adaptive evolution [10]. However, cleavage of self-DNA by RM systems as elements shaping prokaryotic genomes has not been directly detected, and its cause, frequency, and outcome are unknown. We quantify self-restriction caused by two RM systems of Escherichia coli and find that, in agreement with levels of restriction site avoidance, EcoRI, but not EcoRV, cleaves self-DNA at a measurable rate. Self-restriction is a stochastic process, which temporarily induces the SOS response, and is followed by DNA repair, maintaining cell viability. We find that RM systems with higher restriction efficiency against bacteriophage infections exhibit a higher rate of self-restriction, and that this rate can be further increased by stochastic imbalance between R and M. Our results identify molecular noise in RM systems as a factor shaping prokaryotic genomes.

Optimal reachability and a space time tradeoff for distance queries in constant treewidth graphs - Chatterjee, Krishnendu; Ibsen-Jensen, Rasmus; Pavlogiannis, Andreas
We consider data-structures for answering reachability and distance queries on constant-treewidth graphs with n nodes, on the standard RAM computational model with wordsize W=Theta(log n). Our first contribution is a data-structure that after O(n) preprocessing time, allows (1) pair reachability queries in O(1) time; and (2) single-source reachability queries in O(n/log n) time. This is (asymptotically) optimal and is faster than DFS/BFS when answering more than a constant number of single-source queries. The data-structure uses at all times O(n) space. Our second contribution is a space-time tradeoff data-structure for distance queries. For any epsilon in [1/2,1], we provide a data-structure with polynomial preprocessing time that allows pair queries in O(n^{1-ε} alpha(n)) time, where alpha is the inverse of the Ackermann function, and at all times uses O(n^epsilon) space. The input graph G is not considered in the space complexity.

Fast approximations for boundary element based brittle fracture simulation - Hahn, David; Wojtan, Christopher J
We present a boundary element based method for fast simulation of brittle fracture. By introducing simplifying assumptions that allow us to quickly estimate stress intensities and opening displacements during crack propagation, we build a fracture algorithm where the cost of each time step scales linearly with the length of the crackfront. The transition from a full boundary element method to our faster variant is possible at the beginning of any time step. This allows us to build a hybrid method, which uses the expensive but more accurate BEM while the number of degrees of freedom is low, and uses the fast method once that number exceeds a given threshold as the crack geometry becomes more complicated. Furthermore, we integrate this fracture simulation with a standard rigid-body solver. Our rigid-body coupling solves a Neumann boundary value problem by carefully separating translational, rotational and deformational components of the collision forces and then applying a Tikhonov regularizer to the resulting linear system. We show that our method produces physically reasonable results in standard test cases and is capable of dealing with complex scenes faster than previous finite- or boundary element approaches.

Offline witness encryption - Abusalah, Hamza M; Fuchsbauer, Georg; Pietrzak, Krzysztof Z
Witness encryption (WE) was introduced by Garg et al. [GGSW13]. A WE scheme is defined for some NP language L and lets a sender encrypt messages relative to instances x. A ciphertext for x can be decrypted using w witnessing x ∈ L, but hides the message if x ∈ L. Garg et al. construct WE from multilinear maps and give another construction [GGH+13b] using indistinguishability obfuscation (iO) for circuits. Due to the reliance on such heavy tools, WE can cur- rently hardly be implemented on powerful hardware and will unlikely be realizable on constrained devices like smart cards any time soon. We construct a WE scheme where encryption is done by simply computing a Naor-Yung ciphertext (two CPA encryptions and a NIZK proof). To achieve this, our scheme has a setup phase, which outputs public parameters containing an obfuscated circuit (only required for decryption), two encryption keys and a common reference string (used for encryption). This setup need only be run once, and the parame- ters can be used for arbitrary many encryptions. Our scheme can also be turned into a functional WE scheme, where a message is encrypted w.r.t. a statement and a function f, and decryption with a witness w yields f (m, w). Our construction is inspired by the functional encryption scheme by Garg et al. and we prove (selective) security assuming iO and statistically simulation-sound NIZK. We give a construction of the latter in bilinear groups and combining it with ElGamal encryption, our ciphertexts are of size 1.3 kB at a 128-bit security level and can be computed on a smart card.

Constrained PRFs for unbounded inputs - Abusalah, Hamza M; Fuchsbauer, Georg; Pietrzak, Krzysztof Z
A constrained pseudorandom function F: K × X → Y for a family T ⊆ 2X of subsets of X is a function where for any key k ∈ K and set S ∈ T one can efficiently compute a constrained key kS which allows to evaluate F (k, ·) on all inputs x ∈ S, while even given this key, the outputs on all inputs x ∉ S look random. At Asiacrypt’13 Boneh and Waters gave a construction which supports the most general set family so far. Its keys kc are defined for sets decided by boolean circuits C and enable evaluation of the PRF on any x ∈ X where C(x) = 1. In their construction the PRF input length and the size of the circuits C for which constrained keys can be computed must be fixed beforehand during key generation. We construct a constrained PRF that has an unbounded input length and whose constrained keys can be defined for any set recognized by a Turing machine. The only a priori bound we make is on the description size of the machines. We prove our construction secure assuming publiccoin differing-input obfuscation. As applications of our constrained PRF we build a broadcast encryption scheme where the number of potential receivers need not be fixed at setup (in particular, the length of the keys is independent of the number of parties) and the first identity-based non-interactive key exchange protocol with no bound on the number of parties that can agree on a shared key.

Constrained PRFs for unbounded inputs with short keys - Abusalah, Hamza M; Fuchsbauer, Georg
A constrained pseudorandom function (CPRF) F: K×X → Y for a family T of subsets of χ is a function where for any key k ∈ K and set S ∈ T one can efficiently compute a short constrained key kS, which allows to evaluate F(k, ·) on all inputs x ∈ S, while the outputs on all inputs x /∈ S look random even given kS. Abusalah et al. recently constructed the first constrained PRF for inputs of arbitrary length whose sets S are decided by Turing machines. They use their CPRF to build broadcast encryption and the first ID-based non-interactive key exchange for an unbounded number of users. Their constrained keys are obfuscated circuits and are therefore large. In this work we drastically reduce the key size and define a constrained key for a Turing machine M as a short signature on M. For this, we introduce a new signature primitive with constrained signing keys that let one only sign certain messages, while forging a signature on others is hard even when knowing the coins for key generation.

A phytochrome sensory domain permits receptor activation by red light - Gschaider-Reichhart, Eva; Inglés Prieto, Álvaro; Tichy, Alexandra-Madelaine; Mckenzie, Catherine; Janovjak, Harald L (Angewandte Chemie - International Edition)
Optogenetics and photopharmacology enable the spatio-temporal control of cell and animal behavior by light. Although red light offers deep-tissue penetration and minimal phototoxicity, very few red-light-sensitive optogenetic methods are currently available. We have now developed a red-light-induced homodimerization domain. We first showed that an optimized sensory domain of the cyanobacterial phytochrome 1 can be expressed robustly and without cytotoxicity in human cells. We then applied this domain to induce the dimerization of two receptor tyrosine kinases—the fibroblast growth factor receptor 1 and the neurotrophin receptor trkB. This new optogenetic method was then used to activate the MAPK/ERK pathway non-invasively in mammalian tissue and in multicolor cell-signaling experiments. The light-controlled dimerizer and red-light-activated receptor tyrosine kinases will prove useful to regulate a variety of cellular processes with light. Go deep with red: The sensory domain (S) of the cyanobacterial phytochrome 1 (CPH1) was repurposed to induce the homodimerization of proteins in living cells by red light. By using this domain, light-activated protein kinases were engineered that can be activated orthogonally from many fluorescent proteins and through mammalian tissue. Pr/Pfr=red-/far-red-absorbing state of CPH1.

Intrinsic limits to gene regulation by global crosstalk - Friedlander, Tamar; Prizak, Roshan; Guet, Calin C; Barton, Nicholas H; Tkacik, Gasper (Nature Communications)
Gene regulation relies on the specificity of transcription factor (TF)–DNA interactions. Limited specificity may lead to crosstalk: a regulatory state in which a gene is either incorrectly activated due to noncognate TF–DNA interactions or remains erroneously inactive. As each TF can have numerous interactions with noncognate cis-regulatory elements, crosstalk is inherently a global problem, yet has previously not been studied as such. We construct a theoretical framework to analyse the effects of global crosstalk on gene regulation. We find that crosstalk presents a significant challenge for organisms with low-specificity TFs, such as metazoans. Crosstalk is not easily mitigated by known regulatory schemes acting at equilibrium, including variants of cooperativity and combinatorial regulation. Our results suggest that crosstalk imposes a previously unexplored global constraint on the functioning and evolution of regulatory networks, which is qualitatively distinct from the known constraints that act at the level of individual gene regulatory elements.

Mitochondrial uncouplers inhibit clathrin-mediated endocytosis largely through cytoplasmic acidification - Dejonghe, Wim; Kuenen, Sabine; Mylle, Evelien; Vasileva, Mina K; Keech, Olivier; Viotti, Corrado; Swerts, Jef; Fendrych, Matyas; Ortiz Morea, Fausto; Mishev, Kiril; Delang, Simon; Scholl, Stefan; et al. (Nature Communications)
ATP production requires the establishment of an electrochemical proton gradient across the inner mitochondrial membrane. Mitochondrial uncouplers dissipate this proton gradient and disrupt numerous cellular processes, including vesicular trafficking, mainly through energy depletion. Here we show that Endosidin9 (ES9), a novel mitochondrial uncoupler, is a potent inhibitor of clathrin-mediated endocytosis (CME) in different systems and that ES9 induces inhibition of CME not because of its effect on cellular ATP, but rather due to its protonophore activity that leads to cytoplasm acidification. We show that the known tyrosine kinase inhibitor tyrphostinA23, which is routinely used to block CME, displays similar properties, thus questioning its use as a specific inhibitor of cargo recognition by the AP-2 adaptor complex via tyrosine motif-based endocytosis signals. Furthermore, we show that cytoplasm acidification dramatically affects the dynamics and recruitment of clathrin and associated adaptors, and leads to reduction of phosphatidylinositol 4,5-biphosphate from the plasma membrane.

Actin rings of power - Schwayer, Cornelia; Sikora, Mateusz K; Slovakova, Jana; Kardos, Roland; Heisenberg, Carl-Philipp J (Developmental Cell)

Heavy-hole states in germanium hut wires - Watzinger, Hannes; Kloeffel, Christoph; Vukusic, Lada; Rossell, Marta; Sessi, Violetta; Kukucka, Josip; Kirchschlager, Raimund; Lausecker, Elisabeth; Truhlar, Alisha; Glaser, Martin; Rastelli, Armando; Fuhrer, Andreas; et al. (Nano Letters)
Hole spins have gained considerable interest in the past few years due to their potential for fast electrically controlled qubits. Here, we study holes confined in Ge hut wires, a so-far unexplored type of nanostructure. Low-temperature magnetotransport measurements reveal a large anisotropy between the in-plane and out-of-plane g-factors of up to 18. Numerical simulations verify that this large anisotropy originates from a confined wave function of heavy-hole character. A light-hole admixture of less than 1% is estimated for the states of lowest energy, leading to a surprisingly large reduction of the out-of-plane g-factors compared with those for pure heavy holes. Given this tiny light-hole contribution, the spin lifetimes are expected to be very long, even in isotopically nonpurified samples.

Safety assured formal model driven design of the multifunction vehicle bus controller - Jiang, Yu; Liu, Han; Song, Houbing; Kong, Hui; Gu, Ming; Sun, Jiaguang; Sha, Lui
In this paper, we present a formal model-driven engineering approach to establishing a safety-assured implementation of Multifunction vehicle bus controller (MVBC) based on the generic reference models and requirements described in the International Electrotechnical Commission (IEC) standard IEC-61375. First, the generic models described in IEC-61375 are translated into a network of timed automata, and some safety requirements tested in IEC-61375 are formalized as timed computation tree logic (TCTL) formulas. With the help of Uppaal, we check and debug whether the timed automata satisfy the formulas or not. Within this step, several logic inconsistencies in the original standard are detected and corrected. Then, we apply the tool Times to generate C code from the verified model, which was later synthesized into a real MVBC chip. Finally, the runtime verification tool RMOR is applied to verify some safety requirements at the implementation level. We set up a real platform with worldwide mostly used MVBC D113, and verify the correctness and the scalability of the synthesized MVBC chip more comprehensively. The errors in the standard has been confirmed and the resulted MVBC has been deployed in real train communication network.

Commutativity in the algorithmic Lovasz local lemma - Kolmogorov, Vladimir (Proceedings - Annual IEEE Symposium on Foundations of Computer Science)
We consider the recent formulation of the Algorithmic Lovász Local Lemma [1], [2] for finding objects that avoid "bad features", or "flaws". It extends the Moser-Tardos resampling algorithm [3] to more general discrete spaces. At each step the method picks a flaw present in the current state and "resamples" it using a "resampling oracle" provided by the user. However, it is less flexible than the Moser-Tardos method since [1], [2] require a specific flaw selection rule, whereas [3] allows an arbitrary rule (and thus can potentially be implemented more efficiently). We formulate a new "commutativity" condition, and prove that it is sufficient for an arbitrary rule to work. It also enables an efficient parallelization under an additional assumption. We then show that existing resampling oracles for perfect matchings and permutations do satisfy this condition. Finally, we generalize the precondition in [2] (in the case of symmetric potential causality graphs). This unifies special cases that previously were treated separately.

Algorithmic analysis of qualitative and quantitative termination problems for affine probabilistic programs - Chatterjee, Krishnendu; Fu, Hongfei; Novotny, Petr; Hasheminezhad, Rouzbeh
In this paper, we consider termination of probabilistic programs with real-valued variables. The questions concerned are: (a) qualitative ones that ask (i) whether the program terminates with probability 1 (almost-sure termination) and (ii) whether the expected termination time is finite (finite termination); (b) quantitative ones that ask (i) to approximate the expected termination time (expectation problem) and (ii) to compute a bound B such that the probability to terminate after B steps decreases exponentially (concentration problem). To solve these questions, we utilize the notion of ranking supermartingales which is a powerful approach for proving termination of probabilistic programs. In detail, we focus on algorithmic synthesis of linear ranking-supermartingales over affine probabilistic programs (APP's) with both angelic and demonic non-determinism. An important subclass of APP's is LRAPP which is defined as the class of all APP's over which a linear ranking-supermartingale exists. Our main contributions are as follows. Firstly, we show that the membership problem of LRAPP (i) can be decided in polynomial time for APP's with at most demonic non-determinism, and (ii) is NP-hard and in PSPACE for APP's with angelic non-determinism; moreover, the NP-hardness result holds already for APP's without probability and demonic non-determinism. Secondly, we show that the concentration problem over LRAPP can be solved in the same complexity as for the membership problem of LRAPP. Finally, we show that the expectation problem over LRAPP can be solved in 2EXPTIME and is PSPACE-hard even for APP's without probability and non-determinism (i.e., deterministic programs). Our experimental results demonstrate the effectiveness of our approach to answer the qualitative and quantitative questions over APP's with at most demonic non-determinism.

Data from: How does epistasis influence the response to selection? - Barton, Nicholas H
Much of quantitative genetics is based on the ‘infinitesimal model’, under which selection has a negligible effect on the genetic variance. This is typically justified by assuming a very large number of loci with additive effects. However, it applies even when genes interact, provided that the number of loci is large enough that selection on each of them is weak relative to random drift. In the long term, directional selection will change allele frequencies, but even then, the effects of epistasis on the ultimate change in trait mean due to selection may be modest. Stabilising selection can maintain many traits close to their optima, even when the underlying alleles are weakly selected. However, the number of traits that can be optimised is apparently limited to ~4Ne by the ‘drift load’, and this is hard to reconcile with the apparent complexity of many organisms. Just as for the mutation load, this limit can be evaded by a particular form of negative epistasis. A more robust limit is set by the variance in reproductive success. This suggests that selection accumulates information most efficiently in the infinitesimal regime, when selection on individual alleles is weak, and comparable with random drift. A review of evidence on selection strength suggests that although most variance in fitness may be because of alleles with large Nes, substantial amounts of adaptation may be because of alleles in the infinitesimal regime, in which epistasis has modest effects.

Data from evolutionary interplay between structure, energy and epistasis in the coat protein of the ϕX174 phage family - Fernandes Redondo, Rodrigo A; de Vladar, Harold; Włodarski, Tomasz; Bollback, Jonathan P
Viral capsids are structurally constrained by interactions among the amino acids (AAs) of their constituent proteins. Therefore, epistasis is expected to evolve among physically interacting sites and to influence the rates of substitution. To study the evolution of epistasis, we focused on the major structural protein of the ϕX174 phage family by, first, reconstructing the ancestral protein sequences of 18 species using a Bayesian statistical framework. The inferred ancestral reconstruction differed at eight AAs, for a total of 256 possible ancestral haplotypes. For each ancestral haplotype and the extant species, we estimated, in silico, the distribution of free energies and epistasis of the capsid structure. We found that free energy has not significantly increased but epistasis has. We decomposed epistasis up to fifth order and found that higher-order epistasis sometimes compensates pairwise interactions making the free energy seem additive. The dN/dS ratio is low, suggesting strong purifying selection, and that structure is under stabilizing selection. We synthesized phages carrying ancestral haplotypes of the coat protein gene and measured their fitness experimentally. Our findings indicate that stabilizing mutations can have higher fitness, and that fitness optima do not necessarily coincide with energy minima.

C-planarity of embedded cyclic c-graphs - Fulek, Radoslav
We show that c-planarity is solvable in quadratic time for flat clustered graphs with three clusters if the combinatorial embedding of the underlying graph is fixed. In simpler graph-theoretical terms our result can be viewed as follows. Given a graph G with the vertex set partitioned into three parts embedded on a 2-sphere, our algorithm decides if we can augment G by adding edges without creating an edge-crossing so that in the resulting spherical graph the vertices of each part induce a connected sub-graph. We proceed by a reduction to the problem of testing the existence of a perfect matching in planar bipartite graphs. We formulate our result in a slightly more general setting of cyclic clustered graphs, i.e., the simple graph obtained by contracting each cluster, where we disregard loops and multi-edges, is a cycle.

On expansion and topological overlap - Dotterrer, Dominic; Kaufman, Tali; Wagner, Uli
We give a detailed and easily accessible proof of Gromov's Topological Overlap Theorem. Let X be a finite simplicial complex or, more generally, a finite polyhedral cell complex of dimension d. Informally, the theorem states that if X has sufficiently strong higher-dimensional expansion properties (which generalize edge expansion of graphs and are defined in terms of cellular cochains of X) then X has the following topological overlap property: for every continuous map X → ℝd there exists a point p ∈ ℝd whose preimage intersects a positive fraction μ > 0 of the d-cells of X. More generally, the conclusion holds if ℝd is replaced by any d-dimensional piecewise-linear (PL) manifold M, with a constant μ that depends only on d and on the expansion properties of X, but not on M.

Intrinsic membrane properties determine hippocampal differential firing pattern in vivo in anesthetized rats - Kowalski, Janina; Gan, Jian; Jonas, Peter M; Pernia-Andrade, Alejandro (Hippocampus)
The hippocampus plays a key role in learning and memory. Previous studies suggested that the main types of principal neurons, dentate gyrus granule cells (GCs), CA3 pyramidal neurons, and CA1 pyramidal neurons, differ in their activity pattern, with sparse firing in GCs and more frequent firing in CA3 and CA1 pyramidal neurons. It has been assumed but never shown that such different activity may be caused by differential synaptic excitation. To test this hypothesis, we performed high-resolution whole-cell patch-clamp recordings in anesthetized rats in vivo. In contrast to previous in vitro data, both CA3 and CA1 pyramidal neurons fired action potentials spontaneously, with a frequency of ∼3–6 Hz, whereas GCs were silent. Furthermore, both CA3 and CA1 cells primarily fired in bursts. To determine the underlying mechanisms, we quantitatively assessed the frequency of spontaneous excitatory synaptic input, the passive membrane properties, and the active membrane characteristics. Surprisingly, GCs showed comparable synaptic excitation to CA3 and CA1 cells and the highest ratio of excitation versus hyperpolarizing inhibition. Thus, differential synaptic excitation is not responsible for differences in firing. Moreover, the three types of hippocampal neurons markedly differed in their passive properties. While GCs showed the most negative membrane potential, CA3 pyramidal neurons had the highest input resistance and the slowest membrane time constant. The three types of neurons also differed in the active membrane characteristics. GCs showed the highest action potential threshold, but displayed the largest gain of the input-output curves. In conclusion, our results reveal that differential firing of the three main types of hippocampal principal neurons in vivo is not primarily caused by differences in the characteristics of the synaptic input, but by the distinct properties of synaptic integration and input-output transformation.

Inference algorithms for pattern-based CRFs on sequence data - Kolmogorov, Vladimir; Takhanov, Rustem (Algorithmica)
We consider Conditional random fields (CRFs) with pattern-based potentials defined on a chain. In this model the energy of a string (labeling) (Formula presented.) is the sum of terms over intervals [i, j] where each term is non-zero only if the substring (Formula presented.) equals a prespecified pattern w. Such CRFs can be naturally applied to many sequence tagging problems. We present efficient algorithms for the three standard inference tasks in a CRF, namely computing (i) the partition function, (ii) marginals, and (iii) computing the MAP. Their complexities are respectively (Formula presented.), (Formula presented.) and (Formula presented.) where L is the combined length of input patterns, (Formula presented.) is the maximum length of a pattern, and D is the input alphabet. This improves on the previous algorithms of Ye et al. (NIPS, 2009) whose complexities are respectively (Formula presented.), (Formula presented.) and (Formula presented.), where (Formula presented.) is the number of input patterns. In addition, we give an efficient algorithm for sampling, and revisit the case of MAP with non-positive weights.

The CLE gene family in Populus trichocarpa - Liu, Zhijun; Yang, Nan; Lv, Yanting; Pan, Lixia; Lv, Shuo; Han, Huibin; Wang, Guodong (Plant Signaling & Behavior)
The CLE (CLAVATA3/Embryo Surrounding Region-related) peptides are small secreted signaling peptides that are primarily involved in the regulation of stem cell homeostasis in different plant meristems. Particularly, the characterization of the CLE41-PXY/TDR signaling pathway has greatly advanced our understanding on the potential roles of CLE peptides in vascular development and wood formation. Nevertheless, our knowledge on this gene family in a tree species is limited. In a recent study, we reported on a systematically investigation of the CLE gene family in Populus trichocarpa . The potential roles of PtCLE genes were studied by comparative analysis and transcriptional pro fi ling. Among fi fty PtCLE members, many PtCLE proteins share identical CLE motifs or contain the same CLE motif as that of AtCLEs, while PtCLE genes exhibited either comparable or distinct expression patterns comparing to their Arabidopsis counterparts. These fi ndings indicate the existence of both functional conservation and functional divergence between PtCLEs and their AtCLE orthologues. Our results provide valuable resources for future functional investigations of these critical signaling molecules in woody plants.

Efficient microwave to optical photon conversion: An electro-optical realization - Rueda, Alfredo; Sedlmeir, Florian; Collodo, Michele; Vogl, Ulrich; Stiller, Birgit; Schunk, Gerhard; Strekalov, Dmitry; Marquardt, Christoph; Fink, Johannes M; Painter, Oskar; Leuchs, Gerd; Schwefel, Harald (Optica)
Linking classical microwave electrical circuits to the optical telecommunication band is at the core of modern communication. Future quantum information networks will require coherent microwave-to-optical conversion to link electronic quantum processors and memories via low-loss optical telecommunication networks. Efficient conversion can be achieved with electro-optical modulators operating at the single microwave photon level. In the standard electro-optic modulation scheme, this is impossible because both up- and down-converted sidebands are necessarily present. Here, we demonstrate true single-sideband up- or down-conversion in a triply resonant whispering gallery mode resonator by explicitly addressing modes with asymmetric free spectral range. Compared to previous experiments, we show a 3 orders of magnitude improvement of the electro-optical conversion efficiency, reaching 0.1% photon number conversion for a 10 GHz microwave tone at 0.42 mW of optical pump power. The presented scheme is fully compatible with existing superconducting 3D circuit quantum electrodynamics technology and can be used for nonclassical state conversion and communication. Our conversion bandwidth is larger than 1 MHz and is not fundamentally limited.

Modes and exceptional points in waveguides with impedance boundary conditions - Midya, Bikashkali; Konotop, Vladimir (Optics Letters)
A planar waveguide with an impedance boundary, composed of nonperfect metallic plates, and with passive or active dielectric filling, is considered. We show the possibility of selective mode guiding and amplification when a homogeneous pump is added to the dielectric and analyze differences in TE and TM mode propagation. Such a non-conservative system is also shown to feature exceptional points for specific and experimentally tunable parameters, which are described for a particular case of transparent dielectric.

Nonlinear single sideband microwave to optical conversion using an electro-optic WGM-resonator - Rueda, Alfredo; Sedlmeir, Florian; Collodo, Michele; Vogl, Ulrich; Stiller, Birgit; Schunk, Gerhard; Strekalov, Dmitry; Marquardt, Christoph; Fink, Johannes M; Painter, Oskar; Leuchs, Gerd; Schwefel, Harald
Nonlinear electro-optical conversion of microwave radiation into the optical telecommunication band is achieved within a crystalline whispering gallery mode resonator, reaching 0.1% photon number conversion efficiency with MHz bandwidth.

Vascular cambium regeneration and vessel formation in wounded inflorescence stems of Arabidopsis - Mazur, Ewa; Benková, Eva; Friml, Jirí (Scientific Reports)
Synchronized tissue polarization during regeneration or de novo vascular tissue formation is a plant-specific example of intercellular communication and coordinated development. According to the canalization hypothesis, the plant hormone auxin serves as polarizing signal that mediates directional channel formation underlying the spatio-temporal vasculature patterning. A necessary part of canalization is a positive feedback between auxin signaling and polarity of the intercellular auxin flow. The cellular and molecular mechanisms of this process are still poorly understood, not the least, because of a lack of a suitable model system. We show that the main genetic model plant, Arabidopsis (Arabidopsis thaliana) can be used to study the canalization during vascular cambium regeneration and new vasculature formation. We monitored localized auxin responses, directional auxin-transport channels formation, and establishment of new vascular cambium polarity during regenerative processes after stem wounding. The increased auxin response above and around the wound preceded the formation of PIN1 auxin transporter-marked channels from the primarily homogenous tissue and the transient, gradual changes in PIN1 localization preceded the polarity of newly formed vascular tissue. Thus, Arabidopsis is a useful model for studies of coordinated tissue polarization and vasculature formation after wounding allowing for genetic and mechanistic dissection of the canalization hypothesis.

How MicroRNAs Are involved in splitting the mind - Tsai, Lihuei; Siegert, Sandra (JAMA Psychiatry)
This article provides an introduction to the role of microRNAs in the nervous system and outlines their potential involvement in the pathophysiology of schizophrenia, which is hypothesized to arise owing to environmental factors and genetic predisposition.

Arbitrarily strong amplifiers of natural selection - Pavlogiannis, Andreas; Tkadlec, Josef; Chatterjee, Krishnendu; Nowak, Martin

Repeated gains in yellow and anthocyanin pigmentation in flower colour transitions in the Antirrhineae - Ellis, Thomas; Field, David (Annals of Botany)
Background and aims Angiosperms display remarkable diversity in flower colour, implying that transitions between pigmentation phenotypes must have been common. Despite progress in understanding transitions between anthocyanin (blue, purple, pink or red) and unpigmented (white) flowers, little is known about the evolutionary patterns of flower-colour transitions in lineages with both yellow and anthocyanin-pigmented flowers. This study investigates the relative rates of evolutionary transitions between different combinations of yellow- and anthocyanin-pigmentation phenotypes in the tribe Antirrhineae. Methods We surveyed taxonomic literature for data on anthocyanin and yellow floral pigmentation for 369 species across the tribe. We then reconstructed the phylogeny of 169 taxa and used phylogenetic comparative methods to estimate transition rates among pigmentation phenotypes across the phylogeny. Key Results In contrast to previous studies we found a bias towards transitions involving a gain in pigmentation, although transitions to phenotypes with both anthocyanin and yellow taxa are nevertheless extremely rare. Despite the dominance of yellow and anthocyanin-pigmented taxa, transitions between these phenotypes are constrained to move through a white intermediate stage, whereas transitions to double-pigmentation are very rare. The most abundant transitions are between anthocyanin-pigmented and unpigmented flowers, and similarly the most abundant polymorphic taxa were those with anthocyanin-pigmented and unpigmented flowers. Conclusions Our findings show that pigment evolution is limited by the presence of other floral pigments. This interaction between anthocyanin and yellow pigments constrains the breadth of potential floral diversity observed in nature. In particular, they suggest that selection has repeatedly acted to promote the spread of single-pigmented phenotypes across the Antirrhineae phylogeny. Furthermore, the correlation between transition rates and polymorphism suggests that the forces causing and maintaining variance in the short term reflect evolutionary processes on longer time scales.

Flower colour data and phylogeny (NEXUS) files - Ellis, Thomas; Field, David
We collected flower colour information on species in the tribe Antirrhineae from taxonomic literature. We also retreived molecular data from GenBank for as many of these species as possible to estimate phylogenetic relationships among these taxa. We then used the R package 'diversitree' to examine patterns of evolutionary transitions between anthocyanin and yellow pigmentation across the phylogeny. For full details of the methods see: Ellis TJ and Field DL "Repeated gains in yellow and anthocyanin pigmentation in flower colour transitions in the Antirrhineae”, Annals of Botany (in press)

Fiji script to determine average speed and direction of migration of cells - Hauschild, Robert
This FIJI script calculates the population average of the migration speed as a function of time of all cells from wide field microscopy movies.
Keywords: cell migration; wide field microscopy; FIJI

Synthetic discrete tomography problems - Swoboda, Paul
Small synthetic discrete tomography problems. Sizes are 32x32, 64z64 and 256x256. Projection angles are 2, 4, and 6. Number of labels are 3 and 5.
Keywords: discrete tomography