TY - JOUR
AB - Many stochastic models of biochemical reaction networks contain some chemical species for which the number of molecules that are present in the system can only be finite (for instance due to conservation laws), but also other species that can be present in arbitrarily large amounts. The prime example of such networks are models of gene expression, which typically contain a small and finite number of possible states for the promoter but an infinite number of possible states for the amount of mRNA and protein. One of the main approaches to analyze such models is through the use of equations for the time evolution of moments of the chemical species. Recently, a new approach based on conditional moments of the species with infinite state space given all the different possible states of the finite species has been proposed. It was argued that this approach allows one to capture more details about the full underlying probability distribution with a smaller number of equations. Here, I show that the result that less moments provide more information can only stem from an unnecessarily complicated description of the system in the classical formulation. The foundation of this argument will be the derivation of moment equations that describe the complete probability distribution over the finite state space but only low-order moments over the infinite state space. I will show that the number of equations that is needed is always less than what was previously claimed and always less than the number of conditional moment equations up to the same order. To support these arguments, a symbolic algorithm is provided that can be used to derive minimal systems of unconditional moment equations for models with partially finite state space.
AU - Ruess, Jakob
ID - 1539
IS - 24
JF - Journal of Chemical Physics
TI - Minimal moment equations for stochastic models of biochemical reaction networks with partially finite state space
VL - 143
ER -
TY - CONF
AB - Aiming at the automatic diagnosis of tumors from narrow band imaging (NBI) magnifying endoscopy (ME) images of the stomach, we combine methods from image processing, computational topology, and machine learning to classify patterns into normal, tubular, vessel. Training the algorithm on a small number of images of each type, we achieve a high rate of correct classifications. The analysis of the learning algorithm reveals that a handful of geometric and topological features are responsible for the overwhelming majority of decisions.
AU - Dunaeva, Olga
AU - Edelsbrunner, Herbert
AU - Lukyanov, Anton
AU - Machin, Michael
AU - Malkova, Daria
ID - 1568
T2 - Proceedings - 16th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing
TI - The classification of endoscopy images with persistent homology
ER -
TY - JOUR
AB - Spatial regulation of the plant hormone indole-3-acetic acid (IAA, or auxin) is essential for plant development. Auxin gradient establishment is mediated by polarly localized auxin transporters, including PIN-FORMED (PIN) proteins. Their localization and abundance at the plasma membrane are tightly regulated by endomembrane machinery, especially the endocytic and recycling pathways mediated by the ADP ribosylation factor guanine nucleotide exchange factor (ARF-GEF) GNOM. We assessed the role of the early secretory pathway in establishing PIN1 polarity in Arabidopsis thaliana by pharmacological and genetic approaches. We identified the compound endosidin 8 (ES8), which selectively interferes with PIN1 basal polarity without altering the polarity of apical proteins. ES8 alters the auxin distribution pattern in the root and induces a strong developmental phenotype, including reduced root length. The ARF-GEF- defective mutants gnom-like 1 ( gnl1-1) and gnom ( van7) are significantly resistant to ES8. The compound does not affect recycling or vacuolar trafficking of PIN1 but leads to its intracellular accumulation, resulting in loss of PIN1 basal polarity at the plasma membrane. Our data confirm a role for GNOM in endoplasmic reticulum (ER) - Golgi trafficking and reveal that a GNL1/GNOM-mediated early secretory pathway selectively regulates PIN1 basal polarity establishment in a manner essential for normal plant development.
AU - Doyle, Siamsa
AU - Haegera, Ash
AU - Vain, Thomas
AU - Rigala, Adeline
AU - Viotti, Corrado
AU - Łangowskaa, Małgorzata
AU - Maa, Qian
AU - Friml, Jirí
AU - Raikhel, Natasha
AU - Hickse, Glenn
AU - Robert, Stéphanie
ID - 1569
IS - 7
JF - PNAS
TI - An early secretory pathway mediated by gnom-like 1 and gnom is essential for basal polarity establishment in Arabidopsis thaliana
VL - 112
ER -
TY - JOUR
AB - Grounding autonomous behavior in the nervous system is a fundamental challenge for neuroscience. In particular, self-organized behavioral development provides more questions than answers. Are there special functional units for curiosity, motivation, and creativity? This paper argues that these features can be grounded in synaptic plasticity itself, without requiring any higher-level constructs. We propose differential extrinsic plasticity (DEP) as a new synaptic rule for self-learning systems and apply it to a number of complex robotic systems as a test case. Without specifying any purpose or goal, seemingly purposeful and adaptive rhythmic behavior is developed, displaying a certain level of sensorimotor intelligence. These surprising results require no systemspecific modifications of the DEP rule. They rather arise from the underlying mechanism of spontaneous symmetry breaking,which is due to the tight brain body environment coupling. The new synaptic rule is biologically plausible and would be an interesting target for neurobiological investigation. We also argue that this neuronal mechanism may have been a catalyst in natural evolution.
AU - Der, Ralf
AU - Martius, Georg S
ID - 1570
IS - 45
JF - PNAS
TI - Novel plasticity rule can explain the development of sensorimotor intelligence
VL - 112
ER -
TY - JOUR
AB - Epistatic interactions can frustrate and shape evolutionary change. Indeed, phenotypes may fail to evolve when essential mutations are only accessible through positive selection if they are fixed simultaneously. How environmental variability affects such constraints is poorly understood. Here, we studied genetic constraints in fixed and fluctuating environments using the Escherichia coli lac operon as a model system for genotype-environment interactions. We found that, in different fixed environments, all trajectories that were reconstructed by applying point mutations within the transcription factor-operator interface became trapped at suboptima, where no additional improvements were possible. Paradoxically, repeated switching between these same environments allows unconstrained adaptation by continuous improvements. This evolutionary mode is explained by pervasive cross-environmental tradeoffs that reposition the peaks in such a way that trapped genotypes can repeatedly climb ascending slopes and hence, escape adaptive stasis. Using a Markov approach, we developed a mathematical framework to quantify the landscape-crossing rates and show that this ratchet-like adaptive mechanism is robust in a wide spectrum of fluctuating environments. Overall, this study shows that genetic constraints can be overcome by environmental change and that crossenvironmental tradeoffs do not necessarily impede but also, can facilitate adaptive evolution. Because tradeoffs and environmental variability are ubiquitous in nature, we speculate this evolutionary mode to be of general relevance.
AU - De Vos, Marjon
AU - Dawid, Alexandre
AU - Šunderlíková, Vanda
AU - Tans, Sander
ID - 1571
IS - 48
JF - PNAS
TI - Breaking evolutionary constraint with a tradeoff ratchet
VL - 112
ER -
TY - JOUR
AB - We consider the quantum ferromagnetic Heisenberg model in three dimensions, for all spins S ≥ 1/2. We rigorously prove the validity of the spin-wave approximation for the excitation spectrum, at the level of the first non-trivial contribution to the free energy at low temperatures. Our proof comes with explicit, constructive upper and lower bounds on the error term. It uses in an essential way the bosonic formulation of the model in terms of the Holstein-Primakoff representation. In this language, the model describes interacting bosons with a hard-core on-site repulsion and a nearest-neighbor attraction. This attractive interaction makes the lower bound on the free energy particularly tricky: the key idea there is to prove a differential inequality for the two-particle density, which is thereby shown to be smaller than the probability density of a suitably weighted two-particle random process on the lattice.
AU - Correggi, Michele
AU - Giuliani, Alessandro
AU - Seiringer, Robert
ID - 1572
IS - 1
JF - Communications in Mathematical Physics
TI - Validity of the spin-wave approximation for the free energy of the Heisenberg ferromagnet
VL - 339
ER -
TY - JOUR
AB - We present a new, simpler proof of the unconditional uniqueness of solutions to the cubic Gross-Pitaevskii hierarchy in ℝ3. One of the main tools in our analysis is the quantum de Finetti theorem. Our uniqueness result is equivalent to the one established in the celebrated works of Erdos, Schlein, and Yau.
AU - Chen, Thomas
AU - Hainzl, Christian
AU - Pavlović, Nataša
AU - Seiringer, Robert
ID - 1573
IS - 10
JF - Communications on Pure and Applied Mathematics
TI - Unconditional uniqueness for the cubic gross pitaevskii hierarchy via quantum de finetti
VL - 68
ER -
TY - JOUR
AB - Multiple plant developmental processes, such as lateral root development, depend on auxin distribution patterns that are in part generated by the PIN-formed family of auxin-efflux transporters. Here we propose that AUXIN RESPONSE FACTOR7 (ARF7) and the ARF7-regulated FOUR LIPS/MYB124 (FLP) transcription factors jointly form a coherent feed-forward motif that mediates the auxin-responsive PIN3 transcription in planta to steer the early steps of lateral root formation. This regulatory mechanism might endow the PIN3 circuitry with a temporal 'memory' of auxin stimuli, potentially maintaining and enhancing the robustness of the auxin flux directionality during lateral root development. The cooperative action between canonical auxin signalling and other transcription factors might constitute a general mechanism by which transcriptional auxin-sensitivity can be regulated at a tissue-specific level.
AU - Chen, Qian
AU - Liu, Yang
AU - Maere, Steven
AU - Lee, Eunkyoung
AU - Van Isterdael, Gert
AU - Xie, Zidian
AU - Xuan, Wei
AU - Lucas, Jessica
AU - Vassileva, Valya
AU - Kitakura, Saeko
AU - Marhavy, Peter
AU - Wabnik, Krzysztof T
AU - Geldner, Niko
AU - Benková, Eva
AU - Le, Jie
AU - Fukaki, Hidehiro
AU - Grotewold, Erich
AU - Li, Chuanyou
AU - Friml, Jirí
AU - Sack, Fred
AU - Beeckman, Tom
AU - Vanneste, Steffen
ID - 1574
JF - Nature Communications
TI - A coherent transcriptional feed-forward motif model for mediating auxin-sensitive PIN3 expression during lateral root development
VL - 6
ER -
TY - JOUR
AB - The immune response relies on the migration of leukocytes and on their ability to stop in precise anatomical locations to fulfil their task. How leukocyte migration and function are coordinated is unknown. Here we show that in immature dendritic cells, which patrol their environment by engulfing extracellular material, cell migration and antigen capture are antagonistic. This antagonism results from transient enrichment of myosin IIA at the cell front, which disrupts the back-to-front gradient of the motor protein, slowing down locomotion but promoting antigen capture. We further highlight that myosin IIA enrichment at the cell front requires the MHC class II-associated invariant chain (Ii). Thus, by controlling myosin IIA localization, Ii imposes on dendritic cells an intermittent antigen capture behaviour that might facilitate environment patrolling. We propose that the requirement for myosin II in both cell migration and specific cell functions may provide a general mechanism for their coordination in time and space.
AU - Chabaud, Mélanie
AU - Heuzé, Mélina
AU - Bretou, Marine
AU - Vargas, Pablo
AU - Maiuri, Paolo
AU - Solanes, Paola
AU - Maurin, Mathieu
AU - Terriac, Emmanuel
AU - Le Berre, Maël
AU - Lankar, Danielle
AU - Piolot, Tristan
AU - Adelstein, Robert
AU - Zhang, Yingfan
AU - Sixt, Michael K
AU - Jacobelli, Jordan
AU - Bénichou, Olivier
AU - Voituriez, Raphaël
AU - Piel, Matthieu
AU - Lennon Duménil, Ana
ID - 1575
JF - Nature Communications
TI - Cell migration and antigen capture are antagonistic processes coupled by myosin II in dendritic cells
VL - 6
ER -
TY - JOUR
AB - We investigate weighted straight skeletons from a geometric, graph-theoretical, and combinatorial point of view. We start with a thorough definition and shed light on some ambiguity issues in the procedural definition. We investigate the geometry, combinatorics, and topology of faces and the roof model, and we discuss in which cases a weighted straight skeleton is connected. Finally, we show that the weighted straight skeleton of even a simple polygon may be non-planar and may contain cycles, and we discuss under which restrictions on the weights and/or the input polygon the weighted straight skeleton still behaves similar to its unweighted counterpart. In particular, we obtain a non-procedural description and a linear-time construction algorithm for the straight skeleton of strictly convex polygons with arbitrary weights.
AU - Biedl, Therese
AU - Held, Martin
AU - Huber, Stefan
AU - Kaaser, Dominik
AU - Palfrader, Peter
ID - 1584
IS - 5
JF - Computational Geometry: Theory and Applications
TI - Reprint of: Weighted straight skeletons in the plane
VL - 48
ER -
TY - JOUR
AB - In this paper, we consider the fluctuation of mutual information statistics of a multiple input multiple output channel communication systems without assuming that the entries of the channel matrix have zero pseudovariance. To this end, we also establish a central limit theorem of the linear spectral statistics for sample covariance matrices under general moment conditions by removing the restrictions imposed on the second moment and fourth moment on the matrix entries in Bai and Silverstein (2004).
AU - Bao, Zhigang
AU - Pan, Guangming
AU - Zhou, Wang
ID - 1585
IS - 6
JF - IEEE Transactions on Information Theory
TI - Asymptotic mutual information statistics of MIMO channels and CLT of sample covariance matrices
VL - 61
ER -
TY - JOUR
AB - Through metabolic engineering cyanobacteria can be employed in biotechnology. Combining the capacity for oxygenic photosynthesis and carbon fixation with an engineered metabolic pathway allows carbon-based product formation from CO2, light, and water directly. Such cyanobacterial 'cell factories' are constructed to produce biofuels, bioplastics, and commodity chemicals. Efforts of metabolic engineers and synthetic biologists allow the modification of the intermediary metabolism at various branching points, expanding the product range. The new biosynthesis routes 'tap' the metabolism ever more efficiently, particularly through the engineering of driving forces and utilization of cofactors generated during the light reactions of photosynthesis, resulting in higher product titers. High rates of carbon rechanneling ultimately allow an almost-complete allocation of fixed carbon to product above biomass.
AU - Angermayr, Andreas
AU - Gorchs, Aleix
AU - Hellingwerf, Klaas
ID - 1586
IS - 6
JF - Trends in Biotechnology
TI - Metabolic engineering of cyanobacteria for the synthesis of commodity products
VL - 33
ER -
TY - JOUR
AB - We investigate the quantum interference shifts between energetically close states, where the state structure is observed by laser spectroscopy. We report a compact and analytical expression that models the quantum interference induced shift for any admixture of circular polarization of the incident laser and angle of observation. An experimental scenario free of quantum interference can thus be predicted with this formula. Although this study is exemplified here for muonic deuterium, it can be applied to any other laser spectroscopy measurement of ns-n′p frequencies of a nonrelativistic atomic system, via an ns→n′p→n′′s scheme.
AU - Amaro, Pedro
AU - Fratini, Filippo
AU - Safari, Laleh
AU - Antognini, Aldo
AU - Indelicato, Paul
AU - Pohl, Randolf
AU - Santos, José
ID - 1587
IS - 6
JF - Physical Review A - Atomic, Molecular, and Optical Physics
TI - Quantum interference shifts in laser spectroscopy with elliptical polarization
VL - 92
ER -
TY - JOUR
AB - We investigate the Taylor-Couette system where the radius ratio is close to unity. Systematically increasing the Reynolds number, we observe a number of previously known transitions, such as one from the classical Taylor vortex flow (TVF) to wavy vortex flow (WVF) and the transition to fully developed turbulence. Prior to the onset of turbulence, we observe intermittent bursting patterns of localized turbulent patches, confirming the experimentally observed pattern of very short wavelength bursts (VSWBs). A striking finding is that, for a Reynolds number larger than that for the onset of VSWBs, a new type of intermittently bursting behavior emerges: patterns of azimuthally closed rings of various orders. We call them ring-bursting patterns, which surround the cylinder completely but remain localized and separated in the axial direction through nonturbulent wavy structures. We employ a number of quantitative measures including the cross-flow energy to characterize the ring-bursting patterns and to distinguish them from the background flow. These patterns are interesting because they do not occur in the wide-gap Taylor-Couette flow systems. The narrow-gap regime is less studied but certainly deserves further attention to gain deeper insights into complex flow dynamics in fluids.
AU - Altmeyer, Sebastian
AU - Do, Younghae
AU - Lai, Ying
ID - 1588
IS - 5
JF - Physical Review E
TI - Ring-bursting behavior en route to turbulence in narrow-gap Taylor-Couette flows
VL - 92
ER -
TY - JOUR
AB - We investigate the dynamics of ferrofluidic wavy vortex flows in the counter-rotating Taylor-Couette system, with a focus on wavy flows with a mixture of the dominant azimuthal modes. Without external magnetic field flows are stable and pro-grade with respect to the rotation of the inner cylinder. More complex behaviors can arise when an axial or a transverse magnetic field is applied. Depending on the direction and strength of the field, multi-stable wavy states and bifurcations can occur. We uncover the phenomenon of flow pattern reversal as the strength of the magnetic field is increased through a critical value. In between the regimes of pro-grade and retrograde flow rotations, standing waves with zero angular velocities can emerge. A striking finding is that, under a transverse magnetic field, a second reversal in the flow pattern direction can occur, where the flow pattern evolves into pro-grade rotation again from a retrograde state. Flow reversal is relevant to intriguing phenomena in nature such as geomagnetic reversal. Our results suggest that, in ferrofluids, flow pattern reversal can be induced by varying a magnetic field in a controlled manner, which can be realized in laboratory experiments with potential applications in the development of modern fluid devices.
AU - Altmeyer, Sebastian
AU - Do, Younghae
AU - Lai, Ying
ID - 1589
JF - Scientific Reports
TI - Magnetic field induced flow pattern reversal in a ferrofluidic Taylor-Couette system
VL - 5
ER -
TY - CHAP
AB - The straight skeleton of a polygon is the geometric graph obtained by tracing the vertices during a mitered offsetting process. It is known that the straight skeleton of a simple polygon is a tree, and one can naturally derive directions on the edges of the tree from the propagation of the shrinking process. In this paper, we ask the reverse question: Given a tree with directed edges, can it be the straight skeleton of a polygon? And if so, can we find a suitable simple polygon? We answer these questions for all directed trees where the order of edges around each node is fixed.
AU - Aichholzer, Oswin
AU - Biedl, Therese
AU - Hackl, Thomas
AU - Held, Martin
AU - Huber, Stefan
AU - Palfrader, Peter
AU - Vogtenhuber, Birgit
ID - 1590
T2 - Graph Drawing and Network Visualization
TI - Representing directed trees as straight skeletons
VL - 9411
ER -
TY - JOUR
AB - Contrary to the pattern seen in mammalian sex chromosomes, where most Y-linked genes have X-linked homologs, the Drosophila X and Y chromosomes appear to be unrelated. Most of the Y-linked genes have autosomal paralogs, so autosome-to-Y transposition must be the main source of Drosophila Y-linked genes. Here we show how these genes were acquired. We found a previously unidentified gene (flagrante delicto Y, FDY) that originated from a recent duplication of the autosomal gene vig2 to the Y chromosome of Drosophila melanogaster. Four contiguous genes were duplicated along with vig2, but they became pseudogenes through the accumulation of deletions and transposable element insertions, whereas FDY remained functional, acquired testis-specific expression, and now accounts for ∼20% of the vig2-like mRNA in testis. FDY is absent in the closest relatives of D. melanogaster, and DNA sequence divergence indicates that the duplication to the Y chromosome occurred ∼2 million years ago. Thus, FDY provides a snapshot of the early stages of the establishment of a Y-linked gene and demonstrates how the Drosophila Y has been accumulating autosomal genes.
AU - Carvalho, Antonio
AU - Vicoso, Beatriz
AU - Russo, Claudia
AU - Swenor, Bonnielin
AU - Clark, Andrew
ID - 1577
IS - 40
JF - PNAS
TI - Birth of a new gene on the Y chromosome of Drosophila melanogaster
VL - 112
ER -
TY - JOUR
AB - We prove that the dual of the digital Voronoi diagram constructed by flooding the plane from the data points gives a geometrically and topologically correct dual triangulation. This provides the proof of correctness for recently developed GPU algorithms that outperform traditional CPU algorithms for constructing two-dimensional Delaunay triangulations.
AU - Cao, Thanhtung
AU - Edelsbrunner, Herbert
AU - Tan, Tiowseng
ID - 1578
IS - 7
JF - Computational Geometry
TI - Triangulations from topologically correct digital Voronoi diagrams
VL - 48
ER -
TY - JOUR
AB - We show that the Galois group of any Schubert problem involving lines in projective space contains the alternating group. This constitutes the largest family of enumerative problems whose Galois groups have been largely determined. Using a criterion of Vakil and a special position argument due to Schubert, our result follows from a particular inequality among Kostka numbers of two-rowed tableaux. In most cases, a combinatorial injection proves the inequality. For the remaining cases, we use the Weyl integral formulas to obtain an integral formula for these Kostka numbers. This rewrites the inequality as an integral, which we estimate to establish the inequality.
AU - Brooks, Christopher
AU - Martin Del Campo Sanchez, Abraham
AU - Sottile, Frank
ID - 1579
IS - 6
JF - Transactions of the American Mathematical Society
TI - Galois groups of Schubert problems of lines are at least alternating
VL - 367
ER -
TY - JOUR
AB - Synapsins (Syns) are an evolutionarily conserved family of presynaptic proteins crucial for the fine-tuning of synaptic function. A large amount of experimental evidences has shown that Syns are involved in the development of epileptic phenotypes and several mutations in Syn genes have been associated with epilepsy in humans and animal models. Syn mutations induce alterations in circuitry and neurotransmitter release, differentially affecting excitatory and inhibitory synapses, thus causing an excitation/inhibition imbalance in network excitability toward hyperexcitability that may be a determinant with regard to the development of epilepsy. Another approach to investigate epileptogenic mechanisms is to understand how silencing Syn affects the cellular behavior of single neurons and is associated with the hyperexcitable phenotypes observed in epilepsy. Here, we examined the functional effects of antisense-RNA inhibition of Syn expression on individually identified and isolated serotonergic cells of the Helix land snail. We found that Helix synapsin silencing increases cell excitability characterized by a slightly depolarized resting membrane potential, decreases the rheobase, reduces the threshold for action potential (AP) firing and increases the mean and instantaneous firing rates, with respect to control cells. The observed increase of Ca2+ and BK currents in Syn-silenced cells seems to be related to changes in the shape of the AP waveform. These currents sustain the faster spiking in Syn-deficient cells by increasing the after hyperpolarization and limiting the Na+ and Ca2+ channel inactivation during repetitive firing. This in turn speeds up the depolarization phase by reaching the AP threshold faster. Our results provide evidence that Syn silencing increases intrinsic cell excitability associated with increased Ca2+ and Ca2+-dependent BK currents in the absence of excitatory or inhibitory inputs.
AU - Brenes, Oscar
AU - Vandael, David H
AU - Carbone, Emilio
AU - Montarolo, Pier
AU - Ghirardi, Mirella
ID - 1580
JF - Neuroscience
TI - Knock-down of synapsin alters cell excitability and action potential waveform by potentiating BK and voltage gated Ca2 currents in Helix serotonergic neurons
VL - 311
ER -
TY - JOUR
AB - In animal embryos, morphogen gradients determine tissue patterning and morphogenesis. Shyer et al. provide evidence that, during vertebrate gut formation, tissue folding generates graded activity of signals required for subsequent steps of gut growth and differentiation, thereby revealing an intriguing link between tissue morphogenesis and morphogen gradient formation.
AU - Bollenbach, Mark Tobias
AU - Heisenberg, Carl-Philipp J
ID - 1581
IS - 3
JF - Cell
TI - Gradients are shaping up
VL - 161
ER -
TY - JOUR
AB - Plants are sessile organisms that are permanently restricted to their site of germination. To compensate for their lack of mobility, plants evolved unique mechanisms enabling them to rapidly react to ever changing environmental conditions and flexibly adapt their postembryonic developmental program. A prominent demonstration of this developmental plasticity is their ability to bend organs in order to reach the position most optimal for growth and utilization of light, nutrients, and other resources. Shortly after germination, dicotyledonous seedlings form a bended structure, the so-called apical hook, to protect the delicate shoot meristem and cotyledons from damage when penetrating through the soil. Upon perception of a light stimulus, the apical hook rapidly opens and the photomorphogenic developmental program is activated. After germination, plant organs are able to align their growth with the light source and adopt the most favorable orientation through bending, in a process named phototropism. On the other hand, when roots and shoots are diverted from their upright orientation, they immediately detect a change in the gravity vector and bend to maintain a vertical growth direction. Noteworthy, despite the diversity of external stimuli perceived by different plant organs, all plant tropic movements share a common mechanistic basis: differential cell growth. In our review, we will discuss the molecular principles underlying various tropic responses with the focus on mechanisms mediating the perception of external signals, transduction cascades and downstream responses that regulate differential cell growth and consequently, organ bending. In particular, we highlight common and specific features of regulatory pathways in control of the bending of organs and a role for the plant hormone auxin as a key regulatory component.
AU - Žádníková, Petra
AU - Smet, Dajo
AU - Zhu, Qiang
AU - Van Der Straeten, Dominique
AU - Benková, Eva
ID - 1593
IS - 4
JF - Frontiers in Plant Science
TI - Strategies of seedlings to overcome their sessile nature: Auxin in mobility control
VL - 6
ER -
TY - CONF
AB - Quantitative extensions of temporal logics have recently attracted significant attention. In this work, we study frequency LTL (fLTL), an extension of LTL which allows to speak about frequencies of events along an execution. Such an extension is particularly useful for probabilistic systems that often cannot fulfil strict qualitative guarantees on the behaviour. It has been recently shown that controller synthesis for Markov decision processes and fLTL is decidable when all the bounds on frequencies are 1. As a step towards a complete quantitative solution, we show that the problem is decidable for the fragment fLTL\GU, where U does not occur in the scope of G (but still F can). Our solution is based on a novel translation of such quantitative formulae into equivalent deterministic automata.
AU - Forejt, Vojtěch
AU - Krčál, Jan
AU - Kretinsky, Jan
ID - 1594
TI - Controller synthesis for MDPs and frequency LTL\GU
VL - 9450
ER -
TY - JOUR
AB - We investigate weighted straight skeletons from a geometric, graph-theoretical, and combinatorial point of view. We start with a thorough definition and shed light on some ambiguity issues in the procedural definition. We investigate the geometry, combinatorics, and topology of faces and the roof model, and we discuss in which cases a weighted straight skeleton is connected. Finally, we show that the weighted straight skeleton of even a simple polygon may be non-planar and may contain cycles, and we discuss under which restrictions on the weights and/or the input polygon the weighted straight skeleton still behaves similar to its unweighted counterpart. In particular, we obtain a non-procedural description and a linear-time construction algorithm for the straight skeleton of strictly convex polygons with arbitrary weights.
AU - Biedl, Therese
AU - Held, Martin
AU - Huber, Stefan
AU - Kaaser, Dominik
AU - Palfrader, Peter
ID - 1582
IS - 2
JF - Computational Geometry: Theory and Applications
TI - Weighted straight skeletons in the plane
VL - 48
ER -
TY - JOUR
AB - We study the characteristics of straight skeletons of monotone polygonal chains and use them to devise an algorithm for computing positively weighted straight skeletons of monotone polygons. Our algorithm runs in O(nlogn) time and O(n) space, where n denotes the number of vertices of the polygon.
AU - Biedl, Therese
AU - Held, Martin
AU - Huber, Stefan
AU - Kaaser, Dominik
AU - Palfrader, Peter
ID - 1583
IS - 2
JF - Information Processing Letters
TI - A simple algorithm for computing positively weighted straight skeletons of monotone polygons
VL - 115
ER -
TY - CONF
AB - We propose a flexible exchange format for ω-automata, as typically used in formal verification, and implement support for it in a range of established tools. Our aim is to simplify the interaction of tools, helping the research community to build upon other people’s work. A key feature of the format is the use of very generic acceptance conditions, specified by Boolean combinations of acceptance primitives, rather than being limited to common cases such as Büchi, Streett, or Rabin. Such flexibility in the choice of acceptance conditions can be exploited in applications, for example in probabilistic model checking, and furthermore encourages the development of acceptance-agnostic tools for automata manipulations. The format allows acceptance conditions that are either state-based or transition-based, and also supports alternating automata.
AU - Babiak, Tomáš
AU - Blahoudek, František
AU - Duret Lutz, Alexandre
AU - Klein, Joachim
AU - Kretinsky, Jan
AU - Mueller, Daniel
AU - Parker, David
AU - Strejček, Jan
ID - 1601
TI - The Hanoi omega-automata format
VL - 9206
ER -
TY - CONF
AB - A drawing of a graph G is radial if the vertices of G are placed on concentric circles C1, . . . , Ck with common center c, and edges are drawn radially: every edge intersects every circle centered at c at most once. G is radial planar if it has a radial embedding, that is, a crossing- free radial drawing. If the vertices of G are ordered or partitioned into ordered levels (as they are for leveled graphs), we require that the assignment of vertices to circles corresponds to the given ordering or leveling. We show that a graph G is radial planar if G has a radial drawing in which every two edges cross an even number of times; the radial embedding has the same leveling as the radial drawing. In other words, we establish the weak variant of the Hanani-Tutte theorem for radial planarity. This generalizes a result by Pach and Tóth.
AU - Fulek, Radoslav
AU - Pelsmajer, Michael
AU - Schaefer, Marcus
ID - 1595
TI - Hanani-Tutte for radial planarity
VL - 9411
ER -
TY - CONF
AB - Let C={C1,...,Cn} denote a collection of translates of a regular convex k-gon in the plane with the stacking order. The collection C forms a visibility clique if for everyi < j the intersection Ci and (Ci ∩ Cj)\⋃i<l<jCl =∅.elements that are stacked between them, i.e., We show that if C forms a visibility clique its size is bounded from above by O(k4) thereby improving the upper bound of 22k from the aforementioned paper. We also obtain an upper bound of 22(k/2)+2 on the size of a visibility clique for homothetes of a convex (not necessarily regular) k-gon.
AU - Fulek, Radoslav
AU - Radoičić, Radoš
ID - 1596
TI - Vertical visibility among parallel polygons in three dimensions
VL - 9411
ER -
TY - CONF
AB - The synthesis problem asks for the automatic construction of a system from its specification. In the traditional setting, the system is “constructed from scratch” rather than composed from reusable components. However, this is rare in practice, and almost every non-trivial software system relies heavily on the use of libraries of reusable components. Recently, Lustig and Vardi introduced dataflow and controlflow synthesis from libraries of reusable components. They proved that dataflow synthesis is undecidable, while controlflow synthesis is decidable. The problem of controlflow synthesis from libraries of probabilistic components was considered by Nain, Lustig and Vardi, and was shown to be decidable for qualitative analysis (that asks that the specification be satisfied with probability 1). Our main contribution for controlflow synthesis from probabilistic components is to establish better complexity bounds for the qualitative analysis problem, and to show that the more general quantitative problem is undecidable. For the qualitative analysis, we show that the problem (i) is EXPTIME-complete when the specification is given as a deterministic parity word automaton, improving the previously known 2EXPTIME upper bound; and (ii) belongs to UP ∩ coUP and is parity-games hard, when the specification is given directly as a parity condition on the components, improving the previously known EXPTIME upper bound.
AU - Chatterjee, Krishnendu
AU - Doyen, Laurent
AU - Vardi, Moshe
ID - 1609
TI - The complexity of synthesis from probabilistic components
VL - 9135
ER -
TY - CONF
AB - Multiaffine hybrid automata (MHA) represent a powerful formalism to model complex dynamical systems. This formalism is particularly suited for the representation of biological systems which often exhibit highly non-linear behavior. In this paper, we consider the problem of parameter identification for MHA. We present an abstraction of MHA based on linear hybrid automata, which can be analyzed by the SpaceEx model checker. This abstraction enables a precise handling of time-dependent properties. We demonstrate the potential of our approach on a model of a genetic regulatory network and a myocyte model.
AU - Bogomolov, Sergiy
AU - Schilling, Christian
AU - Bartocci, Ezio
AU - Batt, Grégory
AU - Kong, Hui
AU - Grosu, Radu
ID - 1605
TI - Abstraction-based parameter synthesis for multiaffine systems
VL - 9434
ER -
TY - CONF
AB - In this paper, we present the first steps toward a runtime verification framework for monitoring hybrid and cyber-physical systems (CPS) development tools based on randomized differential testing. The development tools include hybrid systems reachability analysis tools, model-based development environments like Simulink/Stateflow (SLSF), etc. First, hybrid automaton models are randomly generated. Next, these hybrid automaton models are translated to a number of different tools (currently, SpaceEx, dReach, Flow*, HyCreate, and the MathWorks’ Simulink/Stateflow) using the HyST source transformation and translation tool. Then, the hybrid automaton models are executed in the different tools and their outputs are parsed. The final step is the differential comparison: the outputs of the different tools are compared. If the results do not agree (in the sense that an analysis or verification result from one tool does not match that of another tool, ignoring timeouts, etc.), a candidate bug is flagged and the model is saved for future analysis by the user. The process then repeats and the monitoring continues until the user terminates the process. We present preliminary results that have been useful in identifying a few bugs in the analysis methods of different development tools, and in an earlier version of HyST.
AU - Nguyen, Luan
AU - Schilling, Christian
AU - Bogomolov, Sergiy
AU - Johnson, Taylor
ID - 1606
TI - Runtime verification for hybrid analysis tools
VL - 9333
ER -
TY - JOUR
AB - Background
Photosynthetic cyanobacteria are attractive for a range of biotechnological applications including biofuel production. However, due to slow growth, screening of mutant libraries using microtiter plates is not feasible.
Results
We present a method for high-throughput, single-cell analysis and sorting of genetically engineered l-lactate-producing strains of Synechocystis sp. PCC6803. A microfluidic device is used to encapsulate single cells in picoliter droplets, assay the droplets for l-lactate production, and sort strains with high productivity. We demonstrate the separation of low- and high-producing reference strains, as well as enrichment of a more productive l-lactate-synthesizing population after UV-induced mutagenesis. The droplet platform also revealed population heterogeneity in photosynthetic growth and lactate production, as well as the presence of metabolically stalled cells.
Conclusions
The workflow will facilitate metabolic engineering and directed evolution studies and will be useful in studies of cyanobacteria biochemistry and physiology.
AU - Hammar, Petter
AU - Angermayr, Andreas
AU - Sjostrom, Staffan
AU - Van Der Meer, Josefin
AU - Hellingwerf, Klaas
AU - Hudson, Elton
AU - Joensson, Hakaan
ID - 1623
IS - 1
JF - Biotechnology for Biofuels
TI - Single-cell screening of photosynthetic growth and lactate production by cyanobacteria
VL - 8
ER -
TY - JOUR
AB - Population structure can facilitate evolution of cooperation. In a structured population, cooperators can form clusters which resist exploitation by defectors. Recently, it was observed that a shift update rule is an extremely strong amplifier of cooperation in a one dimensional spatial model. For the shift update rule, an individual is chosen for reproduction proportional to fecundity; the offspring is placed next to the parent; a random individual dies. Subsequently, the population is rearranged (shifted) until all individual cells are again evenly spaced out. For large population size and a one dimensional population structure, the shift update rule favors cooperation for any benefit-to-cost ratio greater than one. But every attempt to generalize shift updating to higher dimensions while maintaining its strong effect has failed. The reason is that in two dimensions the clusters are fragmented by the movements caused by rearranging the cells. Here we introduce the natural phenomenon of a repulsive force between cells of different types. After a birth and death event, the cells are being rearranged minimizing the overall energy expenditure. If the repulsive force is sufficiently high, shift becomes a strong promoter of cooperation in two dimensions.
AU - Pavlogiannis, Andreas
AU - Chatterjee, Krishnendu
AU - Adlam, Ben
AU - Nowak, Martin
ID - 1624
JF - Scientific Reports
TI - Cellular cooperation with shift updating and repulsion
VL - 5
ER -
TY - CONF
AB - In recent years we have seen numerous improvements on 3D scanning and tracking of human faces, greatly advancing the creation of digital doubles for film and video games. However, despite the high-resolution quality of the reconstruction approaches available, current methods are unable to capture one of the most important regions of the face - the eye region. In this work we present the first method for detailed spatio-temporal reconstruction of eyelids. Tracking and reconstructing eyelids is extremely challenging, as this region exhibits very complex and unique skin deformation where skin is folded under while opening the eye. Furthermore, eyelids are often only partially visible and obstructed due to selfocclusion and eyelashes. Our approach is to combine a geometric deformation model with image data, leveraging multi-view stereo, optical flow, contour tracking and wrinkle detection from local skin appearance. Our deformation model serves as a prior that enables reconstruction of eyelids even under strong self-occlusions caused by rolling and folding skin as the eye opens and closes. The output is a person-specific, time-varying eyelid reconstruction with anatomically plausible deformations. Our high-resolution detailed eyelids couple naturally with current facial performance capture approaches. As a result, our method can largely increase the fidelity of facial capture and the creation of digital doubles.
AU - Bermano, Amit
AU - Beeler, Thabo
AU - Kozlov, Yeara
AU - Bradley, Derek
AU - Bickel, Bernd
AU - Gross, Markus
ID - 1625
IS - 4
TI - Detailed spatio-temporal reconstruction of eyelids
VL - 34
ER -
TY - CONF
AB - This paper introduces "OmniAD," a novel data-driven pipeline to model and acquire the aerodynamics of three-dimensional rigid objects. Traditionally, aerodynamics are examined through elaborate wind tunnel experiments or expensive fluid dynamics computations, and are only measured for a small number of discrete wind directions. OmniAD allows the evaluation of aerodynamic forces, such as drag and lift, for any incoming wind direction using a novel representation based on spherical harmonics. Our datadriven technique acquires the aerodynamic properties of an object simply by capturing its falling motion using a single camera. Once model parameters are estimated, OmniAD enables realistic realtime simulation of rigid bodies, such as the tumbling and gliding of leaves, without simulating the surrounding air. In addition, we propose an intuitive user interface based on OmniAD to interactively design three-dimensional kites that actually fly. Various nontraditional kites were designed to demonstrate the physical validity of our model.
AU - Martin, Tobias
AU - Umetani, Nobuyuki
AU - Bickel, Bernd
ID - 1626
IS - 4
TI - OmniAD: Data-driven omni-directional aerodynamics
VL - 34
ER -
TY - CONF
AB - We present a computational tool for fabrication-oriented design of flexible rod meshes. Given a deformable surface and a set of deformed poses as input, our method automatically computes a printable rod mesh that, once manufactured, closely matches the input poses under the same boundary conditions. The core of our method is formed by an optimization scheme that adjusts the cross-sectional profiles of the rods and their rest centerline in order to best approximate the target deformations. This approach allows us to locally control the bending and stretching resistance of the surface with a single material, yielding high design flexibility and low fabrication cost.
AU - Pérez, Jesús
AU - Thomaszewski, Bernhard
AU - Coros, Stelian
AU - Bickel, Bernd
AU - Canabal, José
AU - Sumner, Robert
AU - Otaduy, Miguel
ID - 1627
IS - 4
TI - Design and fabrication of flexible rod meshes
VL - 34
ER -
TY - CONF
AB - We propose a method for fabricating deformable objects with spatially varying elasticity using 3D printing. Using a single, relatively stiff printer material, our method designs an assembly of smallscale microstructures that have the effect of a softer material at the object scale, with properties depending on the microstructure used in each part of the object. We build on work in the area of metamaterials, using numerical optimization to design tiled microstructures with desired properties, but with the key difference that our method designs families of related structures that can be interpolated to smoothly vary the material properties over a wide range. To create an object with spatially varying elastic properties, we tile the object's interior with microstructures drawn from these families, generating a different microstructure for each cell using an efficient algorithm to select compatible structures for neighboring cells. We show results computed for both 2D and 3D objects, validating several 2D and 3D printed structures using standard material tests as well as demonstrating various example applications.
AU - Schumacher, Christian
AU - Bickel, Bernd
AU - Rys, Jan
AU - Marschner, Steve
AU - Daraio, Chiara
AU - Gross, Markus
ID - 1628
IS - 4
TI - Microstructures to control elasticity in 3D printing
VL - 34
ER -
TY - CONF
AB - We present a method to learn and propagate shape placements in 2D polygonal scenes from a few examples provided by a user. The placement of a shape is modeled as an oriented bounding box. Simple geometric relationships between this bounding box and nearby scene polygons define a feature set for the placement. The feature sets of all example placements are then used to learn a probabilistic model over all possible placements and scenes. With this model, we can generate a new set of placements with similar geometric relationships in any given scene. We introduce extensions that enable propagation and generation of shapes in 3D scenes, as well as the application of a learned modeling session to large scenes without additional user interaction. These concepts allow us to generate complex scenes with thousands of objects with relatively little user interaction.
AU - Guerrero, Paul
AU - Jeschke, Stefan
AU - Wimmer, Michael
AU - Wonka, Peter
ID - 1630
IS - 4
TI - Learning shape placements by example
VL - 34
ER -
TY - CONF
AB - This paper presents a liquid simulation technique that enforces the incompressibility condition using a stream function solve instead of a pressure projection. Previous methods have used stream function techniques for the simulation of detailed single-phase flows, but a formulation for liquid simulation has proved elusive in part due to the free surface boundary conditions. In this paper, we introduce a stream function approach to liquid simulations with novel boundary conditions for free surfaces, solid obstacles, and solid-fluid coupling.
Although our approach increases the dimension of the linear system necessary to enforce incompressibility, it provides interesting and surprising benefits. First, the resulting flow is guaranteed to be divergence-free regardless of the accuracy of the solve. Second, our free-surface boundary conditions guarantee divergence-free motion even in the un-simulated air phase, which enables two-phase flow simulation by only computing a single phase. We implemented this method using a variant of FLIP simulation which only samples particles within a narrow band of the liquid surface, and we illustrate the effectiveness of our method for detailed two-phase flow simulations with complex boundaries, detailed bubble interactions, and two-way solid-fluid coupling.
AU - Ando, Ryoichi
AU - Thuerey, Nils
AU - Wojtan, Christopher J
ID - 1632
IS - 4
TI - A stream function solver for liquid simulations
VL - 34
ER -
TY - JOUR
AB - Biosensors for signaling molecules allow the study of physiological processes by bringing together the fields of protein engineering, fluorescence imaging, and cell biology. Construction of genetically encoded biosensors generally relies on the availability of a binding "core" that is both specific and stable, which can then be combined with fluorescent molecules to create a sensor. However, binding proteins with the desired properties are often not available in nature and substantial improvement to sensors can be required, particularly with regard to their durability. Ancestral protein reconstruction is a powerful protein-engineering tool able to generate highly stable and functional proteins. In this work, we sought to establish the utility of ancestral protein reconstruction to biosensor development, beginning with the construction of an l-arginine biosensor. l-arginine, as the immediate precursor to nitric oxide, is an important molecule in many physiological contexts including brain function. Using a combination of ancestral reconstruction and circular permutation, we constructed a Förster resonance energy transfer (FRET) biosensor for l-arginine (cpFLIPR). cpFLIPR displays high sensitivity and specificity, with a Kd of ∼14 μM and a maximal dynamic range of 35%. Importantly, cpFLIPR was highly robust, enabling accurate l-arginine measurement at physiological temperatures. We established that cpFLIPR is compatible with two-photon excitation fluorescence microscopy and report l-arginine concentrations in brain tissue.
AU - Whitfield, Jason
AU - Zhang, William
AU - Herde, Michel
AU - Clifton, Ben
AU - Radziejewski, Johanna
AU - Janovjak, Harald L
AU - Henneberger, Christian
AU - Jackson, Colin
ID - 1611
IS - 9
JF - Protein Science
TI - Construction of a robust and sensitive arginine biosensor through ancestral protein reconstruction
VL - 24
ER -
TY - JOUR
AB - GABAergic perisoma-inhibiting fast-spiking interneurons (PIIs) effectively control the activity of large neuron populations by their wide axonal arborizations. It is generally assumed that the output of one PII to its target cells is strong and rapid. Here, we show that, unexpectedly, both strength and time course of PII-mediated perisomatic inhibition change with distance between synaptically connected partners in the rodent hippocampus. Synaptic signals become weaker due to lower contact numbers and decay more slowly with distance, very likely resulting from changes in GABAA receptor subunit composition. When distance-dependent synaptic inhibition is introduced to a rhythmically active neuronal network model, randomly driven principal cell assemblies are strongly synchronized by the PIIs, leading to higher precision in principal cell spike times than in a network with uniform synaptic inhibition.
AU - Strüber, Michael
AU - Jonas, Peter M
AU - Bartos, Marlene
ID - 1614
IS - 4
JF - PNAS
TI - Strength and duration of perisomatic GABAergic inhibition depend on distance between synaptically connected cells
VL - 112
ER -
TY - JOUR
AB - Loss-of-function mutations in the synaptic adhesion protein Neuroligin-4 are among the most common genetic abnormalities associated with autism spectrum disorders, but little is known about the function of Neuroligin-4 and the consequences of its loss. We assessed synaptic and network characteristics in Neuroligin-4 knockout mice, focusing on the hippocampus as a model brain region with a critical role in cognition and memory, and found that Neuroligin-4 deletion causes subtle defects of the protein composition and function of GABAergic synapses in the hippocampal CA3 region. Interestingly, these subtle synaptic changes are accompanied by pronounced perturbations of γ-oscillatory network activity, which has been implicated in cognitive function and is altered in multiple psychiatric and neurodevelopmental disorders. Our data provide important insights into the mechanisms by which Neuroligin-4-dependent GABAergic synapses may contribute to autism phenotypes and indicate new strategies for therapeutic approaches.
AU - Hammer, Matthieu
AU - Krueger Burg, Dilja
AU - Tuffy, Liam
AU - Cooper, Benjamin
AU - Taschenberger, Holger
AU - Goswami, Sarit
AU - Ehrenreich, Hannelore
AU - Jonas, Peter M
AU - Varoqueaux, Frederique
AU - Rhee, Jeong
AU - Brose, Nils
ID - 1615
IS - 3
JF - Cell Reports
TI - Perturbed hippocampal synaptic inhibition and γ-oscillations in a neuroligin-4 knockout mouse model of autism
VL - 13
ER -
TY - JOUR
AB - CCL19 and CCL21 are chemokines involved in the trafficking of immune cells, particularly within the lymphatic system, through activation of CCR7. Concurrent expression of PSGL-1 and CCR7 in naive T-cells enhances recruitment of these cells to secondary lymphoid organs by CCL19 and CCL21. Here the solution structure of CCL19 is reported. It contains a canonical chemokine domain. Chemical shift mapping shows the N-termini of PSGL-1 and CCR7 have overlapping binding sites for CCL19 and binding is competitive. Implications for the mechanism of PSGL-1's enhancement of resting T-cell recruitment are discussed.
AU - Veldkamp, Christopher
AU - Kiermaier, Eva
AU - Gabel Eissens, Skylar
AU - Gillitzer, Miranda
AU - Lippner, David
AU - Disilvio, Frank
AU - Mueller, Casey
AU - Wantuch, Paeton
AU - Chaffee, Gary
AU - Famiglietti, Michael
AU - Zgoba, Danielle
AU - Bailey, Asha
AU - Bah, Yaya
AU - Engebretson, Samantha
AU - Graupner, David
AU - Lackner, Emily
AU - Larosa, Vincent
AU - Medeiros, Tysha
AU - Olson, Michael
AU - Phillips, Andrew
AU - Pyles, Harley
AU - Richard, Amanda
AU - Schoeller, Scott
AU - Touzeau, Boris
AU - Williams, Larry
AU - Sixt, Michael K
AU - Peterson, Francis
ID - 1618
IS - 27
JF - Biochemistry
TI - Solution structure of CCL19 and identification of overlapping CCR7 and PSGL-1 binding sites
VL - 54
ER -
TY - CONF
AB - Simulating the delightful dynamics of soap films, bubbles, and foams has traditionally required the use of a fully three-dimensional many-phase Navier-Stokes solver, even though their visual appearance is completely dominated by the thin liquid surface. We depart from earlier work on soap bubbles and foams by noting that their dynamics are naturally described by a Lagrangian vortex sheet model in which circulation is the primary variable. This leads us to derive a novel circulation-preserving surface-only discretization of foam dynamics driven by surface tension on a non-manifold triangle mesh. We represent the surface using a mesh-based multimaterial surface tracker which supports complex bubble topology changes, and evolve the surface according to the ambient air flow induced by a scalar circulation field stored on the mesh. Surface tension forces give rise to a simple update rule for circulation, even at non-manifold Plateau borders, based on a discrete measure of signed scalar mean curvature. We further incorporate vertex constraints to enable the interaction of soap films with wires. The result is a method that is at once simple, robust, and efficient, yet able to capture an array of soap films behaviors including foam rearrangement, catenoid collapse, blowing bubbles, and double bubbles being pulled apart.
AU - Da, Fang
AU - Batty, Christopher
AU - Wojtan, Christopher J
AU - Grinspun, Eitan
ID - 1634
IS - 4
TI - Double bubbles sans toil and trouble: discrete circulation-preserving vortex sheets for soap films and foams
VL - 34
ER -
TY - JOUR
AB - We calculate a Ricci curvature lower bound for some classical examples of random walks, namely, a chain on a slice of the n-dimensional discrete cube (the so-called Bernoulli-Laplace model) and the random transposition shuffle of the symmetric group of permutations on n letters.
AU - Erbar, Matthias
AU - Maas, Jan
AU - Tetali, Prasad
ID - 1635
IS - 4
JF - Annales de la faculté des sciences de Toulouse
TI - Discrete Ricci curvature bounds for Bernoulli-Laplace and random transposition models
VL - 24
ER -
TY - CONF
AB - Constraint Satisfaction Problem (CSP) is a fundamental algorithmic problem that appears in many areas of Computer Science. It can be equivalently stated as computing a homomorphism R→ΓΓ between two relational structures, e.g. between two directed graphs. Analyzing its complexity has been a prominent research direction, especially for the fixed template CSPs where the right side ΓΓ is fixed and the left side R is unconstrained.
Far fewer results are known for the hybrid setting that restricts both sides simultaneously. It assumes that R belongs to a certain class of relational structures (called a structural restriction in this paper). We study which structural restrictions are effective, i.e. there exists a fixed template ΓΓ (from a certain class of languages) for which the problem is tractable when R is restricted, and NP-hard otherwise. We provide a characterization for structural restrictions that are closed under inverse homomorphisms. The criterion is based on the chromatic number of a relational structure defined in this paper; it generalizes the standard chromatic number of a graph.
As our main tool, we use the algebraic machinery developed for fixed template CSPs. To apply it to our case, we introduce a new construction called a “lifted language”. We also give a characterization for structural restrictions corresponding to minor-closed families of graphs, extend results to certain Valued CSPs (namely conservative valued languages), and state implications for (valued) CSPs with ordered variables and for the maximum weight independent set problem on some restricted families of graphs.
AU - Kolmogorov, Vladimir
AU - Rolinek, Michal
AU - Takhanov, Rustem
ID - 1636
TI - Effectiveness of structural restrictions for hybrid CSPs
VL - 9472
ER -
TY - JOUR
AB - The mitochondrial respiratory chain, also known as the electron transport chain (ETC), is crucial to life, and energy production in the form of ATP is the main mitochondrial function. Three proton-translocating enzymes of the ETC, namely complexes I, III and IV, generate proton motive force, which in turn drives ATP synthase (complex V). The atomic structures and basic mechanisms of most respiratory complexes have previously been established, with the exception of complex I, the largest complex in the ETC. Recently, the crystal structure of the entire complex I was solved using a bacterial enzyme. The structure provided novel insights into the core architecture of the complex, the electron transfer and proton translocation pathways, as well as the mechanism that couples these two processes.
AU - Sazanov, Leonid A
ID - 1638
IS - 6
JF - Nature Reviews Molecular Cell Biology
TI - A giant molecular proton pump: structure and mechanism of respiratory complex I
VL - 16
ER -
TY - JOUR
AB - In this paper the optimal transport and the metamorphosis perspectives are combined. For a pair of given input images geodesic paths in the space of images are defined as minimizers of a resulting path energy. To this end, the underlying Riemannian metric measures the rate of transport cost and the rate of viscous dissipation. Furthermore, the model is capable to deal with strongly varying image contrast and explicitly allows for sources and sinks in the transport equations which are incorporated in the metric related to the metamorphosis approach by Trouvé and Younes. In the non-viscous case with source term existence of geodesic paths is proven in the space of measures. The proposed model is explored on the range from merely optimal transport to strongly dissipative dynamics. For this model a robust and effective variational time discretization of geodesic paths is proposed. This requires to minimize a discrete path energy consisting of a sum of consecutive image matching functionals. These functionals are defined on corresponding pairs of intensity functions and on associated pairwise matching deformations. Existence of time discrete geodesics is demonstrated. Furthermore, a finite element implementation is proposed and applied to instructive test cases and to real images. In the non-viscous case this is compared to the algorithm proposed by Benamou and Brenier including a discretization of the source term. Finally, the model is generalized to define discrete weighted barycentres with applications to textures and objects.
AU - Maas, Jan
AU - Rumpf, Martin
AU - Schönlieb, Carola
AU - Simon, Stefan
ID - 1639
IS - 6
JF - ESAIM: Mathematical Modelling and Numerical Analysis
TI - A generalized model for optimal transport of images including dissipation and density modulation
VL - 49
ER -
TY - JOUR
AB - Auxin and cytokinin are key endogenous regulators of plant development. Although cytokinin-mediated modulation of auxin distribution is a developmentally crucial hormonal interaction, its molecular basis is largely unknown. Here we show a direct regulatory link between cytokinin signalling and the auxin transport machinery uncovering a mechanistic framework for cytokinin-auxin cross-talk. We show that the CYTOKININ RESPONSE FACTORS (CRFs), transcription factors downstream of cytokinin perception, transcriptionally control genes encoding PIN-FORMED (PIN) auxin transporters at a specific PIN CYTOKININ RESPONSE ELEMENT (PCRE) domain. Removal of this cis-regulatory element effectively uncouples PIN transcription from the CRF-mediated cytokinin regulation and attenuates plant cytokinin sensitivity. We propose that CRFs represent a missing cross-talk component that fine-tunes auxin transport capacity downstream of cytokinin signalling to control plant development.
AU - Šimášková, Mária
AU - O'Brien, José
AU - Khan-Djamei, Mamoona
AU - Van Noorden, Giel
AU - Ötvös, Krisztina
AU - Vieten, Anne
AU - De Clercq, Inge
AU - Van Haperen, Johanna
AU - Cuesta, Candela
AU - Hoyerová, Klára
AU - Vanneste, Steffen
AU - Marhavy, Peter
AU - Wabnik, Krzysztof T
AU - Van Breusegem, Frank
AU - Nowack, Moritz
AU - Murphy, Angus
AU - Friml, Jiřĺ
AU - Weijers, Dolf
AU - Beeckman, Tom
AU - Benková, Eva
ID - 1640
JF - Nature Communications
TI - Cytokinin response factors regulate PIN-FORMED auxin transporters
VL - 6
ER -
TY - JOUR
AB - The Hanani-Tutte theorem is a classical result proved for the first time in the 1930s that characterizes planar graphs as graphs that admit a drawing in the plane in which every pair of edges not sharing a vertex cross an even number of times. We generalize this result to clustered graphs with two disjoint clusters, and show that a straightforward extension to flat clustered graphs with three or more disjoint clusters is not possible. For general clustered graphs we show a variant of the Hanani-Tutte theorem in the case when each cluster induces a connected subgraph. Di Battista and Frati proved that clustered planarity of embedded clustered graphs whose every face is incident to at most five vertices can be tested in polynomial time. We give a new and short proof of this result, using the matroid intersection algorithm.
AU - Fulek, Radoslav
AU - Kynčl, Jan
AU - Malinovič, Igor
AU - Pálvölgyi, Dömötör
ID - 1642
IS - 4
JF - Electronic Journal of Combinatorics
TI - Clustered planarity testing revisited
VL - 22
ER -