TY - JOUR
AB - High-throughput live-cell screens are intricate elements of systems biology studies and drug discovery pipelines. Here, we demonstrate an optogenetics-assisted method that avoids the need for chemical activators and reporters, reduces the number of operational steps and increases information content in a cell-based small-molecule screen against human protein kinases, including an orphan receptor tyrosine kinase. This blueprint for all-optical screening can be adapted to many drug targets and cellular processes.
AU - Inglés Prieto, Álvaro
AU - Gschaider-Reichhart, Eva
AU - Muellner, Markus
AU - Nowak, Matthias
AU - Nijman, Sebastian
AU - Grusch, Michael
AU - Janovjak, Harald L
ID - 1678
IS - 12
JF - Nature Chemical Biology
TI - Light-assisted small-molecule screening against protein kinases
VL - 11
ER -
TY - JOUR
AU - Lemoult, Grégoire M
AU - Maier, Philipp
AU - Hof, Björn
ID - 1679
IS - 9
JF - Physics of Fluids
TI - Taylor's Forest
VL - 27
ER -
TY - JOUR
AB - We consider the satisfiability problem for modal logic over first-order definable classes of frames.We confirm the conjecture from Hemaspaandra and Schnoor [2008] that modal logic is decidable over classes definable by universal Horn formulae. We provide a full classification of Horn formulae with respect to the complexity of the corresponding satisfiability problem. It turns out, that except for the trivial case of inconsistent formulae, local satisfiability is eitherNP-complete or PSPACE-complete, and global satisfiability is NP-complete, PSPACE-complete, or ExpTime-complete. We also show that the finite satisfiability problem for modal logic over Horn definable classes of frames is decidable. On the negative side, we show undecidability of two related problems. First, we exhibit a simple universal three-variable formula defining the class of frames over which modal logic is undecidable. Second, we consider the satisfiability problem of bimodal logic over Horn definable classes of frames, and also present a formula leading to undecidability.
AU - Michaliszyn, Jakub
AU - Otop, Jan
AU - Kieroňski, Emanuel
ID - 1680
IS - 1
JF - ACM Transactions on Computational Logic
TI - On the decidability of elementary modal logics
VL - 17
ER -
TY - JOUR
AB - In many social situations, individuals endeavor to find the single best possible partner, but are constrained to evaluate the candidates in sequence. Examples include the search for mates, economic partnerships, or any other long-term ties where the choice to interact involves two parties. Surprisingly, however, previous theoretical work on mutual choice problems focuses on finding equilibrium solutions, while ignoring the evolutionary dynamics of decisions. Empirically, this may be of high importance, as some equilibrium solutions can never be reached unless the population undergoes radical changes and a sufficient number of individuals change their decisions simultaneously. To address this question, we apply a mutual choice sequential search problem in an evolutionary game-theoretical model that allows one to find solutions that are favored by evolution. As an example, we study the influence of sequential search on the evolutionary dynamics of cooperation. For this, we focus on the classic snowdrift game and the prisoner’s dilemma game.
AU - Priklopil, Tadeas
AU - Chatterjee, Krishnendu
ID - 1681
IS - 4
JF - Games
TI - Evolution of decisions in population games with sequentially searching individuals
VL - 6
ER -
TY - JOUR
AB - We study the problem of robust satisfiability of systems of nonlinear equations, namely, whether for a given continuous function f:K→ ℝn on a finite simplicial complex K and α > 0, it holds that each function g: K → ℝn such that ||g - f || ∞ < α, has a root in K. Via a reduction to the extension problem of maps into a sphere, we particularly show that this problem is decidable in polynomial time for every fixed n, assuming dimK ≤ 2n - 3. This is a substantial extension of previous computational applications of topological degree and related concepts in numerical and interval analysis. Via a reverse reduction, we prove that the problem is undecidable when dim K > 2n - 2, where the threshold comes from the stable range in homotopy theory. For the lucidity of our exposition, we focus on the setting when f is simplexwise linear. Such functions can approximate general continuous functions, and thus we get approximation schemes and undecidability of the robust satisfiability in other possible settings.
AU - Franek, Peter
AU - Krcál, Marek
ID - 1682
IS - 4
JF - Journal of the ACM
TI - Robust satisfiability of systems of equations
VL - 62
ER -
TY - JOUR
AB - The 1 MDa, 45-subunit proton-pumping NADH-ubiquinone oxidoreductase (complex I) is the largest complex of the mitochondrial electron transport chain. The molecular mechanism of complex I is central to the metabolism of cells, but has yet to be fully characterized. The last two years have seen steady progress towards this goal with the first atomic-resolution structure of the entire bacterial complex I, a 5 Å cryo-electron microscopy map of bovine mitochondrial complex I and a ∼3.8 Å resolution X-ray crystallographic study of mitochondrial complex I from yeast Yarrowia lipotytica. In this review we will discuss what we have learned from these studies and what remains to be elucidated.
AU - Letts, Jame A
AU - Sazanov, Leonid A
ID - 1683
IS - 8
JF - Current Opinion in Structural Biology
TI - Gaining mass: The structure of respiratory complex I-from bacterial towards mitochondrial versions
VL - 33
ER -
TY - CONF
AB - Given a graph G cellularly embedded on a surface Σ of genus g, a cut graph is a subgraph of G such that cutting Σ along G yields a topological disk. We provide a fixed parameter tractable approximation scheme for the problem of computing the shortest cut graph, that is, for any ε > 0, we show how to compute a (1 + ε) approximation of the shortest cut graph in time f(ε, g)n3.
Our techniques first rely on the computation of a spanner for the problem using the technique of brick decompositions, to reduce the problem to the case of bounded tree-width. Then, to solve the bounded tree-width case, we introduce a variant of the surface-cut decomposition of Rué, Sau and Thilikos, which may be of independent interest.
AU - Cohen Addad, Vincent
AU - De Mesmay, Arnaud N
ID - 1685
TI - A fixed parameter tractable approximation scheme for the optimal cut graph of a surface
VL - 9294
ER -
TY - JOUR
AU - Kiermaier, Eva
AU - Sixt, Michael K
ID - 1686
IS - 6252
JF - Science
TI - Fragmented communication between immune cells: Neutrophils blaze a trail with migratory cues for T cells to follow to sites of infection
VL - 349
ER -
TY - JOUR
AB - Guided cell movement is essential for development and integrity of animals and crucially involved in cellular immune responses. Leukocytes are professional migratory cells that can navigate through most types of tissues and sense a wide range of directional cues. The responses of these cells to attractants have been mainly explored in tissue culture settings. How leukocytes make directional decisions in situ, within the challenging environment of a tissue maze, is less understood. Here we review recent advances in how leukocytes sense chemical cues in complex tissue settings and make links with paradigms of directed migration in development and Dictyostelium discoideum amoebae.
AU - Sarris, Milka
AU - Sixt, Michael K
ID - 1687
IS - 10
JF - Current Opinion in Cell Biology
TI - Navigating in tissue mazes: Chemoattractant interpretation in complex environments
VL - 36
ER -
TY - JOUR
AB - We estimate the selection constant in the following geometric selection theorem by Pach: For every positive integer d, there is a constant (Formula presented.) such that whenever (Formula presented.) are n-element subsets of (Formula presented.), we can find a point (Formula presented.) and subsets (Formula presented.) for every i∈[d+1], each of size at least cdn, such that p belongs to all rainbowd-simplices determined by (Formula presented.) simplices with one vertex in each Yi. We show a super-exponentially decreasing upper bound (Formula presented.). The ideas used in the proof of the upper bound also help us to prove Pach’s theorem with (Formula presented.), which is a lower bound doubly exponentially decreasing in d (up to some polynomial in the exponent). For comparison, Pach’s original approach yields a triply exponentially decreasing lower bound. On the other hand, Fox, Pach, and Suk recently obtained a hypergraph density result implying a proof of Pach’s theorem with (Formula presented.). In our construction for the upper bound, we use the fact that the minimum solid angle of every d-simplex is super-exponentially small. This fact was previously unknown and might be of independent interest. For the lower bound, we improve the ‘separation’ part of the argument by showing that in one of the key steps only d+1 separations are necessary, compared to 2d separations in the original proof. We also provide a measure version of Pach’s theorem.
AU - Karasev, Roman
AU - Kynčl, Jan
AU - Paták, Pavel
AU - Patakova, Zuzana
AU - Tancer, Martin
ID - 1688
IS - 3
JF - Discrete & Computational Geometry
TI - Bounds for Pach's selection theorem and for the minimum solid angle in a simplex
VL - 54
ER -