TY - JOUR AB - Input-dependent left-right asymmetry of NMDA receptor ε2 (NR2B) subunit allocation was discovered in hippocampal Schaffer collateral (Sch) and commissural fiber pyramidal cell synapses (Kawakami et al., 2003). To investigate whether this asymmetrical ε2 allocation is also related to the types of the postsynaptic cells, we compared postembedding immunogold labeling for ε2 in left and right Sch synapses on pyramidal cells and interneurons. To facilitate the detection of ε2 density difference, we used ε1 (NR2A) knock-out (KO) mice, which have a simplified NMDA receptor subunit composition. The labeling density for ε2 but not ζ1 (NR1) and subtype 2/3 glutamate receptor (GluR2/3) in Sch-CA1 pyramidal cell synapses was significantly different between the left and right hippocampus with opposite directions in strata oriens and radiatum; the left to right ratio of ε2 labeling density was 1:1.50 in stratum oriens and 1.44:1 in stratum radiatum. No significant difference, however, was detected in CA1 stratum radiatum between the left and right Sch-GluR4-positive (mostly parvalbumin-positive) and Sch-GluR4-negative interneuron synapses. Consistent with the anatomical asymmetry, the amplitude ratio of NMDA EPSCs to non-NMDA EPSCs in pyramidal cells was approximately two times larger in right than left stratum radiatum and vice versa in stratum oriens of ε1 KO mice. Moreover, the amplitude of long-term potentiation in the Sch-CA1 synapses of left stratum radiatum was significantly larger than that in the right corresponding synapses. These results indicate that the asymmetry of ε2 distribution is target cell specific, resulting in the left-right difference in NMDA receptor content and plasticity in Sch-CA1 pyramidal cell synapses in ε1 KO mice. AU - Wu, Yue AU - Kawakami, Ryosuke AU - Shinohara, Yoshiaki AU - Fukaya, Masahiro AU - Sakimura, Kenji AU - Mishina, Masayoshi AU - Watanabe, Masahiko AU - Ito, Isao AU - Ryuichi Shigemoto ID - 2655 IS - 40 JF - Journal of Neuroscience TI - Target-cell-specific left-right asymmetry of NMDA receptor content in Schaffer collateral synapses in ε1/NR2A knock-out mice VL - 25 ER - TY - JOUR AB - Synaptic vesicle release occurs at a specialized membrane domain known as the presynaptic active zone (AZ). Several membrane proteins are involved in the vesicle release processes such as docking, priming, and exocytotic fusion. Cytomatrix at the active zone (CAZ) proteins are structural components of the AZ and are highly concentrated in it. Localization of other release-related proteins including target soluble N-ethylmaleimide-sensitive-factor attachment protein receptor (t-SNARE) proteins, however, has not been well demonstrated in the AZ. Here, we used sodium dodecyl sulfate-digested freeze-fracture replica labeling (SDS-FRL) to analyze quantitatively the distribution of CAZ and t-SNARE proteins in the hippocampal CA3 area. The AZ in replicated membrane was identified by immunolabeling for CAZ proteins (CAZ-associated structural protein [CAST] and Bassoon). Clusters of immunogold particles for these proteins were found on the P-face of presynaptic terminals of the mossy fiber and associational/commissural (AJC) fiber. Co-labeling with CAST revealed distribution of the t-SNARE proteins syntaxin and synaptosomal-associated protein of 25 kDa (SNAP-25) in the AZ as well as in the extrasynaptic membrane surrounding the AZ (SZ). Quantitative analysis demonstrated that the density of immunoparticles for CAST in the AZ was more than 100 times higher than in the SZ, whereas that for syntaxin and SNAP-25 was not significantly different between the AZ and SZ in both the A/C and mossy fiber terminals. These results support the involvement of the t-SNARE proteins in exocytotic fusion in the AZ and the role of CAST in specialization of the membrane domain for the AZ. AU - Hagiwara, Akari AU - Fukazawa, Yugo AU - Deguchi-Tawarada, Maki AU - Ohtsuka, Toshihisa AU - Ryuichi Shigemoto ID - 2653 IS - 2 JF - Journal of Comparative Neurology TI - Differential distribution of release-related proteins in the hippocampal CA3 area as revealed by freeze-fracture replica labeling VL - 489 ER - TY - JOUR AB - Previous studies have shown that neurons in the sacral dorsal commissural nucleus (SDCN) express neurokinin-1 receptor (NK1R) and can be modulated by the co-release of GABA and glycine (Gly) from single presynaptic terminal. These results raise the possibility that GABA/Gly-cocontaining terminals might make synaptic contacts with NK1R-expressing neurons in the SDCN. In order to provide morphological evidence for this hypothesis, the triple-immunohistochemical studies were performed in the SDCN. Triple-immunofluorescence histochemical study showed that some axon terminals in close association with NK1R-immunopositive (NK1R-ip) neurons in the SDCN were immunopositive for both glutamic acid decarboxylase (GAD) and glycine transporter 2 (GlyT2). In electron microscopic dual- and triple-immunohistochemistry for GAD/GlyT2, GAD/NK1R, GlyT2/NK1R, or GAD/GlyT2/NK1R also revealed dually labeled (GAD/GlyT2-ip) synaptic terminals upon SDCN neurons, as well as GAD- and/or GlyT2-ip axon terminals in synaptic contact with NK1R-ip SDCN neurons. These results suggested that some synaptic terminals upon NK1R-expressing SDCN neurons co-released both GABA and Gly. AU - Feng, Yu-Peng AU - Li, Yun-Qing AU - Wang, Wen AU - Wu, Sheng-Xi AU - Chen, Tao AU - Ryuichi Shigemoto AU - Mizuno, Noboru ID - 2656 IS - 3 JF - Neuroscience Letters TI - Morphological evidence for GABA/glycine-cocontaining terminals in synaptic contact with neurokinin-1 receptor-expressing neurons in the sacral dorsal commissural nucleus of the rat VL - 388 ER - TY - JOUR AB - We study the long time evolution of a quantum particle interacting with a random potential in the Boltzmann-Grad low density limit. We prove that the phase space density of the quantum evolution defined through the Husimi function converges weakly to a linear Boltzmann equation. The Boltzmann collision kernel is given by the full quantum scattering cross-section of the obstacle potential. AU - Eng, David AU - László Erdös ID - 2744 IS - 6 JF - Reviews in Mathematical Physics TI - The linear Boltzmann equation as the low density limit of a random Schrödinger equation VL - 17 ER - TY - JOUR AB - We consider the supersymmetric quantum mechanical system which is obtained by dimensionally reducing d = 6, N = 1 supersymmetric gauge theory with gauge group U(1) and a single charged hypermultiplet. Using the deformation method and ideas introduced by Porrati and Rozenberg [1], we present a detailed proof of the existence of a normalizable ground state for this system. AU - László Erdös AU - Hasler, David G AU - Solovej, Jan P ID - 2743 IS - 2 JF - Annales Henri Poincare TI - Existence of the D0-D4 bound state: A detailed proof VL - 6 ER - TY - JOUR AB - We present the results of an experimental investigation into the nature and structure of turbulent pipe flow at moderate Reynolds numbers. A turbulence regeneration mechanism is identified which sustains a symmetric traveling wave within the flow. The periodicity of the mechanism allows comparison to the wavelength of numerically observed exact traveling wave solutions and close agreement is found. The advection speed of the upstream turbulence laminar interface in the experimental flow is observed to form a lower bound on the phase velocities of the exact traveling wave solutions. Overall our observations suggest that the dynamics of the turbulent flow at moderate Reynolds numbers are governed by unstable nonlinear traveling waves. AU - Björn Hof AU - van Doorne, Casimir W AU - Westerweel, Jerry AU - Nieuwstadt, Frans T ID - 2788 IS - 21 JF - Physical Review Letters TI - Turbulence regeneration in pipe flow at moderate reynolds numbers VL - 95 ER - TY - JOUR AB - We present the results of an experimental investigation of the effect of a magnetic field on the stability of convection in a liquid metal. A rectangular container of gallium is subjected to a horizontal temperature gradient and a uniform magnetic field is applied separately in three directions. The magnetic field suppresses the oscillation most effectively when it is applied in the vertical direction and is least efficient when applied in the direction of the temperature gradient. The critical temperature difference required for the onset of oscillations is found to scale exponentially with the magnitude of the magnetic field for all three orientations. Comparisons are made with available theory and qualitative differences are discussed. AU - Björn Hof AU - Juel, Anne AU - Mullin, Tom P ID - 2790 JF - Journal of Fluid Mechanics TI - Magnetohydrodynamic damping of oscillations in low-Prandtl-number convection VL - 545 ER - TY - JOUR AB - Transitional pipe flow is investigated in two different experimental set-ups. In the first the stability threshold and the initial growth of localized perturbations are studied. Good agreement is found with an earlier investigation of the transition threshold. The measurement technique applied in the last part of this study allows the reconstruction of the streamwise vorticity in a turbulent puff. AU - Björn Hof ID - 2789 JF - Fluid Mechanics and its Applications TI - Transition to turbulence in pipe flow VL - 77 ER - TY - JOUR AB - The plant hormone auxin elicits many specific context-dependent developmental responses. Auxin promotes degradation of Aux/IAA proteins that prevent transcription factors of the auxin response factor (ARF) family from regulating auxin-responsive target genes. Aux/IAAs and ARFs are represented by large gene families in Arabidopsis. Here we show that stabilization of BDL/IAA12 or its sister protein IAA13 prevents MP/ARF5-dependent embryonic root formation whereas stabilized SHY2/IAA3 interferes with seedling growth. Although both bdl and shy2-2 proteins inhibited MP/ARF5-dependent reporter gene activation, shy2-2 was much less efficient than bdl to interfere with embryonic root initiation when expressed from the BDL promoter. Similarly, MP was much more efficient than ARF16 in this process. When expressed from the SHY2 promoter, both shy2-2 and bdl inhibited cell elongation and auxin-induced gene expression in the seedling hypocotyl. By contrast, gravitropism and auxin-induced gene expression in the root, which were promoted by functionally redundant NPH4/ARF7 and ARF19 proteins, were inhibited by shy2-2, but not by bdl protein. Our results suggest that auxin signals are converted into specific responses by matching pairs of coexpressed ARF and Aux/IAA proteins. AU - Weijers, Dolf AU - Eva Benková AU - Jäger, Katja E AU - Schlereth, Alexandra AU - Hamann, Thorsten AU - Kientz, Marika AU - Wilmoth, Jill C AU - Reed, Jason W AU - Jürgens, Gerd ID - 2867 IS - 10 JF - EMBO Journal TI - Developmental specificity of auxin response by pairs of ARF and Aux/IAA transcriptional regulators VL - 24 ER - TY - JOUR AB - One of the fundamental properties of the immune system is its capacity to avoid autoimmune diseases. The mechanism underlying this process, known as self-tolerance, is hitherto unresolved but seems to involve the control of clonal expansion of autoreactive lymphocytes. This article reviews mathematical modeling of self-tolerance, addressing two specific hypotheses. The first hypothesis posits that self-tolerance is mediated by tuning of activation thresholds, which makes autoreactive T lymphocytes reversibly "anergic" and unable to proliferate. The second hypothesis posits that the proliferation of autoreactive T lymphocytes is instead controlled by specific regulatory T lymphocytes. Models representing the population dynamics of autoreactive T lymphocytes according to these two hypotheses were derived. For each model we identified how cell density affects tolerance, and predicted the corresponding phase spaces and bifurcations. We show that the simple induction of proliferative anergy, as modeled here, has a density dependence that is only partially compatible with adoptive transfers of tolerance, and that the models of tolerance mediated by specific regulatory T cells are closer to the observations. AU - Carneiro, Jorge AU - Tiago Paixao AU - Milutinovic, Dejan AU - Sousa, João AU - Leon, Kalet AU - Gardner, Rui AU - Faro, Jose ID - 2895 IS - 1 JF - Journal of Computational and Applied Mathematics TI - Immunological self tolerance: Lessons from mathematical modeling VL - 184 ER - TY - JOUR AB - Molecular mechanisms of pattern formation in the plant embryo are not well understood. Recent molecular and cellular studies, in conjunction with earlier microsurgical, physiological, and genetic work, are now starting to define the outlines of a model where gradients of the signaling molecule auxin play a central role in embryo patterning. It is relatively clear how these gradients are established and interpreted, but how they are maintained is still unresolved. Here, we have studied the contributions of auxin biosynthesis, conjugation, and transport pathways to the maintenance of embryonic auxin gradients. Auxin homeostasis in the embryo was manipulated by region-specific conditional expression of indoleacetic acid-tryptophan monooxygenase or indoleacetic acid-lysine synthetase, bacterial enzymes for auxin biosynthesis or conjugation. Neither manipulation of auxin biosynthesis nor of auxin conjugation interfered with auxin gradients and patterning in the embryo. This result suggests a compensatory mechanism for buffering auxin gradients in the embryo. Chemical and genetic inhibition revealed that auxin transport activity, in particular that of the PIN-FORMED1 (PIN1) and PIN4 proteins, is a major factor in the maintenance of these gradients. AU - Weijers, Dolf AU - Sauer, Michael AU - Meurette, Olivier AU - Jirí Friml AU - Ljung, Karin AU - Sandberg, Göran AU - Hooykaas, Paul AU - Offringa, Remko ID - 3004 IS - 9 JF - Plant Cell TI - Maintenance of embryonic auxin distribution for apical basal patterning by PIN FORMED dependent auxin transport in Arabidopsis VL - 17 ER - TY - JOUR AB - In plants, cell polarity is an issue more recurring than in other systems, because plants, due to their adaptive and flexible development, often change cell polarity postembryonically according to intrinsic cues and demands of the environment. Recent findings on the directional movement of the plant signalling molecule auxin provide a unique connection between individual cell polarity and the establishment of polarity at the tissue, organ, and whole-plant levels. Decisions about the subcellular polar targeting of PIN auxin transport components determine the direction of auxin flow between cells and consequently mediate multiple developmental events. In addition, mutations or chemical interference with PIN-based auxin transport result in abnormal cell divisions. Thus, the complicated links between cell polarity establishment, auxin transport, cytoskeleton, and oriented cell divisions now begin to emerge. Here we review the available literature on the issues of cell polarity in both plants and animals to extend our understanding on the generation, maintenance, and transmission of cell polarity in plants. AU - Dhonukshe, Pankaj AU - Kleine Vehn, Jürgen AU - Friml, Jirí ID - 3000 IS - 1-2 JF - Protoplasma TI - Cell polarity, auxin transport and cytoskeleton mediated division planes: Who comes first? VL - 226 ER - TY - JOUR AB - One of the mechanisms by which signalling molecules regulate cellular behaviour is modulating subcellular protein translocation. This mode of regulation is often based on specialized vesicle trafficking, termed constitutive cycling, which consists of repeated internalization and recycling of proteins to and from the plasma membrane. No such mechanism of hormone action has been shown in plants although several proteins, including the PIN auxin efflux facilitators, exhibit constitutive cycling. Here we show that a major regulator of plant development, auxin, inhibits endocytosis. This effect is specific to biologically active auxins and requires activity of the Calossin-like protein BIG. By inhibiting the internalization step of PIN constitutive cycling, auxin increases levels of PINs at the plasma membrane. Concomitantly, auxin promotes its own efflux from cells by a vesicle-trafficking-dependent mechanism. Furthermore, asymmetric auxin translocation during gravitropism is correlated with decreased PIN internalization. Our data imply a previously undescribed mode of plant hormone action: by modulating PIN protein trafficking, auxin regulates PIN abundance and activity at the cell surface, providing a mechanism for the feedback regulation of auxin transport. AU - Paciorek, Tomasz AU - Zažímalová, Eva AU - Ruthardt, Nadia AU - Petrášek, Jan AU - Stierhof, York-Dieter AU - Kleine-Vehn, Jürgen AU - Morris, David A AU - Emans, Neil AU - Jürgens, Gerd AU - Geldner, Niko AU - Jirí Friml ID - 3001 IS - 7046 JF - Nature TI - Auxin inhibits endocytosis and promotes its own efflux from cells VL - 435 ER - TY - JOUR AB - Plant development displays an exceptional plasticity and adaptability that involves the dynamic, asymmetric distribution of the phytohormone auxin. Polar auxin flow, which requires polarly localized transport facilitators of the PIN family, largely contributes to the establishment and maintenance of the auxin gradients. Functionally overlapping action of PIN proteins mediates multiple developmental processes, including embryo formation, organ development and tropisms. Here we show that PIN proteins exhibit synergistic interactions, which involve cross-regulation of PIN gene expression in pin mutants or plants with inhibited auxin transport. Auxin itself positively feeds back on PIN gene expression in a tissue-specific manner through an AUX/IAA-dependent signalling pathway. This regulatory switch is indicative of a mechanism by which the loss of a specific PIN protein is compensated for by auxin-dependent ectopic: expression of its homologues. The compensatory properties of the PIN-dependent transport network might enable the stabilization of auxin gradients and potentially contribute to the robustness of plant adaptive development. AU - Vieten, Anne AU - Vanneste, Steffen AU - Wiśniewska, Justyna AU - Eva Benková AU - Benjamins, René AU - Beeckman, Tom AU - Luschnig, Christian AU - Jirí Friml ID - 3003 IS - 20 JF - Development TI - Functional redundancy of PIN proteins is accompanied by auxin-dependent cross-regulation of PIN expression VL - 132 ER - TY - CONF AB - The Full-Domain Hash (FDH) signature scheme [3] forms one the most basic usages of random oracles. It works with a family F of trapdoor permutations (TDP), where the signature of m is computed as f−1(h(m)) (here f ∈R F and h is modelled as a random oracle). It is known to be existentially unforgeable for any TDP family F [3], although a much tighter security reduction is known for a restrictive class of TDP’s [10,14] — namely, those induced by a family of claw-free permutations (CFP) pairs. The latter result was shown [11] to match the best possible “black-box” security reduction in the random oracle model, irrespective of the TDP family F (e.g., RSA) one might use. In this work we investigate the question if it is possible to instantiate the random oracle h with a “real” family of hash functions H such that the corresponding schemes can be proven secure in the standard model, under some natural assumption on the family F. Our main result rules out the existence of such instantiations for any assumption on F which (1) is satisfied by a family of random permutations; and (2) does not allow the attacker to invert f ∈R F on an a-priori unbounded number of points. Moreover, this holds even if the choice of H can arbitrarily depend on f. As an immediate corollary, we rule out instantiating FDH based on general claw-free permutations, which shows that in order to prove the security of FDH in the standard model one must utilize significantly more structure on F than what is sufficient for the best proof of security in the random oracle model. AU - Dodis, Yevgeniy AU - Oliveira, Roberto AU - Krzysztof Pietrzak ID - 3212 TI - On the generic insecurity of the full domain hash VL - 3621 ER - TY - CONF AB - We study the question whether the sequential or parallel composition of two functions, each indistinguishable from a random function by non-adaptive distinguishers is secure against adaptive distinguishers. The sequential composition of F and G is the function G(F()), the parallel composition is F G where ⋆ is some group operation. It has been shown that composition indeed gives adaptive security in the information theoretic setting, but unfortunately the proof does not translate into the more interesting computational case. In this work we show that in the computational setting composition does not imply adaptive security: If there is a prime order cyclic group where the decisional Diffie-Hellman assumption holds, then there are functions F and G which are indistinguishable by non-adaptive polynomially time-bounded adversaries, but whose parallel composition can be completely broken (i.e. we recover the key) with only three adaptive queries. We give a similar result for sequential composition. Interestingly, we need a standard assumption from the asymmetric (aka. public-key) world to prove a negative result for symmetric (aka. private-key) systems. AU - Krzysztof Pietrzak ID - 3213 TI - Composition does not imply adaptive security VL - 3621 ER - TY - CONF AB - We present an improved bound on the advantage of any q-query adversary at distinguishing between the CBC MAC over a random n-bit permutation and a random function outputting n bits. The result assumes that no message queried is a prefix of any other, as is the case when all messages to be MACed have the same length. We go on to give an improved analysis of the encrypted CBC MAC, where there is no restriction on queried messages. Letting m be the block length of the longest query, our bounds are about mq2/2n for the basic CBC MAC and mo(1)q2/2n for the encrypted CBC MAC, improving prior bounds of m2q2/2n. The new bounds translate into improved guarantees on the probability of forging these MACs. AU - Bellare, Mihir AU - Krzysztof Pietrzak AU - Rogaway, Phillip ID - 3211 TI - Improved security analyses for CBC MACs VL - 3621 ER - TY - JOUR AB - We discuss the formation of graded morphogen profiles in a cell layer by nonlinear transport phenomena, important for patterning developing organisms. We focus on a process termed transcytosis, where morphogen transport results from the binding of ligands to receptors on the cell surface, incorporation into the cell, and subsequent externalization. Starting from a microscopic model, we derive effective transport equations. We show that, in contrast to morphogen transport by extracellular diffusion, transcytosis leads to robust ligand profiles which are insensitive to the rate of ligand production. AU - Bollenbach, Mark Tobias AU - Kruse, Karsten AU - Pantazis, Periklis AU - González Gaitán, Marcos AU - Jülicher, Frank ID - 3426 IS - 1 JF - Physical Review Letters TI - Robust formation of morphogen gradients VL - 94 ER - TY - JOUR AB - In the hippocampal CA1 area, a relatively homogenous population of pyramidal cells is accompanied by a diversity of GABAergic interneurons. Previously, we found that parvalbumin-expressing basket, axo-axonic, bistratified, and oriens-lacunosum moleculare cells, innervating different domains of pyramidal cells, have distinct firing patterns during network oscillations in vivo. A second family of interneurons, expressing cholecystokinin but not parvalbumin, is known to target the same domains of pyramidal cells as do the parvalbumin cells. To test the temporal activity of these independent and parallel GABAergic inputs, we recorded the precise spike timing of identified cholecystokinin interneurons during hippocampal network oscillations in anesthetized rats and determined their molecular expression profiles and synaptic targets. The cells were cannabinoid receptor type 1 immunopositive. Contrary to the stereotyped firing of parvalbumin interneurons, cholecystokinin-expressing basket and dendrite-innervating cells discharge, on average, with 1.7 ± 2.0 Hz during high-frequency ripple oscillations in an episode-dependent manner. During theta oscillations, cholecystokinin- expressing interneurons fire with 8.8 ± 3.3 Hz at a characteristic time on the ascending phase of theta waves (155 ± 81°), when place cells start firing in freely moving animals. The firing patterns of some interneurons recorded in drug-free behaving rats were similar to cholecystokinin cells in anesthetized animals. Our results demonstrate that cholecystokinin- and parvalbumin-expressing interneurons make different contributions to network oscillations and play distinct roles in different brain states. We suggest that the specific spike timing of cholecystokinin interneurons and their sensitivity to endocannabinoids might contribute to differentiate subgroups of pyramidal cells forming neuronal assemblies, whereas parvalbumin interneurons contribute to synchronizing the entire network. Copyright © 2005 Society for Neuroscience. AU - Klausberger,Thomas AU - Marton,Laszlo F AU - Joseph O'Neill AU - Huck, Jojanneke H AU - Dalezios, Yannis AU - Fuentealba,Pablo AU - Suen, Wai Yee AU - Papp, Edit Cs AU - Kaneko, Takeshi AU - Watanabe, Masahiko AU - Jozsef Csicsvari AU - Somogyi, Péter ID - 3443 IS - 42 JF - Journal of Neuroscience TI - Complementary roles of cholecystokinin- and parvalbumin-expressing GABAergic neurons in hippocampal network oscillations VL - 25 ER - TY - CONF AB - A challenging problem in computer-aided geometric design is the decomposition of a surface into four-sided regions that are then represented by NURBS patches. There are various approaches published in the literature and implemented as commercially available software, but all fall short in either automation or quality of the result. At Raindrop Geomagic, we have recently taken a fresh approach based on concepts from Morse theory. This by itself is not a new idea, but we have some novel ingredients that make this work, one being a rational notion of hierarchy that guides the construction of a simplified decomposition sensitive to only the major critical points. AU - Herbert Edelsbrunner ID - 3557 TI - Surface tiling with differential topology ER - TY - CHAP AB - During zebrafish gastrulation, the interplay between patterning events and morphogenesis creates an embryo out of a seemingly unstructured blastula stage embryo, an embryo with distinct polarities along its anterior–posterior, dorsoventral and left–right axes at the end of gastrulation. AU - Köppen, Mathias AU - Heisenberg, Carl-Philipp J ID - 3589 T2 - Encyclopedia of Life Sciences TI - Cleavage and gastrulation in zebrafish embryos ER - TY - CHAP AU - Castanon Ortega, Irinka AU - Heisenberg, Carl-Philipp J ED - Wedlich, Doris ID - 3588 T2 - Cell Migration in Development and Disease TI - Cell migration during zebrafish gastrulation ER - TY - GEN AU - Castanon Ortega, Irinka AU - Heisenberg, Carl-Philipp J ID - 3590 IS - 1 T2 - Nature Cell Biology TI - A stern view of gastrulation VL - 7 ER - TY - CONF AB - Digital cameras have become almost ubiquitous and their use for fast and casual capturing of natural images is unchallenged. For making images of documents, however, they have not caught up to flatbed scanners yet, mainly because camera images tend to suffer from distortion due to the perspective and are therefore limited in their further use for archival or OCR. For images of non-planar paper surfaces like books, page curl causes additional distortion, which poses an even greater problem due to its nonlinearity. This paper presents a new algorithm for removing both perspective and page curl distortion. It requires only a single camera image as input and relies on a priori layout information instead of additional hardware. Therefore, it is much more user friendly than most previous approaches, and allows for flexible ad hoc document capture. Results are presented showing that the algorithm produces visually pleasing output and increases OCR accuracy, thus having the potential to become a general purpose preprocessing tool for camera based document capture. AU - Ulges, Adrian AU - Christoph Lampert AU - Breuel,Thomas M ID - 3689 TI - Document image dewarping using robust estimation of curled text lines VL - 2 ER - TY - CONF AB - Ever since text processors became popular, users have dreamt of handling documents printed on paper as comfortably as electronic ones, with full text search typically appearing very close to the top of the wish list. This paper presents the design of a prototype system that takes a step into this direction. The user’s desktop is continuously monitored and of each detected document a high resolution snapshot is taken using a digital camera. The resulting image is processed using specially designed dewarping and OCR algorithms, making a digital and fully searchable version of the document available to the user in real-time. These steps are performed without any user interaction. This enables the system to run as a background task without disturbing the user in her work, while at the same time offering electronic access to all paper documents that have been present on the desktop during the uptime of the system. AU - Christoph Lampert AU - Braun,Tim AU - Ulges, Adrian AU - Keysers,Daniel AU - Breuel,Thomas M ID - 3684 TI - Oblivious document capture and real-time retrieval ER - TY - JOUR AU - Guzmán, José AU - Gerevich, Zoltan AU - Hengstler, Jan AU - Illes, Peter AU - Kleemann, Werner ID - 3720 IS - 4 JF - Synapse TI - P2Y1 receptors inhibit both strength and plasticity of glutamatergic synaptic neurotransmission in the rat prefrontal cortex. VL - 57 ER - TY - JOUR AB - Characterizing the dynamics of specific RNA levels requires real-time RNA profiling in a single cell. We show that the combination of a synthetic modular genetic system with fluorescence correlation spectroscopy allows us to directly measure in real time the activity of any specific promoter in prokaryotes. Using a simple inducible gene expression system, we found that induced RNA levels within a single bacterium of Escherichia coli exhibited a pulsating profile in response to a steady input of inducer. The genetic deletion of an efflux pump system, a key determinant of antibiotic resistance, altered the pulsating transcriptional dynamics and caused overexpression of induced RNA. In contrast with population measurements, real-time RNA profiling permits identifying relationships between genotypes and transcriptional dynamics that are accessible only at the level of the single cell. AU - Le,Thuc T. AU - Harlepp, Sébastien AU - Calin Guet AU - Dittmar,Kimberly AU - Emonet,Thierry AU - Pan,Tao AU - Cluzel,Philippe ID - 3753 IS - 26 JF - PNAS TI - Real-time RNA profiling within a single bacterium VL - 102 ER - TY - JOUR AB - The generation of realistic motion satisfying user-defined requirements is one of the most important goals of computer animation. Our aim in this paper is the synthesis of realistic, controllable motion for lightweight natural objects in a gaseous medium. We formulate this problem as a large-scale spacetime optimization with user controls and fluid motion equations as constraints. We have devised novel and effective methods to make this large optimization tractable. Initial trajectories are generated with data-driven synthesis based on stylistic motion planning. Smoothed particle hydrodynamics (SPH) is used during optimization to produce fluid simulations at a reasonable computational cost, while interesting vortex-based fluid motion is generated by recording the presence of vortices in the initial trajectories and maintaining them through optimization. Object rotations are refined as a postprocess to enhance the visual quality of the results. We demonstrate our techniques on a number of animations involving single or multiple objects. AU - Shi, Lin AU - Yu, Yizhou AU - Wojtan, Christopher J AU - Chenney, Stephen ID - 3763 IS - 7 JF - The Visual Computer TI - Controllable motion synthesis in a gaseous medium VL - 21 ER - TY - GEN AB - Hippocampal GABAergic interneurons show diverse molecular and morphological properties. The functional significance of this diversity for information processing is poorly understood. Here we show that cholecystokinin (CCK)-expressing interneurons in rat dentate gyrus release GABA in a highly asynchronous manner, in contrast to parvalbumin (PV) interneurons. With a gamma-frequency burst of ten action potentials, the ratio of asynchronous to synchronous release is 3:1 in CCK interneurons but is 1:5 in parvalbumin interneurons. N-type channels trigger synchronous and asynchronous release in CCK interneuron synapses, whereas P/Q-type Ca(2+) channels mediate release at PV interneuron synapses. Effects of Ca(2+) chelators suggest that both a long-lasting presynaptic Ca(2+) transient and a large distance between Ca(2+) source and sensor of exocytosis contribute to the higher ratio of asynchronous to synchronous release in CCK interneuron synapses. Asynchronous release occurs at physiological temperature and with behaviorally relevant stimulation patterns, thus generating long-lasting inhibition in the brain. AU - Hefft, Stefan AU - Peter Jonas ID - 3812 IS - 10 T2 - Nature Neuroscience TI - Asynchronous GABA release generates long-lasting inhibition at a hippocampal interneuron-principal neuron synapse (Review) VL - 8 ER - TY - CONF AB - Temporal Logic Model Checking is one of the most potent tools for the verification of finite state systems. Computation Tree Logic (CTL) has gained popularity because unlike most other logics, CTL model checking of a single transition system can be achieved in polynomial time. However, in most real-life problems, specially in distributed and parallel systems, the system consist of a set of concurrent processes and the verification problem translates to model check the composition of the component processes. Since explicit composition leads to state explosion, verifying the system without actually composing the components is attractive, even for possibly restrictive class of systems. We show that the problem of compositional CTL model checking is PSPACE complete for the class of systems composed of components that are tree-like transition structure and do not interact among themselves. For the simplest forms of existential and universal CTL formulas model checking turns out to be NP complete and coNP complete, respectively. The results hold for both synchronous and asynchronous composition. AU - Krishnendu Chatterjee AU - Dasgupta, Pallab AU - Chakrabarti, Partha P ID - 3896 TI - Complexity of compositional model checking of computation tree logic on simple structures VL - 3326 ER - TY - CONF AB - We study infinite stochastic games played by two-players on a finite graph with goals specified by sets of infinite traces. The games are concurrent (each player simultaneously and independently chooses an action at each round), stochastic (the next state is determined by a probability distribution depending on the current state and the chosen actions), infinite (the game continues for an infinite number of rounds), nonzero-sum (the players' goals are not necessarily conflicting), and undiscounted. We show that if each player has an W-regular objective expressed as a paxity objective, then there exists an epsilon-Nash equilibrium, for every epsilon > 0. However, exact Nash equilibria need not exist. We study the complexity of finding values (payoff profile) of an epsilon-Nash equilibrium. We show that the values of an epsilon-Nash equilibrium in nonzero-sum concurrent parity games can be computed by solving the following two simpler problems: computing the values of zero-sum (the goals of the players axe strictly conflicting) concurrent parity games and computing epsilon-Nash equilibrium values of nonzero-sum concurrent games with reachability objectives. As a consequence we establish that values of an epsilon-Nash equilibrium can be computed in TFNP (total functional NP), and hence in EXPTIME. AU - Krishnendu Chatterjee ID - 3893 TI - Two-player nonzero-sum ω-regular games VL - 3653 ER - TY - JOUR AB - Divergent reproductive interests of males and females often cause sexual conflict [1] and [2]. Males of many species manipulate females by transferring seminal fluids that boost female short-term fecundity while decreasing their life expectancy and future reproductivity [3] and [4]. The life history of ants, however, is expected to reduce sexual conflict; whereas most insect females show repeated phases of mating and reproduction, antqueens mate only during a short period early in life and undergo a lifelong commitment to their mates by storing sperm [5]. Furthermore, sexual offspring can only be reared after a sterile worker force has been built up [5]. Therefore, the males should also profit from a long female lifespan. In the antCardiocondyla obscurior, mating indeed has a positive effect on the lifetime reproductive success of queens. Queens that mated to either one fertile or one sterilized male lived considerably longer and started laying eggs earlier than virgin queens. Only queens that received viable sperm from fertile males showed increased fecundity. The lack of a trade-off between fecundity and longevity is unexpected, given evolutionary theories of aging [6]. Our data instead reveal the existence of sexual cooperation in ants. AU - Schrempf, Alexandra AU - Heinze, Jürgen AU - Cremer, Sylvia ID - 3916 IS - 3 JF - Current Biology TI - Sexual cooperation: mating increases longevity in ant queens VL - 15 ER - TY - JOUR AB - In the ant Cardiocondyla obscurior, wingless males compete with nestmate males for access to female mating partners, leading to local mate competition (LMC). Queen number varies between colonies, resulting in variation in the strength of LMC. Cremer & Heinze (2002, Proceedings of the Royal Society of London, Series B, 269, 417–422) showed that colonies responded to increasing queen number by producing a less femalebiased sex ratio, as predicted by LMC theory. However, the proximate mechanisms responsible for this variation in the sex ratio could not be determined because the study was restricted to adult sex ratios.With LMC, the primary sex ratio (proportion of haploid eggs laid by the queen) is expected to be female biased, which lowers the conflict between queens and workers over sex allocation. We compared the primary sex ratios laid by queens in monogynous and in polygynous experimental colonies of C. obscurior. The proportion of haploid eggs laid by queens was significantly lower in single-queen than in multiple-queen colonies. Furthermore, queens rapidly adjusted their primary sex ratios to changes in colony queen number. This is the first report of an adaptive adjustment of the primary sex ratio in response to LMC by ant queens. AU - De Menten, Ludivine AU - Cremer, Sylvia AU - Heinze, Jürgen AU - Aron, Serge ID - 3915 IS - 5 JF - Animal Behaviour TI - Primary sex ratio adjustment by ant queens in response to local mate competition VL - 69 ER - TY - JOUR AB - In this study, we elucidate the roles of the winged-helix transcription factor Foxa2 in ventral CNS development in zebrafish. Through cloning of monorail (mol), which we find encodes the transcription factor Foxa2, and phenotypic analysis of mol(-/-) embryos, we show that floorplate is induced in the absence of Foxa2 function but fails to further differentiate. In mol(-/-) mutants, expression of Foxa and Hh family genes is not maintained in floorplate cells and lateral expansion of the floorplate fails to occur. Our results suggest that this is due to defects both in the regulation of Hh activity in medial floorplate cells as well as cell-autonomous requirements for Foxa2 in the prospective laterally positioned floorplate cells themselves. Foxa2 is also required for induction and/or patterning of several distinct cell types in the ventral CNS. Serotonergic neurones of the raphe nucleus and the trochlear motor nucleus are absent in mol(-/-) embryos, and oculomotor and facial motoneurones ectopically occupy ventral CNS midline positions in the midbrain and hindbrain. There is also a severe reduction of prospective oligodendrocytes in the midbrain and hindbrain. Finally, in the absence of Foxa2, at least two likely Hh pathway target genes are ectopically expressed in more dorsal regions of the midbrain and hindbrain ventricular neuroepithelium, raising the possibility that Foxa2 activity may normally be required to limit the range of action of secreted Hh proteins. AU - Norton, Will AU - Mangoli, Maryam AU - Lele, Zsolt AU - Pogoda, Hans AU - Diamond, Brianne AU - Mercurio, Sara AU - Russell, Claire AU - Teraoka, Hiroki AU - Stickney, Heather AU - Rauch, Gerd AU - Heisenberg, Carl-Philipp J AU - Houart, Corinne AU - Schilling, Thomas AU - Frohnhoefer, Hans AU - Rastegar, Sepand AU - Neumann, Carl AU - Gardiner, R Mark AU - Strähle, Uwe AU - Geisler, Robert AU - Rees, Michelle AU - Talbot, William AU - Wilson, Stephen ID - 4167 IS - 4 JF - Development TI - Monorail/Foxa2 regulates floorplate differentiation and specification of oligodendrocytes, serotonergic raphe neurones and cranial motoneurones VL - 132 ER - TY - JOUR AB - The spreading of an epithelial cell sheet over a substrate is a common process during embryogenesis. Typical examples include epiboly during zebrafish gastrulation and Drosophila dorsal closure. We provide evidence that in both cases, actin-based contraction of the leading edge of the epithelium is of critical importance. AU - Köppen, Mathias AU - Fernández, Beatriz AU - Carvalho, Lara AU - Jacinto, António AU - Heisenberg, Carl-Philipp J ID - 4183 IS - Supplement 1 JF - Mechanisms of Development TI - Misshapen mediates actin-based cell contraction during zebrafish epiboly and Drosophila dorsal closure VL - 122 ER - TY - CONF AU - Podelski,Andreas AU - Thomas Wies ID - 4367 TI - Boolean Heaps ER - TY - JOUR AB - Two ETS transcription factors of the Pea3 subfamily are induced in subpopulations of dorsal root ganglion (DRG) sensory and spinal motor neurons by target-derived factors. Their expression controls late aspects of neuronal differentiation such as target invasion and branching. Here, we show that the late onset of ETS gene expression is an essential requirement for normal sensory neuron differentiation. We provide genetic evidence in the mouse that precocious ETS expression in DRG sensory neurons perturbs axonal projections, the acquisition of terminal differentiation markers, and their dependence on neurotrophic support. Together, our findings indicate that DRG sensory neurons exhibit a temporal developmental switch that can be revealed by distinct responses to ETS transcription factor signaling at sequential steps of neuronal maturation. AU - Simon Hippenmeyer AU - Vrieseling, Eline AU - Sigrist, Markus AU - Portmann, Thomas AU - Laengle, Celia AU - Ladle, David R AU - Arber, Silvia ID - 3143 IS - 5 JF - PLoS Biology TI - A developmental switch in the response of DRG neurons to ETS transcription factor signaling VL - 3 ER - TY - JOUR AB - The two actin-related subunits of the Arp2/3 complex, Arp2 and Arp3, are proposed to form a pseudo actin dimer that nucleates actin polymerization. However, in the crystal structure of the inactive complex, they are too far apart to form such a nucleus. Here, we show using EM that yeast and bovine Arp2/3 complexes exist in a distribution among open, intermediate and closed conformations. The crystal structure docks well into the open conformation. The activator WASp binds at the cleft between Arp2 and Arp3, and all WASp-bound complexes are closed. The inhibitor coronin binds near the p35 subunit, and all coronin-bound complexes are open. Activating and loss-of-function mutations in the p35 subunit skew conformational distribution in opposite directions, closed and open, respectively. We conclude that WASp stabilizes p35-dependent closure of the complex, holding Arp2 and Arp3 closer together to nucleate an actin filament. AU - Rodal, Avital A AU - Sokolova, Olga AU - Robins, Deborah B AU - Daugherty, Karen M AU - Simon Hippenmeyer AU - Riezman, Howard AU - Grigorieff, Nikolaus AU - Goode, Bruce L ID - 3141 IS - 1 JF - Nature Structural and Molecular Biology TI - Conformational changes in the Arp2 3 complex leading to actin nucleation VL - 12 ER - TY - CONF AB - This paper addresses the novel problem of automatically synthesizing an output image from a large collection of different input images. The synthesized image, called a digital tapestry, can be viewed as a visual summary or a virtual 'thumbnail' of all the images in the input collection. The problem of creating the tapestry is cast as a multi-class labeling problem such that each region in the tapestry is constructed from input image blocks that are salient and such that neighboring blocks satisfy spatial compatibility. This is formulated using a Markov Random Field and optimized via the graph cut based expansion move algorithm. The standard expansion move algorithm can only handle energies with metric terms, while our energy contains non-metric (soft and hard) constraints. Therefore we propose two novel contributions. First, we extend the expansion move algorithm for energy functions with non-metric hard constraints. Secondly, we modify it for functions with "almost" metric soft terms, and show that it gives good results in practice. The proposed framework was tested on several consumer photograph collections, and the results are presented. AU - Rother, Carsten AU - Kumar, Sanjiv AU - Vladimir Kolmogorov AU - Blake, Andrew ID - 3175 TI - Digital tapestry VL - 1 ER - TY - CONF AB - This paper demonstrates the high quality, real-time segmentation techniques. We achieve real-time segmentation of foreground from background layers in stereo video sequences. Automatic separation of layers from colour/contrast or from stereo alone is known to be error-prone. Here, colour, contrast and stereo matching information are fused to infer layers accurately and efficiently. The first algorithm, layered dynamic programming (LDP), solves stereo in an extended 6-state space that represents both foreground/background layers and occluded regions. The stereo-match likelihood is then fused with a contrast-sensitive colour model that is learned on the fly, and stereo disparities are obtained by dynamic programming. The second algorithm, layered graph cut (LGC), does not directly solve stereo. Instead the stereo match likelihood is marginalised over foreground and background hypotheses, and fused with a contrast-sensitive colour model like the one used in LDP. Segmentation is solved efficiently by ternary graph cut. Both algorithms are evaluated with respect to ground truth data and found to have similar performance, substantially better than stereo or colour/contrast alone. However, their characteristics with respect to computational efficiency are rather different. The algorithms are demonstrated in the application of background substitution and shown to give good quality composite video output. AU - Vladimir Kolmogorov AU - Criminisi, Antonio AU - Blake, Andrew AU - Cross, Geoffrey AU - Rother, Carsten ID - 3176 TI - Bi-layer segmentation of binocular stereo video ER - TY - CONF AB - This paper describes two algorithms capable of real-time segmentation of foreground from background layers in stereo video sequences. Automatic separation of layers from colour/contrast or from stereo alone is known to be error-prone. Here, colour, contrast and stereo matching information are fused to infer layers accurately and efficiently. The first algorithm, Layered Dynamic Programming (LDP), solves stereo in an extended 6-state space that represents both foreground/background layers and occluded regions. The stereo-match likelihood is then fused with a contrast-sensitive colour model that is learned on the fly, and stereo disparities are obtained by dynamic programming. The second algorithm, Layered Graph Cut (LGC), does not directly solve stereo. Instead the stereo match likelihood is marginalised over foreground and background hypotheses, and fused with a contrast-sensitive colour model like the one used in LDP. Segmentation is solved efficiently by ternary graph cut. Both algorithms are evaluated with respect to ground truth data and found to have similar perfomance, substantially better than stereo or colour/contrast alone. However, their characteristics with respect to computational efficiency are rather different. The algorithms are demonstrated in the application of background substitution and shown to give good quality composite video output. AU - Vladimir Kolmogorov AU - Criminisi, Antonio AU - Blake, Andrew AU - Cross, Geoffrey AU - Rother, Carsten ID - 3183 TI - Bi-layer segmentation of binocular stereo video VL - 2 ER - TY - CONF AB - In the work of the authors (2003), we showed that graph cuts can find hypersurfaces of globally minimal length (or area) under any Riemannian metric. Here we show that graph cuts on directed regular grids can approximate a significantly more general class of continuous non-symmetric metrics. Using submodularity condition (Boros and Hammer, 2002 and Kolmogorov and Zabih, 2004), we obtain a tight characterization of graph-representable metrics. Such "submodular" metrics have an elegant geometric interpretation via hypersurface functionals combining length/area and flux. Practically speaking, we attend 'geo-cuts' algorithm to a wider class of geometrically motivated hypersurface functionals and show how to globally optimize any combination of length/area and flux of a given vector field. The concept of flux was recently introduced into computer vision by Vasilevskiy and Siddiqi (2002) but it was mainly studied within variational framework so far. We are first to show that flux can be integrated into graph cuts as well. Combining geometric concepts of flux and length/area within the global optimization framework of graph cuts allows principled discrete segmentation models and advances the slate of the art for the graph cuts methods in vision. In particular we address the "shrinking" problem of graph cuts, improve segmentation of long thin objects, and introduce useful shape constraints. AU - Vladimir Kolmogorov AU - Boykov, Yuri ID - 3182 TI - What metrics can be approximated by geo cuts or global optimization of length area and flux VL - 1 ER - TY - CONF AB - Tree-reweighted max-product (TRW) message passing [9] is a modified form of the ordinary max-product algorithm for attempting to find minimal energy configurations in Markov random field with cycles. For a TRW fixed point satisfying the strong tree agreement condition, the algorithm outputs a configuration that is provably optimal. In this paper, we focus on the case of binary variables with pairwise couplings, and establish stronger properties of TRW fixed points that satisfy only the milder condition of weak tree agreement (WTA). First, we demonstrate how it is possible to identify part of the optimal solution - i.e., a provably optimal solution for a subset of nodes - without knowing a complete solution. Second, we show that for submodular functions, a WTA fixed point always yields a globally optimal solution. We establish that for binary variables, any WTA fixed point always achieves the global maximum of the linear programming relaxation underlying the TRW method. AU - Vladimir Kolmogorov AU - Wainwright, Martin J ID - 3181 TI - On the optimality of tree reweighted max product message passing ER - TY - JOUR AB - Recently, direct measurements of forces stabilizing single proteins or individual receptor–ligand bonds became possible with ultra-sensitive force probe methods like the atomic force microscope (AFM). In force spectroscopy experiments using AFM, a single molecule or receptor–ligand pair is tethered between the tip of a micromachined cantilever and a supporting surface. While the molecule is stretched, forces are measured by the deflection of the cantilever and plotted against extension, yielding a force spectrum characteristic for each biomolecular system. In order to obtain statistically relevant results, several hundred to thousand single-molecule experiments have to be performed, each resulting in a unique force spectrum. We developed software and algorithms to analyse large numbers of force spectra. Our algorithms include the fitting polymer extension models to force peaks as well as the automatic alignment of spectra. The aligned spectra allowed recognition of patterns of peaks across different spectra. We demonstrate the capabilities of our software by analysing force spectra that were recorded by unfolding single transmembrane proteins such as bacteriorhodopsin and NhaA. Different unfolding pathways were detected by classifying peak patterns. Deviant spectra, e.g. those with no attachment or erratic peaks, can be easily identified. The software is based on the programming language C++, the GNU Scientific Library (GSL), the software WaveMetrics IGOR Pro and available open-source at http://bioinformatics.org/fskit/. AU - Kuhn, Michael AU - Harald Janovjak AU - Hubain, Maurice AU - Mueller, Daniel J ID - 3417 IS - 2 JF - Journal of Microscopy TI - Automated alignment and pattern recognition of single-molecule force spectroscopy data VL - 218 ER - TY - JOUR AB - In the last decade atomic force microscopy has been used to measure the mechanical stability of single proteins. These force spectroscopy experiments have shown that many water-soluble and membrane proteins unfold via one or more intermediates. Recently, Li and co-workers found a linear correlation between the unfolding force of the native state and the intermediate in fibronectin, which they suggested indicated the presence of a molecular memory or multiple unfolding pathways (1). Here, we apply two independent methods in combination with Monte Carlo simulations to analyze the unfolding of α-helices E and D of bacteriorhodopsin (BR). We show that correlation analysis of unfolding forces is very sensitive to errors in force calibration of the instrument. In contrast, a comparison of relative forces provides a robust measure for the stability of unfolding intermediates. The proposed approach detects three energetically different states of α-helices E and D in trimeric BR. These states are not observed for monomeric BR and indicate that substantial information is hidden in forced unfolding experiments of single proteins. AU - Harald Janovjak AU - Sapra, Tanuj K AU - Mueller, Daniel J ID - 3416 IS - 5 JF - Biophysical Journal TI - Complex stability of single proteins explored by forced unfolding experiments VL - 88 ER - TY - JOUR AB - Atomic force microscopy (AFM) allows the critical forces that unfold single proteins and rupture individual receptor–ligand bonds to be measured. To derive the shape of the energy landscape, the dynamic strength of the system is probed at different force loading rates. This is usually achieved by varying the pulling speed between a few nm/s and a few mgrm/s, although for a more complete investigation of the kinetic properties higher speeds are desirable. Above 10 mgrm/s, the hydrodynamic drag force acting on the AFM cantilever reaches the same order of magnitude as the molecular forces. This has limited the maximum pulling speed in AFM single-molecule force spectroscopy experiments. Here, we present an approach for considering these hydrodynamic effects, thereby allowing a correct evaluation of AFM force measurements recorded over an extended range of pulling speeds (and thus loading rates). To support and illustrate our theoretical considerations, we experimentally evaluated the mechanical unfolding of a multi-domain protein recorded at 30 mgrm/s pulling speed. AU - Harald Janovjak AU - Struckmeier, Jens AU - Mueller, Daniel J ID - 3418 IS - 1 JF - European Biophysics Journal TI - Hydrodynamic effects in fast AFM single molecule force measurements VL - 34 ER - TY - CHAP AU - Jonathan Bollback ED - Nielsen, Rasmus ID - 3433 T2 - Statistical methods in Molecular Evolution TI - Posterior mapping and posterior predictive distributions ER - TY - GEN AB - Methods, apparatus and computer program products can generate light weight but highly realistic and accurate colored models of three-dimensional colored objects. The colored model may be generated from a second plurality of points that define a coarse digital representation of the surface and at least one texture map containing information derived from a first plurality of colored points that define a fine digital representation of the surface. This derivation is achieved by mapping points within the texture map to the fine digital representation of the three-dimensional surface. Colored scan data may be used to construct the fine digital representation as a triangulated surface (i.e., triangulation) using a wrapping operation. AU - Williams, Steven AU - Edelsbrunner, Herbert AU - Fu, Ping ID - 3509 TI - Methods, apparatus and computer program products for modeling three-dimensional colored objects ER - TY - CONF AB - The tandem algorithm combines the marching cube algorithm for surface extraction and the edge contraction algorithm for surface simplification in lock-step to avoid the costly intermediate step of storing the entire extracted surface triangulation. Beyond this basic strategy, we introduce refinements to prevent artifacts in the resulting triangulation, first, by carefully monitoring the amount of simplification during the process and, second, by driving the simplification toward a compromise between shape approximation and mesh quality. We have implemented the algorithm and used extensive computational experiments to document the effects of various design options and to further fine-tune the algorithm. AU - Attali, Dominique AU - Cohen-Steiner, David AU - Herbert Edelsbrunner ID - 3558 TI - Extraction and simplification of iso-surfaces in tandem ER - TY - CHAP AB - ears of research in biology have established that all cellular functions are deeply connected to the shape and dynamics of their molec- ular actors. As a response, structural molecular biology has emerged as a new line of experimental research focused on revealing the structure of biomolecules. The analysis of these structures has led to the development of computational biology, whose aim is to predict from molecular simulation properties inaccessible to experimental probes. Here we focus on the representation of biomolecules used in these sim- ulations, and in particular on the hard sphere models. We review how the geometry of the union of such spheres is used to model their interactions with their environment, and how it has been included in simulations of molecular dynamics. In parallel, we review our own developments in mathematics and com- puter science on understanding the geometry of unions of balls, and their applications in molecular simulation. AU - Herbert Edelsbrunner AU - Koehl, Patrice ID - 3576 T2 - Combinatorial and Computational Geometry TI - The geometry of biomolecular solvation VL - 52 ER - TY - JOUR AB - Left-right asymmetry in snails is intriguing because individuals of opposite chirality are either unable to mate or can only mate with difficulty, so could be reproductively isolated from each other. We have therefore investigated chiral evolution in the Japanese land snail genus Euhadra to understand whether changes in chirality have promoted speciation. In particular, we aimed to understand the effect of the maternal inheritance of chirality on reproductive isolation and gene flow. We found that the mitochondrial DNA phylogeny of Euhadra is consistent with a single, relatively ancient evolution of sinistral species and suggests either recent “single-gene speciation” or gene flow between chiral morphs that are unable to mate. To clarify the conditions under which new chiral morphs might evolve and whether single-gene speciation can occur, we developed a mathematical model that is relevant to any maternal-effect gene. The model shows that reproductive character displacement can promote the evolution of new chiral morphs, tending to counteract the positive frequency-dependent selection that would otherwise drive the more common chiral morph to fixation. This therefore suggests a general mechanism as to how chiral variation arises in snails. In populations that contain both chiral morphs, two different situations are then possible. In the first, gene flow is substantial between morphs even without interchiral mating, because of the maternal inheritance of chirality. In the second, reproductive isolation is possible but unstable, and will also lead to gene flow if intrachiral matings occasionally produce offspring with the opposite chirality. Together, the results imply that speciation by chiral reversal is only meaningful in the context of a complex biogeographical process, and so must usually involve other factors. In order to understand the roles of reproductive character displacement and gene flow in the chiral evolution of Euhadra, it will be necessary to investigate populations in which both chiral morphs coexist. AU - Davison, Angus AU - Chiba, Satoshi AU - Nicholas Barton AU - Clarke, Bernard ID - 3612 IS - 9 JF - PLoS Biology TI - Speciation and gene flow between snails of opposing chirality VL - 3 ER - TY - JOUR AB - We present two novel methods to infer mating patterns from genetic data. They differ from existing statistical methods of parentage inference in that they apply to populations that deviate from Hardy–Weinberg and linkage equilibrium, and so are suited for the study of assortative mating in hybrid zones. The core data set consists of genotypes at several loci for a number of full-sib clutches of unknown parentage. Our inference is based throughout on estimates of allelic associations within and across loci, such as heterozygote deficit and pairwise linkage disequilibrium. In the first method, the most likely parents of a given clutch are determined from the genotypic distribution of the associated adult population, given an explicit model of nonrandom mating. This leads to estimates of the strength of assortment. The second approach is based solely on the offspring genotypes and relies on the fact that a linear relation exists between associations among the offspring and those in the population of breeding pairs. We apply both methods to a sample from the hybrid zone between the fire-bellied toads Bombina bombina and B. variegata (Anura: Disco glossidae) in Croatia. Consistently, both approaches provide no evidence for a departure from random mating, despite adequate statistical power. Instead, B. variegata-like individuals among the adults contributed disproportionately to the offspring cohort, consistent with their preference for the type of breeding habitat in which this study was conducted. AU - Nürnberger, Beate AU - Nicholas Barton AU - Kruuk, Loeske E AU - Vines, Timothy H ID - 3611 IS - 2 JF - Heredity TI - Mating patterns in a Bombina hybrid zone: Inferences from adult and full sib genotypes VL - 94 ER - TY - JOUR AB - The extent of genetic variation in fitness is a crucial issue in evolutionary biology and yet remains largely unresolved. In Drosophila melanogaster, we have devised a method that allows the net effects on fitness of heterozygous wild-type chromosomes to be measured, by competing them against two different “balancer” chromosomes. We have applied the method to a large sample of 40 wild-type third chromosomes and have measured fitnesses of nonlethal chromosomes as well as chromosomes bearing recessive lethals. The measurements were made in the environment to which the population was adapted and did not involve inbreeding. The results show an extraordinary similarity in the behavior of replicates of the same chromosome, indicating consistent genetic effects on total fitness. Some invading chromosomes increased rapidly and some slowly, and some rose to appreciable frequency after several months, but then declined again: in every case, the same pattern was seen in each replicate. We estimated relative fitnesses, rates of change of fitness, and relative viabilities, for each chromosome. There were significant fluctuations around the fitted model, which were also highly replicable. Wild-type chromosomes varied substantially in their effects on heterozygous fitness, and these effects vary through time, most likely as a result of genotype × environment interactions. AU - Gardner, Michael P AU - Fowler, Kevin AU - Nicholas Barton AU - Patridge, Linda ID - 3613 IS - 3 JF - Genetics TI - Genetic variation for total fitness in Drosophila melanogaster: Complex yet replicable patterns VL - 169 ER - TY - JOUR AB - In strictly pseudoconvex domains with smooth boundary, we prove a commutator relationship between admissible integral operators, as introduced by Lieb and Range, and smooth vector fields which are tangential at boundary points. This makes it possible to gain estimates for admissible operators in function spaces which involve tangential derivatives. Examples are given under with circumstances these can be transformed into genuine Sobolev- and C k-estimates. AU - Christoph Lampert ID - 3691 IS - 1 JF - Publicacions Matemàtiques TI - Boundary regularity of admissible operators VL - 49 ER - TY - JOUR AB - Recent advances in atomic force microscopy allowed globular and membrane proteins to be mechanically unfolded on a single-molecule level. Presented is an extension to the existing force spectroscopy experiments. While unfolding single bacteriorhodopsins from native purple membranes, small oscillation amplitudes (6–9nm) were supplied to the vertical displacement of the cantilever at a frequency of 3kHz. The phase and amplitude response of the cantilever-protein system was converted to reveal the elastic (conservative) and viscous (dissipative) contributions to the unfolding process. The elastic response (stiffness) of the extended parts of the protein were in the range of a few tens pN/nm and could be well described by the derivative of the wormlike chain model. Discrete events in the viscous response coincided with the unfolding of single secondary structure elements and were in the range of 1μNs/m. In addition, these force modulation spectroscopy experiments revealed novel mechanical unfolding intermediates of bacteriorhodopsin. We found that kinks result in a loss of unfolding cooperativity in transmembrane helices. Reconstructing force-distance spectra by the integration of amplitude-distance spectra verified their position, offering a novel approach to detect intermediates during the forced unfolding of single proteins. AU - Harald Janovjak AU - Mueller, Daniel J AU - Humphris, Andrew D ID - 3721 IS - 2 JF - Biophysical Journal TI - Molecular force modulation spectroscopy revealing the dynamic response of single bacteriorhodopsins VL - 88 ER - TY - JOUR AB - In an age of increasingly large data sets, investigators in many different disciplines have turned to clustering as a tool for data analysis and exploration. Existing clustering methods, however, typically depend on several nontrivial assumptions about the structure of data. Here, we reformulate the clustering problem from an information theoretic perspective that avoids many of these assumptions. In particular, our formulation obviates the need for defining a cluster "prototype," does not require an a priori similarity metric, is invariant to changes in the representation of the data, and naturally captures nonlinear relations. We apply this approach to different domains and find that it consistently produces clusters that are more coherent than those extracted by existing algorithms. Finally, our approach provides a way of clustering based on collective notions of similarity rather than the traditional pairwise measures. AU - Slonim,N. AU - Atwal,G. AU - Gasper Tkacik AU - Bialek, William S ID - 3741 IS - 51 JF - PNAS TI - Information-based clustering VL - 102 ER - TY - GEN AB - We address the practical problems of estimating the information relations that characterize large networks. Building on methods developed for analysis of the neural code, we show that reliable estimates of mutual information can be obtained with manageable computational effort. The same methods allow estimation of higher order, multi-information terms. These ideas are illustrated by analyses of gene expression, financial markets, and consumer preferences. In each case, information theoretic measures correlate with independent, intuitive measures of the underlying structures in the system. AU - Slonim,Noam AU - Atwal,Gurinder S AU - Gasper Tkacik AU - Bialek, William S ID - 3746 T2 - ArXiv TI - Estimating mutual information and multi-information in large networks ER - TY - JOUR AB - Action potentials in central neurons are initiated near the axon initial segment, propagate into the axon, and finally invade the presynaptic terminals, where they trigger transmitter release. Voltage-gated Na(+) channels are key determinants of excitability, but Na(+) channel density and properties in axons and presynaptic terminals of cortical neurons have not been examined yet. In hippocampal mossy fiber boutons, which emerge from parent axons en passant, Na(+) channels are very abundant, with an estimated number of approximately 2000 channels per bouton. Presynaptic Na(+) channels show faster inactivation kinetics than somatic channels, suggesting differences between subcellular compartments of the same cell. Computational analysis of action potential propagation in axon-multibouton structures reveals that Na(+) channels in boutons preferentially amplify the presynaptic action potential and enhance Ca(2+) inflow, whereas Na(+) channels in axons control the reliability and speed of propagation. Thus, presynaptic and axonal Na(+) channels contribute differentially to mossy fiber synaptic transmission. AU - Engel, Dominique AU - Peter Jonas ID - 3808 IS - 3 JF - Neuron TI - Presynaptic action potential amplification by voltage-gated Na+ channels in hippocampal mossy fiber boutons VL - 45 ER - TY - CONF AB - In 2-player non-zero-sum games, Nash equilibria capture the options for rational behavior if each player attempts to maximize her payoff. In contrast to classical game theory, we consider lexicographic objectives: first, each player tries to maximize her own payoff, and then, the player tries to minimize the opponent's payoff. Such objectives arise naturally in the verification of systems with multiple components. There, instead of proving that each component satisfies its specification no matter how the other components behave, it often suffices to prove that each component satisfies its specification provided that the other components satisfy their specifications. We say that a Nash equilibrium is secure if it is an equilibrium with respect to the lexicographic objectives of both players. We prove that in graph games with Borel winning conditions, which include the games that arise in verification, there may be several Nash equilibria, but there is always a unique maximal payoff profile of a secure equilibrium. We show how this equilibrium can be computed in the case of omega-regular winning conditions, and we characterize the memory requirements of strategies that achieve the equilibrium. AU - Krishnendu Chatterjee AU - Thomas Henzinger AU - Jurdziński, Marcin ID - 3892 TI - Games with secure equilibria VL - 3657 ER - TY - CONF AU - Cremer, Sylvia AU - Boomsma, Jacobus ID - 3902 TI - The drawback of mobility: invasive species in a globalised world ER - TY - JOUR AB - Resident dendritic cells (DC) within the T cell area of the lymph node take up soluble antigens that enter via the afferent lymphatics before antigen carrying DC arrive from the periphery. The reticular network within the lymph node is a conduit system forming the infrastructure for the fast delivery of soluble substances from the afferent lymph to the lumen of high endothelial venules (HEVs). Using high-resolution light microscopy and 3D reconstruction, we show here that these conduits are unique basement membrane-like structures ensheathed by fibroblastic reticular cells with occasional resident DC embedded within this cell layer. Conduit-associated DC are capable of taking up and processing soluble antigens transported within the conduits, whereas immigrated mature DC occur remote from the reticular fibers. The conduit system is, therefore, not a closed compartment that shuttles substances through the lymph node but represents the morphological equivalent to the filtering function of the lymph node. AU - Sixt, Michael K AU - Kanazawa, Nobuo AU - Selg, Manuel AU - Samson, Thomas AU - Roos, Gunnel AU - Reinhardt, Dieter AU - Pabst, Reinhard AU - Lutz, Manfred AU - Sorokin, Lydia ID - 3933 IS - 1 JF - Immunity TI - The conduit system transports soluble antigens from the afferent lymph to resident dendritic cells in the T cell area of the lymph node VL - 22 ER - TY - JOUR AB - Cdc25 phosphatases are key activators of the eukaryotic cell cycle and compelling anticancer targets because their overexpression has been associated with numerous cancers. However, drug discovery targeting these phosphatases has been hampered by the lack of structural information about how Cdc25s interact with their native protein substrates, the cyclin-dependent kinases. Herein, we predict a docked orientation for Cdc25B with its Cdk2-pTpY-CycA protein substrate by a rigid-body docking method and refine the docked models with full-scale molecular dynamics simulations and minimization. We validate the stable ensemble structure experimentally by a variety of in vitro and in vivo techniques. Specifically, we compare our model with a crystal structure of the substrate-trapping mutant of Cdc25B. We identify and validate in vivo a novel hot-spot residue on Cdc25B (Arg492) that plays a central role in protein substrate recognition. We identify a hot-spot residue on the Substrate Cdk2 (Asp206) and confirm its interaction with hot-spot residues on Cdc25 using hot-spot swapping and double mutant cycles to derive interaction energies. Our experimentally validated model is consistent with previous studies of Cdk2 and its interaction partners and initiates the opportunity for drug discovery of inhibitors that target the remote binding sites of this protein-protein interaction. AU - Sohn, Jungsan AU - Parks, Jerry M AU - Buhrman, Gregory AU - Brown, Paul AU - Kristjánsdóttir, Kolbrun AU - Safi, Alexias AU - Herbert Edelsbrunner AU - Yang, Weitao T AU - Rudolph, Johannes ID - 3983 IS - 50 JF - Biochemistry TI - Experimental validation of the docking orientation of Cdc25 with its Cdk2-CycA protein substrate VL - 44 ER - TY - CONF AB - We present an efficient algorithm for generating a small set of coarse alignments between interacting proteins using meaningful features on their surfaces. The proteins are treated as rigid bodies, but the results are more generally useful as the produced configurations can serve as input to local improvement algorithms that allow for protein flexibility. We apply our algorithm to a diverse set of protein complexes from the Protein Data Bank, demonstrating the effectivity of our algorithm, both for bound and for unbound protein docking problems. AU - Wang, Yusu AU - Agarwal, Pankaj K AU - Brown, Paul AU - Herbert Edelsbrunner AU - Rudolph, Johannes ID - 3982 TI - Coarse and reliable geometric alignment for protein docking ER - TY - JOUR AB - Wnt11 plays a central role in tissue morphogenesis during vertebrate gastrulation, but the molecular and cellular mechanisms by which Wnt11 exerts its effects remain poorly understood. Here, we show that Wnt11 functions during zebrafish gastrulation by regulating the cohesion of mesodermal and endodermal (mesendodermal) progenitor cells. Importantly, we demonstrate that Wnt11 activity in this process is mediated by the GTPase Rab5, a key regulator of early endocytosis, as blocking Rab5c activity in wild-type embryos phenocopies slb/wnt11 mutants, and enhancing Rab5c activity in slb/wnt11 mutant embryos rescues the mutant phenotype. In addition, we find that Wnt11 and Rab5c control the endocytosis of E-cadherin and are required in mesendodermal cells for E-cadherin-mediated cell cohesion. Together, our results suggest that Wnt11 controls tissue morphogenesis by modulating E-cadherin-mediated cell cohesion through Rab5c, a novel mechanism of Wnt signaling in gastrulation. AU - Ulrich, Florian AU - Krieg, Michael AU - Schötz, Eva AU - Link, Vinzenz AU - Castanon, Irinka AU - Schnabel, Viktor AU - Taubenberger, Anna AU - Müller, Daniel AU - Puech, Pierre AU - Heisenberg, Carl-Philipp J ID - 4144 IS - 4 JF - Developmental Cell TI - Wnt11 functions in gastrulation by controlling cell cohesion through Rab5c and E-cadherin VL - 9 ER - TY - JOUR AB - Adaptive dynamics describes the evolution of an asexual population through the successive substitution of mutations of small effect. Waxman & Gavrilets (2005) give an excellent overview of the method and its applications. In this note, we focus on the plausibility of the key assumption that mutations have small effects, and the consequences of relaxing that assumption. We argue that: (i) successful mutations often have large effects; (ii) such mutations generate a qualitatively different evolutionary pattern, which is inherently stochastic; and (iii) in models of competition for a continuous resource, selection becomes very weak once several phenotypes are established. This makes the effects of introducing new mutations unpredictable using the methods of adaptive dynamics. We should make clear at the outset that our criticism is of methods that rely on local analysis of fitness gradients (eqn 2 of Waxman & Gavrilets, 2005), and not of the broader idea that evolution can be understood by examining the invasion of successive mutations. We use the term ‘adaptive dynamics’ to refer to the former technique, and contrast it with a more general population genetic analysis of probabilities of invasion. AU - Nicholas Barton AU - Jitka Polechova ID - 4138 IS - 5 JF - Journal of Evolutionary Biology TI - The limitations of adaptive dynamics as a model of evolution VL - 18 ER - TY - JOUR AB - During vertebrate gastrulation, progenitor cells of different germ layers acquire specific adhesive properties that contribute to germ layer formation and separation. Wnt signals have been suggested to function in this process by modulating the different levels of adhesion between the germ layers, however, direct evidence for this is still lacking. Here we show that Wnt11, a key signal regulating gastrulation movements, is needed for the adhesion of zebrafish mesendodermal progenitor cells to fibronectin, an abundant extracellular matrix component during gastrulation. To measure this effect, we developed an assay to quantify the adhesion of single zebrafish primary mesendodermal progenitors using atomic-force microscopy (AFM). We observed significant differences in detachment force and work between cultured mesendodermal progenitors from wild-type embryos and from slb/wit11 mutant embryos, which carry a loss-of-function mutation in the wnt11 gene, when tested on fibronectin-coated substrates. These differences were probably due to reduced adhesion to the fibronectin substrate as neither the overall cell morphology nor the cell elasticity grossly differed between wild-type and mutant cells. Furthermore, in the presence of inhibitors of fibronectin-integrin binding, such as RGD peptides, the adhesion force and work were strongly decreased, indicating that integrins are involved in the binding of mesendodermal progenitors in our assay. These findings demonstrate that AFM can be used to quantitatively determine the substrate-adhesion of cultured primary gastrulating cells and provide insight into the role of Wnt11 signalling in modulating cell adhesion at the single cell scale. AU - Puech, Pierre AU - Taubenberger, Anna AU - Ulrich, Florian AU - Krieg, Michael AU - Mueller, Daniel AU - Heisenberg, Carl-Philipp J ID - 4155 IS - 18 JF - Journal of Cell Science TI - Measuring cell adhesion forces of primary gastrulating cells from zebrafish using atomic force microscopy VL - 118 ER - TY - JOUR AB - During vertebrate gastrulation, the three germ layers, ectoderm, mesoderm and endoderm are formed, and the resulting progenitor cells are brought into the positions from which they will later contribute more complex tissues and organs. A core element in this process is the internalization of mesodermal and endodermal progenitors at the onset of gastrulation. Although many of the molecules that induce mesendoderm have been identified, much less is known about the cellular mechanisms underlying mesendodermal cell internalization and germ layer formation. Here we show that at the onset of zebrafish gastrulation, mesendodermal progenitors in dorsal/axial regions of the germ ring internalize by single cell delamination. Once internalized, mesendodermal progenitors upregulate ECadherin (Cadherin 1) expression, become increasingly motile and eventually migrate along the overlying epiblast (ectodermal) cell layer towards the animal pole of the gastrula. When E-Cadherin function is compromised, mesendodermal progenitors still internalize, but, with gastrulation proceeding, fail to elongate and efficiently migrate along the epiblast, whereas epiblast cells themselves exhibit reduced radial cell intercalation movements. This indicates that cadherin-mediated cell-cell adhesion is needed within the forming shield for both epiblast cell intercalation, and mesendodermal progenitor cell elongation and migration during zebrafish gastrulation. Our data provide insight into the cellular mechanisms underlying mesendodermal progenitor cell internalization and subsequent migration during zebrafish gastrulation, and the role of cadherin-mediated cell-cell adhesion in these processes. AU - Montero, Juan AU - Carvalho, Lara AU - Wilsch Bräuninger, Michaela AU - Kilian, Beate AU - Mustafa, Chigdem AU - Heisenberg, Carl-Philipp J ID - 4171 IS - 6 JF - Development TI - Shield formation at the onset of zebrafish gastrulation VL - 132 ER - TY - JOUR AB - We examined causes of speciation in asexual populations in both sympatry and parapatry, providing an alternative explanation for the speciation patterns reported by Dieckmann and Doebeli (1999) and Doebeli and Dieckmann (2003). Both in sympatry and parapatry, they find that speciation occurs relatively easily. We reveal that in the sympatric clonal model, the equilibrium distribution is continuous and the disruptive selection driving evolution of discrete clusters is only transient. Hence, if discrete phenotypes are to remain stable in the sympatric sexual model, there should be some source of nontransient disruptive selection that will drive evolution of assortment. We analyze sexually reproducing populations using the Bulmer’s infinitesimal model and show that cost-free assortment alone leads to speciation and disruptive selection only arises when the optimal distribution cannot be matched—in this example, because the phenotypic range is limited. In addition, Doebeli and Dieckmann’s analyses assumed a high genetic variance and a high mutation rate. Thus, these theoretical models do not support the conclusion that sympatric speciation is a likely outcome of competition for resources. In their parapatric model (Doebeli and Dieckmann 2003), clustering into distinct phenotypes is driven by edge effects, rather than by frequency-dependent competition. AU - Jitka Polechova AU - Nicholas Barton ID - 4249 IS - 6 JF - Evolution; International Journal of Organic Evolution TI - Speciation through competition: A critical review VL - 59 ER - TY - JOUR AB - In finite populations subject to selection, genetic drift generates negative linkage disequilibrium, on average, even if selection acts independently (i.e. multiplicatively) upon all loci. Negative disequilibrium reduces the variance in fitness and hence, by FISHER's Fundamental Theorem (1930), slows the rate of increase in mean fitness. Modifiers that increase recombination eliminate the negative disequilibria that impede selection and consequently increase in frequency by 'hitch-hiking'. In addition, recombinant progeny are more fit on average than non-recombinant progeny when there is negative linkage disequilibrium and loci interact multiplicatively. For both these reasons, stochastic fluctuations in linkage disequilibrium in finite populations favor the evolution of increased rates of recombination, even in the absence of epistatic interactions among loci and even when disequilibrium is initially absent. The method developed within this paper quantifies the strength of selection on a modifier allele that increases recombination due to stochastically generated linkage disequilibria. The analysis indicates that, in a population subject to multiplicative selection, genetic associations generated by drift do select for increased recombination, a result that is confirmed by Monte Carlo simulations. Selection for a modifier that increases recombination is highest when linkage among all loci is tight, when beneficial alleles rise from low to high frequency, and when the population size is small. AU - Nicholas Barton AU - Otto, Sarah P ID - 4251 IS - 4 JF - Genetics TI - Evolution of recombination due to random drift VL - 169 ER - TY - JOUR AB - Empirical studies of quantitative genetic variation have revealed robust patterns that are observed both across traits and across species. However, these patterns have no compelling explanation, and some of the observations even appear to be mutually incompatible. We review and extend a major class of theoretical models, ‘mutation–selection models’, that have been proposed to explain quantitative genetic variation. We also briefly review an alternative class of ‘balancing selection models’. We consider to what extent the models are compatible with the general observations, and argue that a key issue is understanding and modelling pleiotropy. We discuss some AU - Johnson, Toby AU - Nicholas Barton ID - 4252 IS - 1459 JF - Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences TI - Theoretical models of selection and mutationon quantitative traits VL - 360 ER - TY - CONF AU - Alur, Rajeev AU - Pavol Cerny AU - Madhusudan,P. AU - Nam,Wonhong ID - 4404 TI - Synthesis of interface specifications for Java classes ER - TY - CONF AB - The periodic resource model for hierarchical, compositional scheduling abstracts task groups by resource requirements. We study this model in the presence of dataflow constraints between the tasks within a group (intragroup dependencies), and between tasks in different groups (inter-group dependencies). We consider two natural semantics for dataflow constraints, namely, RTW (real-time workshop) semantics and LET (logical execution time) semantics. We show that while RTW semantics offers better end-to-end latency on the task group level, LET semantics allows tighter resource bounds in the abstraction hierarchy and therefore provides better composability properties. This result holds both for intragroup and intergroup dependencies, as well as for shared and for distributed resources. AU - Matic, Slobodan AU - Thomas Henzinger ID - 4412 TI - Trading end-to-end latency for composability ER - TY - CONF AB - We present a new software system architecture for the implementation of hard real-time applications. The core of the system is a microkernel whose reactivity (interrupt handling as in synchronous reactive programs) and proactivity (task scheduling as in traditional RTOSs) are fully programmable. The microkernel, which we implemented on a StrongARM processor, consists of two interacting domain-specific virtual machines, a reactive E (Embedded) machine and a proactive S (Scheduling) machine. The microkernel code (or microcode) that runs on the microkernel is partitioned into E and S code. E code manages the interaction of the system with the physical environment: the execution of E code is triggered by environment interrupts, which signal external events such as the arrival of a message or sensor value, and it releases application tasks to the S machine. S code manages the interaction of the system with the processor: the execution of S code is triggered by hardware interrupts, which signal internal events such as the completion of a task or time slice, and it dispatches application tasks to the CPU, possibly preempting a running task. This partition of the system orthogonalizes the two main concerns of real-time implementations: E code refers to environment time and thus defines the reactivity of the system in a hardware- and scheduler-independent fashion; S code refers to CPU time and defines a system scheduler. If both time lines can be reconciled, then the code is called time safe; violations of time safety are handled again in a programmable way, by run-time exceptions. The separation of E from S code permits the independent programming, verification, optimization, composition, dynamic adaptation, and reuse of both reaction and scheduling mechanisms. Our measurements show that the system overhead is very acceptable even for large sets of task, generally in the 0.2--0.3% range. AU - Kirsch, Christoph M AU - Sanvido, Marco A AU - Thomas Henzinger ID - 4418 TI - A programmable microkernel for real-time systems ER - TY - JOUR AB - We define five increasingly comprehensive classes of infinite-state systems, called STS1--STS5, whose state spaces have finitary structure. For four of these classes, we provide examples from hybrid systems.STS1 These are the systems with finite bisimilarity quotients. They can be analyzed symbolically by iteratively applying predecessor and Boolean operations on state sets, starting from a finite number of observable state sets. Any such iteration is guaranteed to terminate in that only a finite number of state sets can be generated. This enables model checking of the μ-calculus.STS2 These are the systems with finite similarity quotients. They can be analyzed symbolically by iterating the predecessor and positive Boolean operations. This enables model checking of the existential and universal fragments of the μ-calculus.STS3 These are the systems with finite trace-equivalence quotients. They can be analyzed symbolically by iterating the predecessor operation and a restricted form of positive Boolean operations (intersection is restricted to intersection with observables). This enables model checking of all ω-regular properties, including linear temporal logic.STS4 These are the systems with finite distance-equivalence quotients (two states are equivalent if for every distance d, the same observables can be reached in d transitions). The systems in this class can be analyzed symbolically by iterating the predecessor operation and terminating when no new state sets are generated. This enables model checking of the existential conjunction-free and universal disjunction-free fragments of the μ-calculus.STS5 These are the systems with finite bounded-reachability quotients (two states are equivalent if for every distance d, the same observables can be reached in d or fewer transitions). The systems in this class can be analyzed symbolically by iterating the predecessor operation and terminating when no new states are encountered (this is a weaker termination condition than above). This enables model checking of reachability properties. AU - Thomas Henzinger AU - Majumdar, Ritankar S AU - Raskin, Jean-François ID - 4454 IS - 1 JF - ACM Transactions on Computational Logic (TOCL) TI - A classification of symbolic transition systems VL - 6 ER - TY - CONF AB - We define quantitative similarity functions between timed transition systems that measure the degree of closeness of two systems as a real, in contrast to the traditional boolean yes/no approach to timed simulation and language inclusion. Two systems are close if for each timed trace of one system, there exists a corresponding timed trace in the other system with the same sequence of events and closely corresponding event timings. We show that timed CTL is robust with respect to our quantitative version of bisimilarity, in particular, if a system satisfies a formula, then every close system satisfies a close formula. We also define a discounted version of CTL over timed systems, which assigns to every CTL formula a real value that is obtained by discounting real time. We prove the robustness of discounted CTL by establishing that close states in the bisimilarity metric have close values for all discounted CTL formulas. AU - Thomas Henzinger AU - Majumdar, Ritankar S AU - Prabhu, Vinayak S ID - 4455 TI - Quantifying similarities between timed systems VL - 3829 ER - TY - CONF AB - A modular program analysis considers components independently and provides a succinct summary for each component, which is used when checking the rest of the system. Consider a system consisting of a library and a client. A temporal summary, or interface, of the library specifies legal sequences of library calls. The interface is safe if no call sequence violates the library's internal invariants; the interface is permissive if it contains every such sequence. Modular program analysis requires full interfaces, which are both safe and permissive: the client does not cause errors in the library if and only if it makes only sequences of library calls that are allowed by the full interface of the library.Previous interface-based methods have focused on safe interfaces, which may be too restrictive and thus reject good clients. We present an algorithm for automatically synthesizing software interfaces that are both safe and permissive. The algorithm generates interfaces as graphs whose vertices are labeled with predicates over the library's internal state, and whose edges are labeled with library calls. The interface state is refined incrementally until the full interface is constructed. In other words, the algorithm automatically synthesizes a typestate system for the library, against which any client can be checked for compatibility. We present an implementation of the algorithm which is based on the BLAST model checker, and we evaluate some case studies. AU - Thomas Henzinger AU - Jhala, Ranjit AU - Majumdar, Ritankar S ID - 4456 TI - Permissive interfaces ER - TY - CONF AB - We present a compositional approach to the implementation of hard real-time software running on a distributed platform. We explain how several code suppliers, coordinated by a system integrator, can independently generate different parts of the distributed software. The task structure, interaction, and timing is specified as a Giotto program. Each supplier is given a part of the Giotto program and a timing interface, from which the supplier generates task and scheduling code. The integrator then checks, individually for each supplier, in pseudo-polynomial time, if the supplied code meets its timing specification. If all checks succeed, then the supplied software parts are guaranteed to work together and implement the original Giotto program. The feasibility of the approach is demonstrated by a prototype implementation. AU - Thomas Henzinger AU - Kirsch, Christoph M AU - Matic, Slobodan ID - 4457 TI - Composable code generation for distributed Giotto ER - TY - CONF AB - We show how to automatically construct and refine rectangular abstractions of systems of linear differential equations. From a hybrid automaton whose dynamics are given by a system of linear differential equations, our method computes automatically a sequence of rectangular hybrid automata that are increasingly precise overapproximations of the original hybrid automaton. We prove an optimality criterion for successive refinements. We also show that this method can take into account a safety property to be verified, refining only relevant parts of the state space. The practicability of the method is illustrated on a benchmark case study. AU - Doyen, Laurent AU - Thomas Henzinger AU - Raskin, Jean-François ID - 4536 TI - Automatic rectangular refinement of affine hybrid systems VL - 3829 ER - TY - CONF AB - Much recent research has focused on the applications of games with ω-regular objectives in the control and verification of reactive systems. However, many of the game-based models are ill-suited for these applications, because they assume that each player has complete information about the state of the system (they are “perfect-information” games). This is because in many situations, a controller does not see the private state of the plant. Such scenarios are naturally modeled by “partial-information” games. On the other hand, these games are intractable; for example, partial-information games with simple reachability objectives are 2EXPTIME-complete. We study the intermediate case of “semiperfect-information” games, where one player has complete knowledge of the state, while the other player has only partial knowledge. This model is appropriate in control situations where a controller must cope with plant behavior that is as adversarial as possible, i.e., the controller has partial information while the plant has perfect information. As is customary, we assume that the controller and plant take turns to make moves. We show that these semiperfect-information turn-based games are equivalent to perfect-information concurrent games, where the two players choose their moves simultaneously and independently. Since the perfect-information concurrent games are well-understood, we obtain several results of how semiperfect-information turn-based games differ from perfect-information turn-based games on one hand, and from partial-information turn-based games on the other hand. In particular, semiperfect-information turn-based games can benefit from randomized strategies while the perfect-information variety cannot, and semiperfect-information turn-based games are in NP ∩ coNP for all parity objectives. AU - Krishnendu Chatterjee AU - Thomas Henzinger ID - 4541 TI - Semiperfect-information games VL - 3821 ER - TY - CONF AB - The theory of graph games with ω-regular winning conditions is the foundation for modeling and synthesizing reactive processes. In the case of stochastic reactive processes, the corresponding stochastic graph games have three players, two of them (System and Environment) behaving adversarially, and the third (Uncertainty) behaving probabilistically. We consider two problems for stochastic graph games: the qualitative problem asks for the set of states from which a player can win with probability 1 (almost-sure winning); the quantitative problem asks for the maximal probability of winning (optimal winning) from each state. We show that for Rabin winning conditions, both problems are in NP. As these problems were known to be NP-hard, it follows that they are NP-complete for Rabin conditions, and dually, coNP-complete for Streett conditions. The proof proceeds by showing that pure memoryless strategies suffice for qualitatively and quantitatively winning stochastic graph games with Rabin conditions. This insight is of interest in its own right, as it implies that controllers for Rabin objectives have simple implementations. We also prove that for every ω-regular condition, optimal winning strategies are no more complex than almost-sure winning strategies. AU - Krishnendu Chatterjee AU - de Alfaro, Luca AU - Thomas Henzinger ID - 4553 TI - The complexity of stochastic Rabin and Streett games VL - 3580 ER - TY - CONF AB - Games played on graphs may have qualitative objectives, such as the satisfaction of an ω-regular property, or quantitative objectives, such as the optimization of a real-valued reward. When games are used to model reactive systems with both fairness assumptions and quantitative (e.g., resource) constraints, then the corresponding objective combines both a qualitative and a quantitative component. In a general case of interest, the qualitative component is a parity condition and the quantitative component is a mean-payoff reward. We study and solve such mean-payoff parity games. We also prove some interesting facts about mean-payoff parity games which distinguish them both from mean-payoff and from parity games. In particular, we show that optimal strategies exist in mean-payoff parity games, but they may require infinite memory. AU - Krishnendu Chatterjee AU - Thomas Henzinger AU - Jurdziński, Marcin ID - 4554 TI - Mean-payoff parity games ER - TY - CONF AB - We define and study a quantitative generalization of the traditional boolean framework of model-based specification and verification. In our setting, propositions have integer values at states, and properties have integer values on traces. For example, the value of a quantitative proposition at a state may represent power consumed at the state, and the value of a quantitative property on a trace may represent energy used along the trace. The value of a quantitative property at a state, then, is the maximum (or minimum) value achievable over all possible traces from the state. In this framework, model checking can be used to compute, for example, the minimum battery capacity necessary for achieving a given objective, or the maximal achievable lifetime of a system with a given initial battery capacity. In the case of open systems, these problems require the solution of games with integer values. Quantitative model checking and game solving is undecidable, except if bounds on the computation can be found. Indeed, many interesting quantitative properties, like minimal necessary battery capacity and maximal achievable lifetime, can be naturally specified by quantitative-bound automata, which are finite automata with integer registers whose analysis is constrained by a bound function f that maps each system K to an integer f(K). Along with the linear-time, automaton-based view of quantitative verification, we present a corresponding branching-time view based on a quantitative-bound μ-calculus, and we study the relationship, expressive power, and complexity of both views. AU - Chakrabarti, Arindam AU - Krishnendu Chatterjee AU - Thomas Henzinger AU - Kupferman, Orna AU - Majumdar, Ritankar S ID - 4560 TI - Verifying quantitative properties using bound functions VL - 3725 ER - TY - CONF AB - Planning in adversarial and uncertain environments can be modeled as the problem of devising strategies in stochastic perfect information games. These games are generalizations of Markov decision processes (MDPs): there are two (adversarial) players, and a source of randomness. The main practical obstacle to computing winning strategies in such games is the size of the state space. In practice therefore, one typically works with abstractions of the model. The diffculty is to come up with an abstraction that is neither too coarse to remove all winning strategies (plans), nor too fine to be intractable. In verification, the paradigm of counterexample-guided abstraction refinement has been successful to construct useful but parsimonious abstractions automatically. We extend this paradigm to probabilistic models (namely, perfect information games and, as a special case, MDPs). This allows us to apply the counterexample-guided abstraction paradigm to the AI planning problem. As special cases, we get planning algorithms for MDPs and deterministic systems that automatically construct system abstractions. AU - Krishnendu Chatterjee AU - Thomas Henzinger AU - Jhala, Ranjit AU - Majumdar, Ritankar S ID - 4557 TI - Counterexample-guided planning ER - TY - CONF AB - BLAST is an automatic verification tool for checking temporal safety properties of C programs. Given a C program and a temporal safety property, BLAST statically proves that either the program satisfies the safety property or the program has an execution trace that exhibits a violation of the property. BLAST constructs, explores, and refines abstractions of the program state space based on lazy predicate abstraction and interpolation-based predicate discovery. We show how BLAST can be used to statically prove memory safety for C programs. We take a two-step approach. First, we use Ccured, a type-based memory safety analyzer, to annotate with run-time checks all program points that cannot be proved memory safe by the type system. Second, we use BLAST to remove as many of the run-time checks as possible (by proving that these checks never fail), and to generate for the remaining run-time checks execution traces that witness them fail. Our experience shows that BLAST can remove many of the run-time checks added by Ccured and provide useful information to the programmer about many of the remaining checks. AU - Beyer, Dirk AU - Thomas Henzinger AU - Jhala, Ranjit AU - Majumdar, Ritankar S ID - 4579 TI - Checking memory safety with BLAST VL - 3442 ER - TY - CONF AB - We present a language for specifying web service interfaces. A web service interface puts three kinds of constraints on the users of the service. First, the interface specifies the methods that can be called by a client, together with types of input and output parameters; these are called signature constraints. Second, the interface may specify propositional constraints on method calls and output values that may oc- cur in a web service conversation; these are called consis- tency constraints. Third, the interface may specify temporal constraints on the ordering of method calls; these are called protocol constraints. The interfaces can be used to check, first, if two or more web services are compatible, and second, if a web service A can be safely substituted for a web ser- vice B. The algorithm for compatibility checking verifies that two or more interfaces fulfill each others’ constraints. The algorithm for substitutivity checking verifies that service A demands fewer and fulfills more constraints than service B. AU - Beyer, Dirk AU - Chakrabarti, Arindam AU - Thomas Henzinger ID - 4576 TI - Web service interfaces ER - TY - JOUR AB - Temporal logic is two-valued: formulas are interpreted as either true or false. When applied to the analysis of stochastic systems, or systems with imprecise formal models, temporal logic is therefore fragile: even small changes in the model can lead to opposite truth values for a specification. We present a generalization of the branching-time logic CTL which achieves robustness with respect to model perturbations by giving a quantitative interpretation to predicates and logical operators, and by discounting the importance of events according to how late they occur. In every state, the value of a formula is a real number in the interval [0,1], where 1 corresponds to truth and 0 to falsehood. The boolean operators and and or are replaced by min and max, the path quantifiers ∃ and ∀ determine sup and inf over all paths from a given state, and the temporal operators ⋄ and □ specify sup and inf over a given path; a new operator averages all values along a path. Furthermore, all path operators are discounted by a parameter that can be chosen to give more weight to states that are closer to the beginning of the path. We interpret the resulting logic DCTL over transition systems, Markov chains, and Markov decision processes. We present two semantics for DCTL: a path semantics, inspired by the standard interpretation of state and path formulas in CTL, and a fixpoint semantics, inspired by the μ-calculus evaluation of CTL formulas. We show that, while these semantics coincide for CTL, they differ for DCTL, and we provide model-checking algorithms for both semantics. AU - de Alfaro, Luca AU - Faella, Marco AU - Thomas Henzinger AU - Majumdar, Ritankar S AU - Stoelinga, Mariëlle ID - 4625 IS - 1 JF - Theoretical Computer Science TI - Model checking discounted temporal properties VL - 345 ER - TY - CONF AB - Surveying results from [5] and [6], we motivate and introduce the theory behind formalizing rich interfaces for software and hardware components. Rich interfaces specify the protocol aspects of component interaction. Their formalization, called interface automata, permits a compiler to check the compatibility of component interaction protocols. Interface automata support incremental design and independent implementability. Incremental design means that the compatibility checking of interfaces can proceed for partial system descriptions, without knowing the interfaces of all components. Independent implementability means that compatible interfaces can be refined separately, while still maintaining compatibility. AU - de Alfaro, Luca AU - Thomas Henzinger ID - 4624 TI - Interface-based design VL - 195 ER - TY - CONF AB - We present the first demonstration of Jozsa's "counterfactual computation", using an optical Grover's search algorithm. We put the algorithm in a superposition of 'running' and 'not-running', obtaining information even though the algorithm does not run. AU - Onur Hosten AU - Rakher, Matthew T AU - Barreiro, Julio T AU - Peters, Nicholas A AU - Kwiat, Paul G ID - 575 TI - Counterfactual quantum computation VL - 1 ER - TY - JOUR AB - A current challenge in neuroscience is to bridge the gaps between genes, proteins, neurons, neural circuits, and behavior in a single animal model. The nematode Caenorhabditis elegans has unique features that facilitate this synthesis. Its nervous system includes exactly 302 neurons, and their pattern of synaptic connectivity is known. With only five olfactory neurons, C. elegans can dynamically respond to dozens of attractive and repellant odors. Thermosensory neurons enable the nematode to remember its cultivation temperature and to track narrow isotherms. Polymodal sensory neurons detect a wide range of nociceptive cues and signal robust escape responses. Pairing of sensory stimuli leads to long-lived changes in behavior consistent with associative learning. Worms exhibit social behaviors and complex ultradian rhythms driven by Ca2+ oscillators with clock-like properties. Genetic analysis has identified gene products required for nervous system function and elucidated the molecular and neural bases of behaviors. AU - de Bono, Mario AU - Villu Maricq, Andres ID - 6153 JF - Annual Review of Neuroscience SN - 0147-006X TI - Neuronal substrates of complex behaviors in C. elegans VL - 28 ER - TY - JOUR AU - Cheung, Benny H.H. AU - Cohen, Merav AU - Rogers, Candida AU - Albayram, Onder AU - de Bono, Mario ID - 6154 IS - 10 JF - Current Biology SN - 0960-9822 TI - Experience-dependent modulation of C. elegans behavior by ambient oxygen VL - 15 ER - TY - JOUR AB - Transmission of signals within the brain is essential for cognitive function, but it is not clear how neural circuits support reliable and accurate signal propagation over a sufficiently large dynamic range. Two modes of propagation have been studied: synfire chains, in which synchronous activity travels through feedforward layers of a neuronal network, and the propagation of fluctuations in firing rate across these layers. In both cases, a sufficient amount of noise, which was added to previous models from an external source, had to be included to support stable propagation. Sparse, randomly connected networks of spiking model neurons can generate chaotic patterns of activity. We investigate whether this activity, which is a more realistic noise source, is sufficient to allow for signal transmission. We find that, for rate-coded signals but not for synfire chains, such networks support robust and accurate signal reproduction through up to six layers if appropriate adjustments are made in synaptic strengths. We investigate the factors affecting transmission and show that multiple signals can propagate simultaneously along different pathways. Using this feature, we show how different types of logic gates can arise within the architecture of the random network through the strengthening of specific synapses. AU - Vogels, Tim P AU - Abbott, L. F. ID - 8028 IS - 46 JF - Journal of Neuroscience SN - 0270-6474 TI - Signal propagation and logic gating in networks of integrate-and-fire neurons VL - 25 ER - TY - JOUR AB - Neural network modeling is often concerned with stimulus-driven responses, but most of the activity in the brain is internally generated. Here, we review network models of internally generated activity, focusing on three types of network dynamics: (a) sustained responses to transient stimuli, which provide a model of working memory; (b) oscillatory network activity; and (c) chaotic activity, which models complex patterns of background spiking in cortical and other circuits. We also review propagation of stimulus-driven activity through spontaneously active networks. Exploring these aspects of neural network dynamics is critical for understanding how neural circuits produce cognitive function. AU - Vogels, Tim P AU - Rajan, Kanaka AU - Abbott, L.F. ID - 8029 IS - 1 JF - Annual Review of Neuroscience SN - 0147-006X TI - Neural network dynamics VL - 28 ER - TY - JOUR AB - Cytosine DNA methylation in vertebrates is widespread, but methylation in plants is found almost exclusively at transposable elements and repetitive DNA [1]. Within regions of methylation, methylcytosines are typically found in CG, CNG, and asymmetric contexts. CG sites are maintained by a plant homolog of mammalian Dnmt1 acting on hemi-methylated DNA after replication. Methylation of CNG and asymmetric sites appears to be maintained at each cell cycle by other mechanisms. We report a new type of DNA methylation in Arabidopsis, dense CG methylation clusters found at scattered sites throughout the genome. These clusters lack non-CG methylation and are preferentially found in genes, although they are relatively deficient toward the 5′ end. CG methylation clusters are present in lines derived from different accessions and in mutants that eliminate de novo methylation, indicating that CG methylation clusters are stably maintained at specific sites. Because 5-methylcytosine is mutagenic, the appearance of CG methylation clusters over evolutionary time predicts a genome-wide deficiency of CG dinucleotides and an excess of C(A/T)G trinucleotides within transcribed regions. This is exactly what we find, implying that CG methylation clusters have contributed profoundly to plant gene evolution. We suggest that CG methylation clusters silence cryptic promoters that arise sporadically within transcription units. AU - Tran, Robert K. AU - Henikoff, Jorja G. AU - Zilberman, Daniel AU - Ditt, Renata F. AU - Jacobsen, Steven E. AU - Henikoff, Steven ID - 9491 IS - 2 JF - Current Biology SN - 0960-9822 TI - DNA methylation profiling identifies CG methylation clusters in Arabidopsis genes VL - 15 ER - TY - JOUR AB - Background: DNA methylation occurs at preferred sites in eukaryotes. In Arabidopsis, DNA cytosine methylation is maintained by three subfamilies of methyltransferases with distinct substrate specificities and different modes of action. Targeting of cytosine methylation at selected loci has been found to sometimes involve histone H3 methylation and small interfering (si)RNAs. However, the relationship between different cytosine methylation pathways and their preferred targets is not known. Results: We used a microarray-based profiling method to explore the involvement of Arabidopsis CMT3 and DRM DNA methyltransferases, a histone H3 lysine-9 methyltransferase (KYP) and an Argonaute-related siRNA silencing component (AGO4) in methylating target loci. We found that KYP targets are also CMT3 targets, suggesting that histone methylation maintains CNG methylation genome-wide. CMT3 and KYP targets show similar proximal distributions that correspond to the overall distribution of transposable elements of all types, whereas DRM targets are distributed more distally along the chromosome. We find an inverse relationship between element size and loss of methylation in ago4 and drm mutants. Conclusion: We conclude that the targets of both DNA methylation and histone H3K9 methylation pathways are transposable elements genome-wide, irrespective of element type and position. Our findings also suggest that RNA-directed DNA methylation is required to silence isolated elements that may be too small to be maintained in a silent state by a chromatin-based mechanism alone. Thus, parallel pathways would be needed to maintain silencing of transposable elements. AU - Tran, Robert K. AU - Zilberman, Daniel AU - de Bustos, Cecilia AU - Ditt, Renata F. AU - Henikoff, Jorja G. AU - Lindroth, Anders M. AU - Delrow, Jeffrey AU - Boyle, Tom AU - Kwong, Samson AU - Bryson, Terri D. AU - Jacobsen, Steven E. AU - Henikoff, Steven ID - 9514 IS - 11 JF - Genome Biology SN - 1474-760X TI - Chromatin and siRNA pathways cooperate to maintain DNA methylation of small transposable elements in Arabidopsis VL - 6 ER - TY - JOUR AB - The impact of an amino acid replacement on the organism's fitness can vary from lethal to selectively neutral and even, in rare cases, beneficial. Substantial data are available on either pathogenic or acceptable replacements. However, the whole distribution of coefficients of selection against individual replacements is not known for any organism. To ascertain this distribution for human proteins, we combined data on pathogenic missense mutations, on human non-synonymous SNPs and on human-chimpanzee divergence of orthologous proteins. Fractions of amino acid replacements which reduce fitness by >10-2, 10-2-10-4, 10-4-10-5 and <10-5 are 25, 49, 14 and 12%, respectively. On average, the strength of selection against a replacement is substantially higher when chemically dissimilar amino acids are involved, and the Grantham's index of a replacement explains 35% of variance in the average logarithm of selection coefficients associated with different replacements. Still, the impact of a replacement depends on its context within the protein more than on its own nature. Reciprocal replacements are often associated with rather different selection coefficients, in particular, replacements of non-polar amino acids with polar ones are typically much more deleterious than replacements in the opposite direction. However, differences between evolutionary fluxes of reciprocal replacements are only weakly correlated with the differences between the corresponding selection coefficients. AU - Yampolsky, Lev Y AU - Fyodor Kondrashov AU - Kondrashov, Alexey S ID - 843 IS - 21 JF - Human Molecular Genetics TI - Distribution of the strength of selection against amino acid replacements in human proteins VL - 14 ER - TY - JOUR AB - Fast multidimensional NMR with a time resolution of a few seconds provides a new tool for high throughput screening and site-resolved real-time studies of kinetic molecular processes by NMR. Recently we have demonstrated the feasibility to record protein 1H–15N correlation spectra in a few seconds of acquisition time using a new SOFAST-HMQC experiment (Schanda and Brutscher (2005) J. Am. Chem. Soc. 127, 8014). Here, we investigate in detail the performance of SOFAST-HMQC to record 1H–15N and 1H−13C correlation spectra of proteins of different size and at different magnetic field strengths. Compared to standard 1H–15N correlation experiments SOFAST-HMQC provides a significant gain in sensitivity, especially for fast repetition rates. Guidelines are provided on how to set up SOFAST-HMQC experiments for a given protein sample. In addition, an alternative pulse scheme, IPAP-SOFAST-HMQC is presented that allows application on NMR spectrometers equipped with cryogenic probes, and fast measurement of one-bond 1H–13C and 1H–15N scalar and residual dipolar coupling constants. AU - Schanda, Paul AU - Kupče, Ēriks AU - Brutscher, Bernhard ID - 8491 IS - 4 JF - Journal of Biomolecular NMR KW - Spectroscopy KW - Biochemistry SN - 0925-2738 TI - SOFAST-HMQC experiments for recording two-dimensional deteronuclear correlation spectra of proteins within a few seconds VL - 33 ER - TY - JOUR AB - We demonstrate for different protein samples that 2D 1H−15N correlation NMR spectra can be recorded in a few seconds of acquisition time using a new band-selective optimized flip-angle short-transient heteronuclear multiple quantum coherence experiment. This has enabled us to measure fast hydrogen−deuterium exchange rate constants along the backbone of a small globular protein fragment by real-time 2D NMR. AU - Schanda, Paul AU - Brutscher, Bernhard ID - 8492 IS - 22 JF - Journal of the American Chemical Society KW - Colloid and Surface Chemistry KW - Biochemistry KW - General Chemistry KW - Catalysis SN - 0002-7863 TI - Very fast two-dimensional NMR spectroscopy for real-time investigation of dynamic events in proteins on the time scale of seconds VL - 127 ER - TY - JOUR AB - The purpose of this paper is to construct examples of diffusion for E-Hamiltonian perturbations of completely integrable Hamiltonian systems in 2d-dimensional phase space, with d large. In the first part of the paper, simple and explicit examples are constructed illustrating absence of ‘long-time’ stability for size E Hamiltonian perturbations of quasi-convex integrable systems already when the dimension 2d of phase space becomes as large as log 1/E . We first produce the example in Gevrey class and then a real analytic one, with some additional work. In the second part, we consider again E-Hamiltonian perturbations of completely integrable Hamiltonian system in 2d-dimensional space with E-small but not too small, |E| > exp(−d), with d the number of degrees of freedom assumed large. It is shown that for a class of analytic time-periodic perturbations, there exist linearly diffusing trajectories. The underlying idea for both examples is similar and consists in coupling a fixed degree of freedom with a large number of them. The procedure and analytical details are however significantly different. As mentioned, the construction in Part I is totally elementary while Part II is more involved, relying in particular on the theory of normally hyperbolic invariant manifolds, methods of generating functions, Aubry–Mather theory, and Mather’s variational methods. AU - Bourgain, Jean AU - Kaloshin, Vadim ID - 8516 IS - 1 JF - Journal of Functional Analysis KW - Analysis SN - 0022-1236 TI - On diffusion in high-dimensional Hamiltonian systems VL - 229 ER - TY - JOUR AB - Sequence analysis of protein and mitochondrially encoded tRNA genes shows that substitutions producing pathogenic effects in humans are often found in normal, healthy individuals from other species. Analysis of stability of protein and tRNA structures shows that the disease-causing effects of pathogenic mutations can be neutralized by other, compensatory substitutions that restore the structural stability of the molecule. Further study of such substitutions will, hopefully, lead to new methods for curing genetic dis- eases that may be based on the correction of molecule stability as a whole instead of reversing an individual pathogenic mutation. AU - Kondrashov, Fyodor ID - 877 IS - 3 JF - Biofizika TI - The analysis of monomer sequences in protein and tRNA and the manifestation of the compensation of pathogenic deviations in their evolution VL - 50 ER - TY - JOUR AB - Negative trade-offs are thought to be a pervasive phenomenon and to inhibit evolution at all levels. New evidence shows that at the molecular level, there may be no trade-offs preventing the emergence of an enzyme with multiple functions. AU - Fyodor Kondrashov ID - 878 IS - 1 JF - Nature Genetics TI - In search of the limits of evolution VL - 37 ER -