TY - JOUR AB - Solid-state NMR provides insight into protein motion over time scales ranging from picoseconds to seconds. While in solution state the methodology to measure protein dynamics is well established, there is currently no such consensus protocol for measuring dynamics in solids. In this article, we perform a detailed investigation of measurement protocols for fast motions, i.e. motions ranging from picoseconds to a few microseconds, which is the range covered by dipolar coupling and relaxation experiments. We perform a detailed theoretical investigation how dipolar couplings and relaxation data can provide information about amplitudes and time scales of local motion. We show that the measurement of dipolar couplings is crucial for obtaining accurate motional parameters, while systematic errors are found when only relaxation data are used. Based on this realization, we investigate how the REDOR experiment can provide such data in a very accurate manner. We identify that with accurate rf calibration, and explicit consideration of rf field inhomogeneities, one can obtain highly accurate absolute order parameters. We then perform joint model-free analyses of 6 relaxation data sets and dipolar couplings, based on previously existing, as well as new data sets on microcrystalline ubiquitin. We show that nanosecond motion can be detected primarily in loop regions, and compare solid-state data to solution-state relaxation and RDC analyses. The protocols investigated here will serve as a useful basis towards the establishment of a routine protocol for the characterization of ps–μs motions in proteins by solid-state NMR. AU - Haller, Jens D. AU - Schanda, Paul ID - 8461 IS - 3 JF - Journal of Biomolecular NMR KW - Spectroscopy KW - Biochemistry SN - 0925-2738 TI - Amplitudes and time scales of picosecond-to-microsecond motion in proteins studied by solid-state NMR: a critical evaluation of experimental approaches and application to crystalline ubiquitin VL - 57 ER - TY - JOUR AB - The transition of proteins from their soluble functional state to amyloid fibrils and aggregates is associated with the onset of several human diseases. Protein aggregation often requires some structural reshaping and the subsequent formation of intermolecular contacts. Therefore, the study of the conformation of excited protein states and their ability to form oligomers is of primary importance for understanding the molecular basis of amyloid fibril formation. Here, we investigated the oligomerization processes that occur along the folding of the amyloidogenic human protein β2-microglobulin. The combination of real-time two-dimensional NMR data with real-time small-angle X-ray scattering measurements allowed us to derive thermodynamic and kinetic information on protein oligomerization of different conformational states populated along the folding pathways. In particular, we could demonstrate that a long-lived folding intermediate (I-state) has a higher propensity to oligomerize compared to the native state. Our data agree well with a simple five-state kinetic model that involves only monomeric and dimeric species. The dimers have an elongated shape with the dimerization interface located at the apical side of β2-microglobulin close to Pro32, the residue that has a trans conformation in the I-state and a cis conformation in the native (N) state. Our experimental data suggest that partial unfolding in the apical half of the protein close to Pro32 leads to an excited state conformation with enhanced propensity for oligomerization. This excited state becomes more populated in the transient I-state due to the destabilization of the native conformation by the trans-Pro32 configuration. AU - Rennella, E. AU - Cutuil, T. AU - Schanda, Paul AU - Ayala, I. AU - Gabel, F. AU - Forge, V. AU - Corazza, A. AU - Esposito, G. AU - Brutscher, B. ID - 8462 IS - 15 JF - Journal of Molecular Biology KW - Molecular Biology SN - 0022-2836 TI - Oligomeric states along the folding pathways of β2-microglobulin: Kinetics, thermodynamics, and structure VL - 425 ER - TY - JOUR AB - Understanding fitness landscapes, a conceptual depiction of the genotype-to-phenotype relationship, is crucial to many areas of biology. Two aspects of fitness landscapes are the focus of contemporary studies of molecular evolution. First, the local shape of the fitness landscape defined by the contribution of individual alleles to fitness that is independent of all genetic interactions. Second, the global, multidimensional fitness landscape shape determined by how interactions between alleles at different loci change each other’s fitness impact, or epistasis. In explaining the high amino-acid usage (u), we focused on the global shape of the fitness landscape, ignoring the perturbations at individual sites. AU - Breen, Michael S AU - Kemena, Carsten AU - Vlasov, Peter K AU - Notredame, Cédric AU - Fyodor Kondrashov ID - 899 IS - 7451 JF - Nature TI - Breen et al. reply VL - 497 ER - TY - JOUR AB - The coalescence of nano-crystals during sintering is often found to result in interesting crystalline structures such as multi-fold twins, and yet the plasticity mechanism accompanying their formation is unclear. In this work, the sintering behavior of two unsupported copper nanoparticles initially at room temperature is investigated by molecular dynamics simulations under the constant-energy ensemble. The results reveal that once the two nanoparticles are brought into contact, they often go through drastic structural changes with the inter-particle grain boundary quickly eliminated, and single- and multi-fold twinning occurs frequently in the coalesced product. Whereas the formation of single twins is found to be via the more usual mechanism of emission of Shockley partials on {1 1 1} planes, the formation of fivefold twins, however, takes place via a novel dislocation-free mechanism involving a series of shear and rigid-body rotation processes caused by elastic waves with amplitudes not corresponding to any allowable Burgers vector in the fcc lattice. Such a lattice-wave, dislocation-free twinning mechanism has never been reported before. AU - Cheng, Bingqing AU - Ngan, Alfonso H.W. ID - 9674 JF - International Journal of Plasticity SN - 0749-6419 TI - The crystal structures of sintered copper nanoparticles: A molecular dynamics study VL - 47 ER - TY - JOUR AB - Despite its relevance to a range of technological applications including nanocrystalline material fabrication, the sintering mechanisms of nanoparticles have not been well understood. It has been recognized that extrapolation from understanding of macro-particle sintering is unreliable for the nano-particle size regime. In this work, the sintering behaviour of copper nanoparticles under periodic boundary conditions at different temperatures and pressures was investigated by Molecular Dynamics simulations. It was found that smaller particle sizes, higher temperature and higher external pressure facilitate densification. Through a comparison with a two-sphere model, the governing mechanisms for many nanoparticles sintered at low temperature (T⩽900K) were identified to be a variety of plasticity processes including dislocation, twinning and even amorphization at the contact neck regions, due to the presence of high stresses. AU - Cheng, Bingqing AU - Ngan, Alfonso H.W. ID - 9676 JF - Computational Materials Science SN - 0927-0256 TI - The sintering and densification behaviour of many copper nanoparticles: A molecular dynamics study VL - 74 ER - TY - JOUR AB - We study the stability of the normal state in a mesoscopic NSN junction biased by a constant voltage V with respect to the formation of the superconducting order. Using the linearized time-dependent Ginzburg-Landau equation, we obtain the temperature dependence of the instability line, V inst(T), where nucleation of superconductivity takes place. For sufficiently low biases, a stationary symmetric superconducting state emerges below the instability line. For higher biases, the normal phase is destroyed by the formation of a nonstationary bimodal state with two superconducting nuclei localized near the opposite terminals. The low-temperature and large-voltage behavior of the instability line is highly sensitive to the details of the inelastic relaxation mechanism in the wire. Therefore, experimental studies of Vinst(T) in NSN junctions may be used as an effective tool to access the parameters of the inelastic relaxation in the normal state. AU - Maksym Serbyn AU - Skvortsov, Mikhail A ID - 971 IS - 2 JF - Physical Review B - Condensed Matter and Materials Physics TI - Onset of superconductivity in a voltage-biased normal-superconducting-normal microbridge VL - 87 ER - TY - JOUR AB - In topological crystalline insulators (TCIs), topology and crystal symmetry intertwine to create surface states with distinct characteristics. The breaking of crystal symmetry in TCIs is predicted to impart mass to the massless Dirac fermions. Here, we report high-resolution scanning tunneling microscopy studies of a TCI, Pb1-xSnxSe that reveal the coexistence of zero-mass Dirac fermions protected by crystal symmetry with massive Dirac fermions consistent with crystal symmetry breaking. In addition, we show two distinct regimes of the Fermi surface topology separated by a Van-Hove singularity at the Lifshitz transition point. Our work paves the way for engineering the Dirac band gap and realizing interaction-driven topological quantum phenomena in TCIs. AU - Okada, Yoshinori AU - Serbyn, Maksym AU - Lin, Hsin AU - Walkup, Daniel AU - Zhou, Wenwen AU - Dhital, Chetan AU - Neupane, Madhab AU - Xu, Suyang AU - Wang, Yungjui AU - Sankar, Raman AU - Chou, Fangcheng AU - Bansil, Arun AU - Hasan, Md AU - Wilson, Stephen AU - Fu, Liang AU - Madhavan, Vidya ID - 972 IS - 6153 JF - Science TI - Observation of dirac node formation and mass acquisition in a topological crystalline insulator VL - 341 ER - TY - JOUR AB - Recent numerical work by Bardarson, Pollmann, and Moore revealed a slow, logarithmic in time, growth of the entanglement entropy for initial product states in a putative many-body localized phase. We show that this surprising phenomenon results from the dephasing due to exponentially small interaction-induced corrections to the eigenenergies of different states. For weak interactions, we find that the entanglement entropy grows as ξln (Vt/), where V is the interaction strength, and ξ is the single-particle localization length. The saturated value of the entanglement entropy at long times is determined by the participation ratios of the initial state over the eigenstates of the subsystem. Our work shows that the logarithmic entanglement growth is a universal phenomenon characteristic of the many-body localized phase in any number of spatial dimensions, and reveals a broad hierarchy of dephasing time scales present in such a phase. AU - Maksym Serbyn AU - Papić, Zlatko AU - Abanin, Dmitry A ID - 975 IS - 26 JF - Physical Review Letters TI - Universal slow growth of entanglement in interacting strongly disordered systems VL - 110 ER - TY - GEN AB - Cooperative behavior, where one individual incurs a cost to help another, is a wide spread phenomenon. Here we study direct reciprocity in the context of the alternating Prisoner's Dilemma. We consider all strategies that can be implemented by one and two-state automata. We calculate the payoff matrix of all pairwise encounters in the presence of noise. We explore deterministic selection dynamics with and without mutation. Using different error rates and payoff values, we observe convergence to a small number of distinct equilibria. Two of them are uncooperative strict Nash equilibria representing always-defect (ALLD) and Grim. The third equilibrium is mixed and represents a cooperative alliance of several strategies, dominated by a strategy which we call Forgiver. Forgiver cooperates whenever the opponent has cooperated; it defects once when the opponent has defected, but subsequently Forgiver attempts to re-establish cooperation even if the opponent has defected again. Forgiver is not an evolutionarily stable strategy, but the alliance, which it rules, is asymptotically stable. For a wide range of parameter values the most commonly observed outcome is convergence to the mixed equilibrium, dominated by Forgiver. Our results show that although forgiving might incur a short-term loss it can lead to a long-term gain. Forgiveness facilitates stable cooperation in the presence of exploitation and noise. AU - Zagorsky, Benjamin AU - Reiter, Johannes AU - Chatterjee, Krishnendu AU - Nowak, Martin ID - 9749 TI - Forgiver triumphs in alternating prisoner's dilemma ER - TY - JOUR AB - We propose a two-step procedure for estimating multiple migration rates in an approximate Bayesian computation (ABC) framework, accounting for global nuisance parameters. The approach is not limited to migration, but generally of interest for inference problems with multiple parameters and a modular structure (e.g. independent sets of demes or loci). We condition on a known, but complex demographic model of a spatially subdivided population, motivated by the reintroduction of Alpine ibex (Capra ibex) into Switzerland. In the first step, the global parameters ancestral mutation rate and male mating skew have been estimated for the whole population in Aeschbacher et al. (Genetics 2012; 192: 1027). In the second step, we estimate in this study the migration rates independently for clusters of demes putatively connected by migration. For large clusters (many migration rates), ABC faces the problem of too many summary statistics. We therefore assess by simulation if estimation per pair of demes is a valid alternative. We find that the trade-off between reduced dimensionality for the pairwise estimation on the one hand and lower accuracy due to the assumption of pairwise independence on the other depends on the number of migration rates to be inferred: the accuracy of the pairwise approach increases with the number of parameters, relative to the joint estimation approach. To distinguish between low and zero migration, we perform ABC-type model comparison between a model with migration and one without. Applying the approach to microsatellite data from Alpine ibex, we find no evidence for substantial gene flow via migration, except for one pair of demes in one direction. AU - Aeschbacher, Simon AU - Futschik, Andreas AU - Beaumont, Mark ID - 2944 IS - 4 JF - Molecular Ecology TI - Approximate Bayesian computation for modular inference problems with many parameters: the example of migration rates. VL - 22 ER - TY - JOUR AB - Background: Genetic variation at the melanocortin-1 receptor (MC1R) gene is correlated with melanin color variation in many birds. Feral pigeons (Columba livia) show two major melanin-based colorations: a red coloration due to pheomelanic pigment and a black coloration due to eumelanic pigment. Furthermore, within each color type, feral pigeons display continuous variation in the amount of melanin pigment present in the feathers, with individuals varying from pure white to a full dark melanic color. Coloration is highly heritable and it has been suggested that it is under natural or sexual selection, or both. Our objective was to investigate whether MC1R allelic variants are associated with plumage color in feral pigeons. Findings. We sequenced 888 bp of the coding sequence of MC1R among pigeons varying both in the type, eumelanin or pheomelanin, and the amount of melanin in their feathers. We detected 10 non-synonymous substitutions and 2 synonymous substitution but none of them were associated with a plumage type. It remains possible that non-synonymous substitutions that influence coloration are present in the short MC1R fragment that we did not sequence but this seems unlikely because we analyzed the entire functionally important region of the gene. Conclusions: Our results show that color differences among feral pigeons are probably not attributable to amino acid variation at the MC1R locus. Therefore, variation in regulatory regions of MC1R or variation in other genes may be responsible for the color polymorphism of feral pigeons. AU - Derelle, Romain AU - Kondrashov, Fyodor AU - Arkhipov, Vladimir AU - Corbel, Hélène AU - Frantz, Adrien AU - Gasparini, Julien AU - Jacquin, Lisa AU - Jacob, Gwenaël AU - Thibault, Sophie AU - Baudry, Emmanuelle ID - 894 IS - 1 JF - BMC Research Notes TI - Color differences among feral pigeons (Columba livia) are not attributable to sequence variation in the coding region of the melanocortin-1 receptor gene MC1R VL - 6 ER - TY - JOUR AB - Spontaneous formation of colonies of bacteria or flocks of birds are examples of self-organization in active living matter. Here, we demonstrate a form of self-organization from nonequilibrium driving forces in a suspension of synthetic photoactivated colloidal particles. They lead to two-dimensional "living crystals," which form, break, explode, and re-form elsewhere. The dynamic assembly results from a competition between self-propulsion of particles and an attractive interaction induced respectively by osmotic and phoretic effects and activated by light. We measured a transition from normal to giant-number fluctuations. Our experiments are quantitatively described by simple numerical simulations. We show that the existence of the living crystals is intrinsically related to the out-of-equilibrium collisions of the self-propelled particles. AU - Palacci, Jérémie A AU - Sacanna, S. AU - Steinberg, A. P. AU - Pine, D. J. AU - Chaikin, P. M. ID - 9055 IS - 6122 JF - Science KW - Multidisciplinary SN - 0036-8075 TI - Living crystals of light-activated colloidal surfers VL - 339 ER - TY - JOUR AB - A survey of avifauna was carried out in the Mys Shmidta area, north Chukotka, Russia from 8 June to 12 July 2011. A total of 90 species was recorded in the area, which together with literature data made a final list of 104 species. For several species this area is beyond the northern, north-eastern or north-western limits of their known distribution. We collected new data for 19 globally or locally threatened species. Tundra Swan Cygnus columbianus, Emperor Goose Anser canagica, American Golden Plover Pluvialis dominica, Western Sandpiper Calidris mauri, Semipalmated Sandpiper C. pusilla, Northern House Martin Delichon urbica and Barn Swallow Hirundo rustica were all confirmed to be breeding. Breeding of Brent Goose Branta bernicla nigricans, Spectacled Eider Somateria fischeri and Steller's Eider Polysticta stelleri was judged to be 'very likely'. There was no evidence for breeding of Ross's Gull Rhodostethia rosea despite several records. Two Eurasian Dotterels Eudromias morinellus were recorded displaying for the first time in the area, but the status of the species is unclear. The area is important for Snowy Owl Nyctea scandiaca, and as moulting grounds for Emperor Goose. Canada Goose Branta canadensis, Baikal Teal Anas formosa, Bar-tailed Godwit Limosa lapponica, Slaty-backed Gull Larus schistisagus, Thayer's Gull L. thayeri, Black-headed Gull L. ridibundus, White-tailed Eagle Haliaeetus albicilla, Steller's Sea Eagle H. pelagicus, Osprey Pandion haliaetus, Arctic Warbler Phylloscopus borealis and House Sparrow Passer domesticus are more likely to be rare vagrants or migrants. An observation of a Pine Siskin Carduelis pinus is the first record for Eurasia. AU - Arkhipov, Vladimir Y AU - Noah T AU - Koschkar, Steffen AU - Fyodor Kondrashov ID - 905 IS - 29 JF - Forktail TI - Birds of Mys Shmidta, north Chukotka, Russia ER - TY - JOUR AB - Internal tide driven mixing plays a key role in sustaining the deep ocean stratification and meridional overturning circulation. Internal tides can be generated by topographic horizontal scales ranging from hundreds of meters to tens of kilometers. State of the art topographic products barely resolve scales smaller than ∼10 km in the deep ocean. On these scales abyssal hills dominate ocean floor roughness. The impact of abyssal hill roughness on internal‐tide generation is evaluated in this study. The conversion of M2 barotropic to baroclinic tidal energy is calculated based on linear wave theory both in real and spectral space using the Shuttle Radar Topography Mission SRTM30_PLUS bathymetric product at 1/120° resolution with and without the addition of synthetic abyssal hill roughness. Internal tide generation by abyssal hills integrates to 0.1 TW globally or 0.03 TW when the energy flux is empirically corrected for supercritical slope (i.e., ∼10% of the energy flux due to larger topographic scales resolved in standard products in both cases). The abyssal hill driven energy conversion is dominated by mid‐ocean ridges, where abyssal hill roughness is large. Focusing on two regions located over the Mid‐Atlantic Ridge and the East Pacific Rise, it is shown that regionally linear theory predicts an increase of the energy flux due to abyssal hills of up to 100% or 60% when an empirical correction for supercritical slopes is attempted. Therefore, abyssal hills, unresolved in state of the art topographic products, can have a strong impact on internal tide generation, especially over mid‐ocean ridges. AU - Melet, Angélique AU - Nikurashin, Maxim AU - Muller, Caroline J AU - Falahat, S. AU - Nycander, Jonas AU - Timko, Patrick G. AU - Arbic, Brian K. AU - Goff, John A. ID - 9153 IS - 11 JF - Journal of Geophysical Research: Oceans SN - 2169-9275 TI - Internal tide generation by abyssal hills using analytical theory VL - 118 ER - TY - JOUR AB - In this study the response of tropical precipitation extremes to warming in organized convection is examined using a cloud-resolving model. Vertical shear is imposed to organize the convection into squall lines. Earlier studies show that in disorganized convection, the fractional increase of precipitation extremes is similar to that of surface water vapor, which is substantially smaller than the increase in column water vapor. It has been suggested that organized convection could lead to stronger amplifications. Regardless of the strength of the shear, amplifications of precipitation extremes in the cloud-resolving simulations are comparable to those of surface water vapor and are substantially less than increases in column water vapor. The results without shear and with critical shear, for which the squall lines are perpendicular to the shear, are surprisingly similar with a fractional rate of increase of precipitation extremes slightly smaller than that of surface water vapor. Interestingly, the dependence on shear is nonmonotonic, and stronger supercritical shear yields larger rates, close to or slightly larger than surface humidity. A scaling is used to evaluate the thermodynamic and dynamic contributions to precipitation extreme changes. To first order, they are dominated by the thermodynamic component, which has the same magnitude for all shears, close to the change in surface water vapor. The dynamic contribution plays a secondary role and tends to weaken extremes without shear and with critical shear, while it strengthens extremes with supercritical shear. These different dynamic contributions for different shears are due to different responses of convective mass fluxes in individual updrafts to warming. AU - Muller, Caroline J ID - 9154 IS - 14 JF - Journal of Climate KW - Atmospheric Science SN - 0894-8755 TI - Impact of convective organization on the response of tropical precipitation extremes to warming VL - 26 ER - TY - JOUR AB - We introduce a self-propelled colloidal hematite docker that can be steered to a small particle cargo many times its size, dock, transport the cargo to a remote location, and then release it. The self-propulsion and docking are reversible and activated by visible light. The docker can be steered either by a weak uniform magnetic field or by nanoscale tracks in a textured substrate. The light-activated motion and docking originate from osmotic/phoretic particle transport in a concentration gradient of fuel, hydrogen peroxide, induced by the photocatalytic activity of the hematite. The docking mechanism is versatile and can be applied to various materials and shapes. The hematite dockers are simple single-component particles and are synthesized in bulk quantities. This system opens up new possibilities for designing complex micrometer-size factories as well as new biomimetic systems. AU - Palacci, Jérémie A AU - Sacanna, Stefano AU - Vatchinsky, Adrian AU - Chaikin, Paul M. AU - Pine, David J. ID - 9167 IS - 43 JF - Journal of the American Chemical Society KW - Colloid and Surface Chemistry KW - Biochemistry KW - General Chemistry KW - Catalysis SN - 00027863 TI - Photoactivated colloidal dockers for cargo transportation VL - 135 ER - TY - JOUR AB - Recent experiments have shown that spreading epithelial sheets exhibit a long-range coordination of motility forces that leads to a buildup of tension in the tissue, which may enhance cell division and the speed of wound healing. Furthermore, the edges of these epithelial sheets commonly show finger-like protrusions whereas the bulk often displays spontaneous swirls of motile cells. To explain these experimental observations, we propose a simple flocking-type mechanism, in which cells tend to align their motility forceswith their velocity. Implementing this idea in amechanical tissue simulation, the proposed model gives rise to efficient spreading and can explain the experimentally observed long-range alignment of motility forces in highly disordered patterns, as well as the buildup of tensile stress throughout the tissue. Our model also qualitatively reproduces the dependence of swirl size and swirl velocity on cell density reported in experiments and exhibits an undulation instability at the edge of the spreading tissue commonly observed in vivo. Finally, we study the dependence of colony spreading speed on important physical and biological parameters and derive simple scaling relations that show that coordination of motility forces leads to an improvement of the wound healing process for realistic tissue parameters. AU - Basan, Markus AU - Elgeti, Jens AU - Hannezo, Edouard B AU - Rappel, Wouter AU - Levine, Herbert ID - 921 IS - 7 JF - PNAS TI - Alignment of cellular motility forces with tissue flow as a mechanism for efficient wound healing VL - 110 ER - TY - JOUR AB - Nucleosome remodelers of the DDM1/Lsh family are required for DNA methylation of transposable elements, but the reason for this is unknown. How DDM1 interacts with other methylation pathways, such as small-RNA-directed DNA methylation (RdDM), which is thought to mediate plant asymmetric methylation through DRM enzymes, is also unclear. Here, we show that most asymmetric methylation is facilitated by DDM1 and mediated by the methyltransferase CMT2 separately from RdDM. We find that heterochromatic sequences preferentially require DDM1 for DNA methylation and that this preference depends on linker histone H1. RdDM is instead inhibited by heterochromatin and absolutely requires the nucleosome remodeler DRD1. Together, DDM1 and RdDM mediate nearly all transposon methylation and collaborate to repress transposition and regulate the methylation and expression of genes. Our results indicate that DDM1 provides DNA methyltransferases access to H1-containing heterochromatin to allow stable silencing of transposable elements in cooperation with the RdDM pathway. AU - Zemach, Assaf AU - Kim, M. Yvonne AU - Hsieh, Ping-Hung AU - Coleman-Derr, Devin AU - Eshed-Williams, Leor AU - Thao, Ka AU - Harmer, Stacey L. AU - Zilberman, Daniel ID - 9459 IS - 1 JF - Cell SN - 0092-8674 TI - The Arabidopsis nucleosome remodeler DDM1 allows DNA methyltransferases to access H1-containing heterochromatin VL - 153 ER - TY - JOUR AB - Arabidopsis thaliana endosperm, a transient tissue that nourishes the embryo, exhibits extensive localized DNA demethylation on maternally inherited chromosomes. Demethylation mediates parent-of-origin–specific (imprinted) gene expression but is apparently unnecessary for the extensive accumulation of maternally biased small RNA (sRNA) molecules detected in seeds. Endosperm DNA in the distantly related monocots rice and maize is likewise locally hypomethylated, but whether this hypomethylation is generally parent-of-origin specific is unknown. Imprinted expression of sRNA also remains uninvestigated in monocot seeds. Here, we report high-coverage sequencing of the Kitaake rice cultivar that enabled us to show that localized hypomethylation in rice endosperm occurs solely on the maternal genome, preferring regions of high DNA accessibility. Maternally expressed imprinted genes are enriched for hypomethylation at putative promoter regions and transcriptional termini and paternally expressed genes at promoters and gene bodies, mirroring our recent results in A. thaliana. However, unlike in A. thaliana, rice endosperm sRNA populations are dominated by specific strong sRNA-producing loci, and imprinted 24-nt sRNAs are expressed from both parental genomes and correlate with hypomethylation. Overlaps between imprinted sRNA loci and imprinted genes expressed from opposite alleles suggest that sRNAs may regulate genomic imprinting. Whereas sRNAs in seedling tissues primarily originate from small class II (cut-and-paste) transposable elements, those in endosperm are more uniformly derived, including sequences from other transposon classes, as well as genic and intergenic regions. Our data indicate that the endosperm exhibits a unique pattern of sRNA expression and suggest that localized hypomethylation of maternal endosperm DNA is conserved in flowering plants. AU - Rodrigues, Jessica A. AU - Ruan, Randy AU - Nishimura, Toshiro AU - Sharma, Manoj K. AU - Sharma, Rita AU - Ronald, Pamela C AU - Fischer, Robert L. AU - Zilberman, Daniel ID - 9481 IS - 19 JF - Proceedings of the National Academy of Sciences KW - Multidisciplinary SN - 0027-8424 TI - Imprinted expression of genes and small RNA is associated with localized hypomethylation of the maternal genome in rice endosperm VL - 110 ER - TY - JOUR AB - Molecular dynamics simulations of small Cu nanoparticles using three different interatomic potentials at rising temperature indicate that small nanoparticles can undergo solid-solid structural transitions through a direct geometrical conversion route. The direct geometrical conversion can happen for cuboctahedral nanoparticles, which turn into an icosahedra shape: one diagonal of the square faces contracts, and the faces are folded along the diagonal to give rise to two equilateral triangles. The transition is a kinetic process that cannot be fully explained through an energetic point of view. It has low activation energy and fast reaction time in the simulations. The transition mechanism is via the transmission of shear waves initiated from the particle surface and does not involve dislocation activity. AU - Cheng, Bingqing AU - Ngan, Alfonso H. W. ID - 9663 IS - 16 JF - The Journal of Chemical Physics SN - 0021-9606 TI - Thermally induced solid-solid structural transition of copper nanoparticles through direct geometrical conversion VL - 138 ER - TY - JOUR AB - In this work, we simulate the response of two Cu nanoparticles colliding at different approaching rates at room temperature by MD. For small nanospheres, the formation of single twins is favored at high approach rates, whereas larger nanospheres mainly deform by dislocation slip. For small nanocubes with large {100} flat surfaces, however, a dislocation-free direct geometrical conversion process that leads to five-fold twinning dominates except at highly retarded approaching rates. For larger nanocubes, single twin formation is the governing plasticity mechanism. The probability for plastic deformation by dislocation slip or twinning is attributed to the abundance of surface steps, which act as sites for dislocation nucleation. AU - Cheng, Bingqing AU - Ngan, Alfonso H.W. ID - 9682 JF - Materials Science and Engineering: A SN - 0921-5093 TI - Crystal plasticity of Cu nanocrystals during collision VL - 585 ER - TY - JOUR AB - Recently a new high-mobility Dirac material, trilayer graphene, was realized experimentally. The band structure of ABA-stacked trilayer graphene consists of a monolayer-like and a bilayer-like pair of bands. Here we study electronic properties of ABA-stacked trilayer graphene biased by a perpendicular electric field. We find that the combination of the bias and trigonal warping gives rise to a set of new Dirac points: In each valley, seven species of Dirac fermions with small masses of order of a few meV emerge. The positions and masses of the emergent Dirac fermions are tunable by bias, and one group of Dirac fermions becomes massless at a certain bias value. Therefore, in contrast to bilayer graphene, the conductivity at the neutrality point is expected to show nonmonotonic behavior, becoming of the order of a few e2/h when some Dirac masses vanish. Further, we analyze the evolution of the Landau level spectrum as a function of bias. The emergence of new Dirac points in the band structure translates into new threefold-degenerate groups of Landau levels. This leads to an anomalous quantum Hall effect, in which some quantum Hall steps have a height of 3e2/h. At an intermediate bias, the degeneracies of all Landau levels get lifted, and in this regime all quantum Hall plateaus are spaced by e2/h. Finally, we show that the pattern of Landau level crossings is very sensitive to certain band structure parameters, and can therefore provide a useful tool for determining their precise values. AU - Maksym Serbyn AU - Abanin, Dmitry A ID - 970 IS - 11 JF - Physical Review B - Condensed Matter and Materials Physics TI - New Dirac points and multiple Landau level crossings in biased trilayer graphene VL - 87 ER - TY - JOUR AB - We construct a complete set of local integrals of motion that characterize the many-body localized (MBL) phase. Our approach relies on the assumption that local perturbations act locally on the eigenstates in the MBL phase, which is supported by numerical simulations of the random-field XXZ spin chain. We describe the structure of the eigenstates in the MBL phase and discuss the implications of local conservation laws for its nonequilibrium quantum dynamics. We argue that the many-body localization can be used to protect coherence in the system by suppressing relaxation between eigenstates with different local integrals of motion. AU - Maksym Serbyn AU - Papić, Zlatko AU - Abanin, Dmitry A ID - 973 IS - 12 JF - Physical Review Letters TI - Local conservation laws and the structure of the many body localized states VL - 111 ER - TY - JOUR AB - We propose a possible realization of the overscreened Kondo impurity problem by a magnetic s=1/2 impurity embedded in a two-dimensional S=1 U(1) spin liquid with a Fermi surface. This problem contains an interesting interplay between non-Fermi-liquid behavior induced by a U(1) gauge field coupled to fermions and a non-Fermi-liquid fixed point in the overscreened Kondo problem. Using a large-N expansion together with an expansion in the dynamical exponent of the gauge field, we find that the coupling to the gauge field leads to weak but observable changes in the physical properties of the system at the overscreened Kondo fixed point. We discuss the extrapolation of this result to a physical case and argue that the realization of overscreened Kondo physics could lead to observations of effects due to gauge fields. AU - Serbyn, Maksym AU - Senthil, Todadri AU - Lee, Patrick ID - 974 IS - 2 JF - Physical Review B - Condensed Matter and Materials Physics TI - Overscreened Kondo fixed point in S=1 spin liquid VL - 88 ER - TY - JOUR AB - Background: The brood of ants and other social insects is highly susceptible to pathogens, particularly those that penetrate the soft larval and pupal cuticle. We here test whether the presence of a pupal cocoon, which occurs in some ant species but not in others, affects the sanitary brood care and fungal infection patterns after exposure to the entomopathogenic fungus Metarhizium brunneum. We use a) a comparative approach analysing four species with either naked or cocooned pupae and b) a within-species analysis of a single ant species, in which both pupal types co-exist in the same colony. Results: We found that the presence of a cocoon did not compromise fungal pathogen detection by the ants and that species with cocooned pupae increased brood grooming after pathogen exposure. All tested ant species further removed brood from their nests, which was predominantly expressed towards larvae and naked pupae treated with the live fungal pathogen. In contrast, cocooned pupae exposed to live fungus were not removed at higher rates than cocooned pupae exposed to dead fungus or a sham control. Consistent with this, exposure to the live fungus caused high numbers of infections and fungal outgrowth in larvae and naked pupae, but not in cocooned pupae. Moreover, the ants consistently removed the brood prior to fungal outgrowth, ensuring a clean brood chamber. Conclusion: Our study suggests that the pupal cocoon has a protective effect against fungal infection, causing an adaptive change in sanitary behaviours by the ants. It further demonstrates that brood removal-originally described for honeybees as "hygienic behaviour"-is a widespread sanitary behaviour in ants, which likely has important implications on disease dynamics in social insect colonies. AU - Tragust, Simon AU - Ugelvig, Line V AU - Chapuisat, Michel AU - Heinze, Jürgen AU - Cremer, Sylvia ID - 2284 IS - 1 JF - BMC Evolutionary Biology TI - Pupal cocoons affect sanitary brood care and limit fungal infections in ant colonies VL - 13 ER - TY - JOUR AB - Redundancies and correlations in the responses of sensory neurons may seem to waste neural resources, but they can also carry cues about structured stimuli and may help the brain to correct for response errors. To investigate the effect of stimulus structure on redundancy in retina, we measured simultaneous responses from populations of retinal ganglion cells presented with natural and artificial stimuli that varied greatly in correlation structure; these stimuli and recordings are publicly available online. Responding to spatio-temporally structured stimuli such as natural movies, pairs of ganglion cells were modestly more correlated than in response to white noise checkerboards, but they were much less correlated than predicted by a non-adapting functional model of retinal response. Meanwhile, responding to stimuli with purely spatial correlations, pairs of ganglion cells showed increased correlations consistent with a static, non-adapting receptive field and nonlinearity. We found that in response to spatio-temporally correlated stimuli, ganglion cells had faster temporal kernels and tended to have stronger surrounds. These properties of individual cells, along with gain changes that opposed changes in effective contrast at the ganglion cell input, largely explained the pattern of pairwise correlations across stimuli where receptive field measurements were possible. AU - Simmons, Kristina AU - Prentice, Jason AU - Tkacik, Gasper AU - Homann, Jan AU - Yee, Heather AU - Palmer, Stephanie AU - Nelson, Philip AU - Balasubramanian, Vijay ID - 2277 IS - 12 JF - PLoS Computational Biology TI - Transformation of stimulus correlations by the retina VL - 9 ER - TY - GEN AB - Short-read sequencing technologies have in principle made it feasible to draw detailed inferences about the recent history of any organism. In practice, however, this remains challenging due to the difficulty of genome assembly in most organisms and the lack of statistical methods powerful enough to discriminate among recent, non-equilibrium histories. We address both the assembly and inference challenges. We develop a bioinformatic pipeline for generating outgroup-rooted alignments of orthologous sequence blocks from de novo low-coverage short-read data for a small number of genomes, and show how such sequence blocks can be used to fit explicit models of population divergence and admixture in a likelihood framework. To illustrate our approach, we reconstruct the Pleistocene history of an oak-feeding insect (the oak gallwasp Biorhiza pallida) which, in common with many other taxa, was restricted during Pleistocene ice ages to a longitudinal series of southern refugia spanning theWestern Palaearctic. Our analysis of sequence blocks sampled from a single genome from each of three major glacial refugia reveals support for an unexpected history dominated by recent admixture. Despite the fact that 80% of the genome is affected by admixture during the last glacial cycle, we are able to infer the deeper divergence history of these populations. These inferences are robust to variation in block length, mutation model, and the sampling location of individual genomes within refugia. This combination of de novo assembly and numerical likelihood calculation provides a powerful framework for estimating recent population history that can be applied to any organism without the need for prior genetic resources. AU - Hearn, Jack AU - Stone, Graham AU - Barton, Nicholas H AU - Lohse, Konrad AU - Bunnefeld, Lynsey ID - 9754 TI - Data from: Likelihood-based inference of population history from low coverage de novo genome assemblies ER - TY - JOUR AB - Motivated by a search for experimental probes to access the physics of fractionalized excitations called spinons in spin liquids, we study the interaction of spinons with lattice vibrations. We consider the case of algebraic spin liquid, when spinons have fermionic statistics and a Dirac-like dispersion. We establish the general procedure for deriving spinon-phonon interactions, which is based on symmetry considerations. The procedure is illustrated for four different algebraic spin liquids: π-flux and staggered-flux phases on a square lattice, π-flux phase on a kagome lattice, and zero-flux phase on a honeycomb lattice. Although the low-energy description is similar for all these phases, different underlying symmetry groups lead to a distinct form of spinon-phonon interaction Hamiltonian. The explicit form of the spinon-phonon interaction is used to estimate the attenuation of ultrasound in an algebraic spin liquid. The prospects of the sound attenuation as a probe of spinons are discussed. AU - Maksym Serbyn AU - Lee, Patrick ID - 976 IS - 17 JF - Physical Review B - Condensed Matter and Materials Physics TI - Spinon-phonon interaction in algebraic spin liquids VL - 87 ER - TY - JOUR AB - Central Asian water resources largely depend on melt water generated in the Pamir and Tien Shan mountain ranges. To estimate future water availability in this region, it is necessary to use climate projections to estimate the future glacier extent and volume. In this study, we evaluate the impact of uncertainty in climate change projections on the future glacier extent in the Amu and Syr Darya river basins. To this end we use the latest climate change projections generated for the upcoming IPCC report (CMIP5) and, for comparison, projections used in the fourth IPCC assessment (CMIP3). With these projections we force a regionalized glacier mass balance model, and estimate changes in the basins' glacier extent as a function of the glacier size distribution in the basins and projected temperature and precipitation. This glacier mass balance model is specifically developed for implementation in large scale hydrological models, where the spatial resolution does not allow for simulating individual glaciers and data scarcity is an issue. Although the CMIP5 ensemble results in greater regional warming than the CMIP3 ensemble and the range in projections for temperature as well as precipitation is wider for the CMIP5 than for the CMIP3, the spread in projections of future glacier extent in Central Asia is similar for both ensembles. This is because differences in temperature rise are small during periods of maximum melt (July–September) while differences in precipitation change are small during the period of maximum accumulation (October–February). However, the model uncertainty due to parameter uncertainty is high, and has roughly the same importance as uncertainty in the climate projections. Uncertainty about the size of the decline in glacier extent remains large, making estimates of future Central Asian glacier evolution and downstream water availability uncertain. AU - Lutz, A. F. AU - Immerzeel, W. W. AU - Gobiet, A. AU - Pellicciotti, Francesca AU - Bierkens, M. F. P. ID - 12638 IS - 9 JF - Hydrology and Earth System Sciences KW - General Earth and Planetary Sciences KW - General Engineering KW - General Environmental Science SN - 1607-7938 TI - Comparison of climate change signals in CMIP3 and CMIP5 multi-model ensembles and implications for Central Asian glaciers VL - 17 ER - TY - JOUR AB - In the headwater catchments of the main Asian rivers, glaciohydrological models are a useful tool to anticipate impacts of climatic changes. However, the reliability of their projections strongly depends on the quality and quantity of data that are available for parameter estimation, model calibration and validation, as well as on the accuracy of climate change projections. In this study the physically oriented, glaciohydrological model TOPKAPI-ETH is used to simulate future changes in snow, glacier, and runoff from the Hunza River Basin in northern Pakistan. Three key sources of model uncertainty in future runoff projections are compared: model parameters, climate projections, and natural climate variability. A novel approach, applicable also to ungauged catchments, is used to determine which model parameters and model components significantly affect the overall model uncertainty. We show that the model is capable of reproducing streamflow and glacier mass balances, but that all analyzed sources of uncertainty significantly affect the reliability of future projections, and that their effect is variable in time and in space. The effect of parametric uncertainty often exceeds the impact of climate uncertainty and natural climate variability, especially in heavily glacierized subcatchments. The results of the uncertainty analysis allow detailed recommendations on network design and the timing and location of field measurements, which could efficiently help to reduce model uncertainty in the future. AU - Ragettli, S. AU - Pellicciotti, Francesca AU - Bordoy, R. AU - Immerzeel, W. W. ID - 12639 IS - 9 JF - Water Resources Research KW - Water Science and Technology SN - 0043-1397 TI - Sources of uncertainty in modeling the glaciohydrological response of a Karakoram watershed to climate change VL - 49 ER - TY - JOUR AB - We use two hydrological models of varying complexity to study the Juncal River Basin in the Central Andes of Chile with the aim to understand the degree of conceptualization and the spatial structure that are needed to model present and future streamflows. We use a conceptual semi-distributed model based on elevation bands [Water Evaluation and Planning (WEAP)], frequently used for water management, and a physically oriented, fully distributed model [Topographic Kinematic Wave Approximation and Integration ETH Zurich (TOPKAPI-ETH)] developed for research purposes mainly. We evaluate the ability of the two models to reproduce the key hydrological processes in the basin with emphasis on snow accumulation and melt, streamflow and the relationships between internal processes. Both models are capable of reproducing observed runoff and the evolution of Moderate-resolution Imaging Spectroradiometer snow cover adequately. In spite of WEAP's simple and conceptual approach for modelling snowmelt and its lack of glacier representation and snow gravitational redistribution as well as a proper routing algorithm, this model can reproduce historical data with a similar goodness of fit as the more complex TOPKAPI-ETH. We show that the performance of both models can be improved by using measured precipitation gradients of higher temporal resolution. In contrast to the good performance of the conceptual model for the present climate, however, we demonstrate that the simplifications in WEAP lead to error compensation, which results in different predictions in simulated melt and runoff for a potentially warmer future climate. TOPKAPI-ETH, using a more physical representation of processes, depends less on calibration and thus is less subject to a compensation of errors through different model components. Our results show that data obtained locally in ad hoc short-term field campaigns are needed to complement data extrapolated from long-term records for simulating changes in the water cycle of high-elevation catchments but that these data can only be efficiently used by a model applying a spatially distributed physical representation of hydrological processes. AU - Ragettli, S. AU - Cortés, G. AU - McPhee, J. AU - Pellicciotti, Francesca ID - 12633 IS - 23 JF - Hydrological Processes KW - Water Science and Technology SN - 0885-6087 TI - An evaluation of approaches for modelling hydrological processes in high-elevation, glacierized Andean watersheds VL - 28 ER - TY - JOUR AB - Plants undergo alternation of generation in which reproductive cells develop in the plant body ("sporophytic generation") and then differentiate into a multicellular gamete-forming "gametophytic generation." Different populations of helper cells assist in this transgenerational journey, with somatic tissues supporting early development and single nurse cells supporting gametogenesis. New data reveal a two-way relationship between early reproductive cells and their helpers involving complex epigenetic and signaling networks determining cell number and fate. Later, the egg cell plays a central role in specifying accessory cells, whereas in both gametophytes, companion cells contribute non-cell-autonomously to the epigenetic landscape of the gamete genomes. AU - Feng, Xiaoqi AU - Zilberman, Daniel AU - Dickinson, Hugh ID - 9520 IS - 3 JF - Developmental Cell SN - 1534-5807 TI - A conversation across generations: Soma-germ cell crosstalk in plants VL - 24 ER - TY - JOUR AB - We report a method for preparing electrode–molecule–electrode junctions that incorporate nonsymmetrical azobenzene dithiols. Our approach is based on sequential deprotection of thiol moieties originally carrying two different protecting groups. The azobenzene derivatives retained their switching properties within monolayers and permitted the photocontrol of electrical conductance. AU - Ely, Tal AU - Das, Sanjib AU - Li, Wenjie AU - Kundu, Pintu AU - Tirosh, Einat AU - Cahen, David AU - Vilan, Ayelet AU - Klajn, Rafal ID - 13405 IS - 18 JF - Synlett KW - Organic Chemistry SN - 0936-5214 TI - Photocontrol of electrical conductance with a nonsymmetrical azobenzene dithiol VL - 24 ER - TY - JOUR AB - Dual-responsive nanoparticles are designed by functionalizing magnetic cores with light-responsive ligands. These materials respond to both light and magnetic fields and can be assembled into various higher-order structures, depending on the relative contributions of these two stimuli. AU - Das, Sanjib AU - Ranjan, Priyadarshi AU - Maiti, Pradipta Sankar AU - Singh, Gurvinder AU - Leitus, Gregory AU - Klajn, Rafal ID - 13406 IS - 3 JF - Advanced Materials KW - Mechanical Engineering KW - Mechanics of Materials KW - General Materials Science SN - 0935-9648 TI - Dual-responsive nanoparticles and their self-assembly VL - 25 ER - TY - JOUR AB - The scale invariance of natural images suggests an analogy to the statistical mechanics of physical systems at a critical point. Here we examine the distribution of pixels in small image patches and show how to construct the corresponding thermodynamics. We find evidence for criticality in a diverging specific heat, which corresponds to large fluctuations in how "surprising" we find individual images, and in the quantitative form of the entropy vs energy. We identify special image configurations as local energy minima and show that average patches within each basin are interpretable as lines and edges in all orientations. AU - Stephens, Greg AU - Mora, Thierry AU - Tkacik, Gasper AU - Bialek, William ID - 2914 IS - 1 JF - Physical Review Letters TI - Statistical thermodynamics of natural images VL - 110 ER - TY - CHAP AB - Leukocyte migration through the interstitial space is crucial for the maintenance of tolerance and immunity. The main cues for leukocyte trafficking are chemokines thought to directionally guide these cells towards their targets. However, model systems that facilitate quantification of chemokine-guided leukocyte migration in vivo are uncommon. Here we describe an ex vivo crawl-in assay using explanted mouse ears that allows the visualization of chemokine-dependent dendritic cell (DC) motility in the dermal interstitium in real time. We present methods for the preparation of mouse ear sheets and their use in multidimensional confocal imaging experiments to monitor and analyze the directional migration of fluorescently labelled DCs through the dermis and into afferent lymphatic vessels. The assay provides a more physiological approach to study leukocyte migration than in vitro three-dimensional (3D) or 2-dimensional (2D) migration assays such as collagen gels and transwell assays. AU - Weber, Michele AU - Sixt, Michael K ED - Cardona, Astrid ED - Ubogu, Eroboghene ID - 10900 SN - 1064-3745 T2 - Chemokines TI - Live Cell Imaging of Chemotactic Dendritic Cell Migration in Explanted Mouse Ear Preparations VL - 1013 ER - TY - CHAP AU - Dragoi, Cezara AU - Gupta, Ashutosh AU - Henzinger, Thomas A ID - 5747 SN - 0302-9743 T2 - Computer Aided Verification TI - Automatic Linearizability Proofs of Concurrent Objects with Cooperating Updates VL - 8044 ER - TY - CONF AB - We consider how to edit strings from a source language so that the edited strings belong to a target language, where the languages are given as deterministic finite automata. Non-streaming (or offline) transducers perform edits given the whole source string. We show that the class of deterministic one-pass transducers with registers along with increment and min operation suffices for computing optimal edit distance, whereas the same class of transducers without the min operation is not sufficient. Streaming (or online) transducers perform edits as the letters of the source string are received. We present a polynomial time algorithm for the partial-repair problem that given a bound α asks for the construction of a deterministic streaming transducer (if one exists) that ensures that the ‘maximum fraction’ η of the strings of the source language are edited, within cost α, to the target language. AU - Chatterjee, Krishnendu AU - Chaubal, Siddhesh AU - Rubin, Sasha ID - 10902 SN - 0302-9743 T2 - 7th International Conference on Language and Automata Theory and Applications TI - How to travel between languages VL - 7810 ER - TY - CONF AB - Taking images is an efficient way to collect data about the physical world. It can be done fast and in exquisite detail. By definition, image processing is the field that concerns itself with the computation aimed at harnessing the information contained in images [10]. This talk is concerned with topological information. Our main thesis is that persistent homology [5] is a useful method to quantify and summarize topological information, building a bridge that connects algebraic topology with applications. We provide supporting evidence for this thesis by touching upon four technical developments in the overlap between persistent homology and image processing. AU - Edelsbrunner, Herbert ID - 10897 SN - 0302-9743 T2 - Graph-Based Representations in Pattern Recognition TI - Persistent homology in image processing VL - 7877 ER - TY - THES AB - Motivated by the analysis of highly dynamic message-passing systems, i.e. unbounded thread creation, mobility, etc. we present a framework for the analysis of depth-bounded systems. Depth-bounded systems are one of the most expressive known fragment of the π-calculus for which interesting verification problems are still decidable. Even though they are infinite state systems depth-bounded systems are well-structured, thus can be analyzed algorithmically. We give an interpretation of depth-bounded systems as graph-rewriting systems. This gives more flexibility and ease of use to apply depth-bounded systems to other type of systems like shared memory concurrency. First, we develop an adequate domain of limits for depth-bounded systems, a prerequisite for the effective representation of downward-closed sets. Downward-closed sets are needed by forward saturation-based algorithms to represent potentially infinite sets of states. Then, we present an abstract interpretation framework to compute the covering set of well-structured transition systems. Because, in general, the covering set is not computable, our abstraction over-approximates the actual covering set. Our abstraction captures the essence of acceleration based-algorithms while giving up enough precision to ensure convergence. We have implemented the analysis in the PICASSO tool and show that it is accurate in practice. Finally, we build some further analyses like termination using the covering set as starting point. AU - Zufferey, Damien ID - 1405 SN - 2663-337X TI - Analysis of dynamic message passing programs ER - TY - CONF AB - Depth-Bounded Systems form an expressive class of well-structured transition systems. They can model a wide range of concurrent infinite-state systems including those with dynamic thread creation, dynamically changing communication topology, and complex shared heap structures. We present the first method to automatically prove fair termination of depth-bounded systems. Our method uses a numerical abstraction of the system, which we obtain by systematically augmenting an over-approximation of the system’s reachable states with a finite set of counters. This numerical abstraction can be analyzed with existing termination provers. What makes our approach unique is the way in which it exploits the well-structuredness of the analyzed system. We have implemented our work in a prototype tool and used it to automatically prove liveness properties of complex concurrent systems, including nonblocking algorithms such as Treiber’s stack and several distributed processes. Many of these examples are beyond the scope of termination analyses that are based on traditional counter abstractions. AU - Bansal, Kshitij AU - Koskinen, Eric AU - Wies, Thomas AU - Zufferey, Damien ED - Piterman, Nir ED - Smolka, Scott ID - 2847 TI - Structural Counter Abstraction VL - 7795 ER - TY - THES AB - Epithelial spreading is a critical part of various developmental and wound repair processes. Here we use zebrafish epiboly as a model system to study the cellular and molecular mechanisms underlying the spreading of epithelial sheets. During zebrafish epiboly the enveloping cell layer (EVL), a simple squamous epithelium, spreads over the embryo to eventually cover the entire yolk cell by the end of gastrulation. The EVL leading edge is anchored through tight junctions to the yolk syncytial layer (YSL), where directly adjacent to the EVL margin a contractile actomyosin ring is formed that is thought to drive EVL epiboly. The prevalent view in the field was that the contractile ring exerts a pulling force on the EVL margin, which pulls the EVL towards the vegetal pole. However, how this force is generated and how it affects EVL morphology still remains elusive. Moreover, the cellular mechanisms mediating the increase in EVL surface area, while maintaining tissue integrity and function are still unclear. Here we show that the YSL actomyosin ring pulls on the EVL margin by two distinct force-generating mechanisms. One mechanism is based on contraction of the ring around its circumference, as previously proposed. The second mechanism is based on actomyosin retrogade flows, generating force through resistance against the substrate. The latter can function at any epiboly stage even in situations where the contraction-based mechanism is unproductive. Additionally, we demonstrate that during epiboly the EVL is subjected to anisotropic tension, which guides the orientation of EVL cell division along the main axis (animal-vegetal) of tension. The influence of tension in cell division orientation involves cell elongation and requires myosin-2 activity for proper spindle alignment. Strikingly, we reveal that tension-oriented cell divisions release anisotropic tension within the EVL and that in the absence of such divisions, EVL cells undergo ectopic fusions. We conclude that forces applied to the EVL by the action of the YSL actomyosin ring generate a tension anisotropy in the EVL that orients cell divisions, which in turn limit tissue tension increase thereby facilitating tissue spreading. AU - Campinho, Pedro ID - 1406 SN - 2663-337X TI - Mechanics of zebrafish epiboly: Tension-oriented cell divisions limit anisotropic tissue tension in epithelial spreading ER - TY - JOUR AB - Cooperative behavior, where one individual incurs a cost to help another, is a wide spread phenomenon. Here we study direct reciprocity in the context of the alternating Prisoner's Dilemma. We consider all strategies that can be implemented by one and two-state automata. We calculate the payoff matrix of all pairwise encounters in the presence of noise. We explore deterministic selection dynamics with and without mutation. Using different error rates and payoff values, we observe convergence to a small number of distinct equilibria. Two of them are uncooperative strict Nash equilibria representing always-defect (ALLD) and Grim. The third equilibrium is mixed and represents a cooperative alliance of several strategies, dominated by a strategy which we call Forgiver. Forgiver cooperates whenever the opponent has cooperated; it defects once when the opponent has defected, but subsequently Forgiver attempts to re-establish cooperation even if the opponent has defected again. Forgiver is not an evolutionarily stable strategy, but the alliance, which it rules, is asymptotically stable. For a wide range of parameter values the most commonly observed outcome is convergence to the mixed equilibrium, dominated by Forgiver. Our results show that although forgiving might incur a short-term loss it can lead to a long-term gain. Forgiveness facilitates stable cooperation in the presence of exploitation and noise. AU - Zagorsky, Benjamin AU - Reiter, Johannes AU - Chatterjee, Krishnendu AU - Nowak, Martin ID - 2247 IS - 12 JF - PLoS One TI - Forgiver triumphs in alternating prisoner's dilemma VL - 8 ER - TY - JOUR AB - Tumor growth is caused by the acquisition of driver mutations, which enhance the net reproductive rate of cells. Driver mutations may increase cell division, reduce cell death, or allow cells to overcome density-limiting effects. We study the dynamics of tumor growth as one additional driver mutation is acquired. Our models are based on two-type branching processes that terminate in either tumor disappearance or tumor detection. In our first model, both cell types grow exponentially, with a faster rate for cells carrying the additional driver. We find that the additional driver mutation does not affect the survival probability of the lesion, but can substantially reduce the time to reach the detectable size if the lesion is slow growing. In our second model, cells lacking the additional driver cannot exceed a fixed carrying capacity, due to density limitations. In this case, the time to detection depends strongly on this carrying capacity. Our model provides a quantitative framework for studying tumor dynamics during different stages of progression. We observe that early, small lesions need additional drivers, while late stage metastases are only marginally affected by them. These results help to explain why additional driver mutations are typically not detected in fast-growing metastases. AU - Reiter, Johannes AU - Božić, Ivana AU - Allen, Benjamin AU - Chatterjee, Krishnendu AU - Nowak, Martin ID - 2858 IS - 1 JF - Evolutionary Applications TI - The effect of one additional driver mutation on tumor progression VL - 6 ER - TY - JOUR AB - In solid tumors, targeted treatments can lead to dramatic regressions, but responses are often short-lived because resistant cancer cells arise. The major strategy proposed for overcoming resistance is combination therapy. We present a mathematical model describing the evolutionary dynamics of lesions in response to treatment. We first studied 20 melanoma patients receiving vemurafenib. We then applied our model to an independent set of pancreatic, colorectal, and melanoma cancer patients with metastatic disease. We find that dual therapy results in long-term disease control for most patients, if there are no single mutations that cause cross-resistance to both drugs; in patients with large disease burden, triple therapy is needed. We also find that simultaneous therapy with two drugs is much more effective than sequential therapy. Our results provide realistic expectations for the efficacy of new drug combinations and inform the design of trials for new cancer therapeutics. AU - Božić, Ivana AU - Reiter, Johannes AU - Allen, Benjamin AU - Antal, Tibor AU - Chatterjee, Krishnendu AU - Shah, Preya AU - Moon, Yo AU - Yaqubie, Amin AU - Kelly, Nicole AU - Le, Dung AU - Lipson, Evan AU - Chapman, Paul AU - Diaz, Luis AU - Vogelstein, Bert AU - Nowak, Martin ID - 2816 JF - eLife TI - Evolutionary dynamics of cancer in response to targeted combination therapy VL - 2 ER - TY - CONF AB - In this work we present a flexible tool for tumor progression, which simulates the evolutionary dynamics of cancer. Tumor progression implements a multi-type branching process where the key parameters are the fitness landscape, the mutation rate, and the average time of cell division. The fitness of a cancer cell depends on the mutations it has accumulated. The input to our tool could be any fitness landscape, mutation rate, and cell division time, and the tool produces the growth dynamics and all relevant statistics. AU - Reiter, Johannes AU - Božić, Ivana AU - Chatterjee, Krishnendu AU - Nowak, Martin ID - 2000 T2 - Proceedings of 25th Int. Conf. on Computer Aided Verification TI - TTP: Tool for tumor progression VL - 8044 ER - TY - CONF AB - We develop program synthesis techniques that can help programmers fix concurrency-related bugs. We make two new contributions to synthesis for concurrency, the first improving the efficiency of the synthesized code, and the second improving the efficiency of the synthesis procedure itself. The first contribution is to have the synthesis procedure explore a variety of (sequential) semantics-preserving program transformations. Classically, only one such transformation has been considered, namely, the insertion of synchronization primitives (such as locks). Based on common manual bug-fixing techniques used by Linux device-driver developers, we explore additional, more efficient transformations, such as the reordering of independent instructions. The second contribution is to speed up the counterexample-guided removal of concurrency bugs within the synthesis procedure by considering partial-order traces (instead of linear traces) as counterexamples. A partial-order error trace represents a set of linear (interleaved) traces of a concurrent program all of which lead to the same error. By eliminating a partial-order error trace, we eliminate in a single iteration of the synthesis procedure all linearizations of the partial-order trace. We evaluated our techniques on several simplified examples of real concurrency bugs that occurred in Linux device drivers. AU - Cerny, Pavol AU - Henzinger, Thomas A AU - Radhakrishna, Arjun AU - Ryzhyk, Leonid AU - Tarrach, Thorsten ID - 2445 TI - Efficient synthesis for concurrency by semantics-preserving transformations VL - 8044 ER - TY - JOUR AB - To fight infectious diseases, host immune defenses are employed at multiple levels. Sanitary behavior, such as pathogen avoidance and removal, acts as a first line of defense to prevent infection [1] before activation of the physiological immune system. Insect societies have evolved a wide range of collective hygiene measures and intensive health care toward pathogen-exposed group members [2]. One of the most common behaviors is allogrooming, in which nestmates remove infectious particles from the body surfaces of exposed individuals [3]. Here we show that, in invasive garden ants, grooming of fungus-exposed brood is effective beyond the sheer mechanical removal of fungal conidiospores; it also includes chemical disinfection through the application of poison produced by the ants themselves. Formic acid is the main active component of the poison. It inhibits fungal growth of conidiospores remaining on the brood surface after grooming and also those collected in the mouth of the grooming ant. This dual function is achieved by uptake of the poison droplet into the mouth through acidopore self-grooming and subsequent application onto the infectious brood via brood grooming. This extraordinary behavior extends the current understanding of grooming and the establishment of social immunity in insect societies. AU - Tragust, Simon AU - Mitteregger, Barbara AU - Barone, Vanessa AU - Konrad, Matthias AU - Ugelvig, Line V AU - Cremer, Sylvia ID - 2926 IS - 1 JF - Current Biology TI - Ants disinfect fungus-exposed brood by oral uptake and spread of their poison VL - 23 ER - TY - CONF AB - We study the complexity of central controller synthesis problems for finite-state Markov decision processes, where the objective is to optimize both the expected mean-payoff performance of the system and its stability. e argue that the basic theoretical notion of expressing the stability in terms of the variance of the mean-payoff (called global variance in our paper) is not always sufficient, since it ignores possible instabilities on respective runs. For this reason we propose alernative definitions of stability, which we call local and hybrid variance, and which express how rewards on each run deviate from the run's own mean-payoff and from the expected mean-payoff, respectively. We show that a strategy ensuring both the expected mean-payoff and the variance below given bounds requires randomization and memory, under all the above semantics of variance. We then look at the problem of determining whether there is a such a strategy. For the global variance, we show that the problem is in PSPACE, and that the answer can be approximated in pseudo-polynomial time. For the hybrid variance, the analogous decision problem is in NP, and a polynomial-time approximating algorithm also exists. For local variance, we show that the decision problem is in NP. Since the overall performance can be traded for stability (and vice versa), we also present algorithms for approximating the associated Pareto curve in all the three cases. Finally, we study a special case of the decision problems, where we require a given expected mean-payoff together with zero variance. Here we show that the problems can be all solved in polynomial time. AU - Brázdil, Tomáš AU - Chatterjee, Krishnendu AU - Forejt, Vojtěch AU - Kučera, Antonín ID - 2305 T2 - 28th Annual ACM/IEEE Symposium TI - Trading performance for stability in Markov decision processes ER - TY - CONF AB - In this paper, we introduce the powerful framework of graph games for the analysis of real-time scheduling with firm deadlines. We introduce a novel instance of a partial-observation game that is suitable for this purpose, and prove decidability of all the involved decision problems. We derive a graph game that allows the automated computation of the competitive ratio (along with an optimal witness algorithm for the competitive ratio) and establish an NP-completeness proof for the graph game problem. For a given on-line algorithm, we present polynomial time solution for computing (i) the worst-case utility; (ii) the worst-case utility ratio w.r.t. a clairvoyant off-line algorithm; and (iii) the competitive ratio. A major strength of the proposed approach lies in its flexibility w.r.t. incorporating additional constraints on the adversary and/or the algorithm, including limited maximum or average load, finiteness of periods of overload, etc., which are easily added by means of additional instances of standard objective functions for graph games. AU - Chatterjee, Krishnendu AU - Kößler, Alexander AU - Schmid, Ulrich ID - 2820 SN - 978-1-4503-1567-8 T2 - Proceedings of the 16th International conference on Hybrid systems: Computation and control TI - Automated analysis of real-time scheduling using graph games ER -