Are lock-free concurrent algorithms practically wait-free? - Alistarh, Dan-Adrian; Censor Hillel, Keren; Shavit, Nir
Lock-free concurrent algorithms guarantee that some concurrent operation will always make progress in a finite number of steps. Yet programmers prefer to treat concurrent code as if it were wait-free, guaranteeing that all operations always make progress. Unfortunately, designing wait-free algorithms is generally a very complex task, and the resulting algorithms are not always efficient. While obtaining efficient wait-free algorithms has been a long-time goal for the theory community, most non-blocking commercial code is only lock-free. This paper suggests a simple solution to this problem. We show that, for a large class of lock-free algorithms, under scheduling conditions which approximate those found in commercial hardware architectures, lock-free algorithms behave as if they are wait-free. In other words, programmers can keep on designing simple lock-free algorithms instead of complex wait-free ones, and in practice, they will get wait-free progress. Our main contribution is a new way of analyzing a general class of lock-free algorithms under a stochastic scheduler. Our analysis relates the individual performance of processes with the global performance of the system using Markov chain lifting between a complex per-process chain and a simpler system progress chain. We show that lock-free algorithms are not only wait-free with probability 1, but that in fact a general subset of lock-free algorithms can be closely bounded in terms of the average number of steps required until an operation completes. To the best of our knowledge, this is the first attempt to analyze progress conditions, typically stated in relation to a worst case adversary, in a stochastic model capturing their expected asymptotic behavior.

Communication-efficient randomized consensus - Alistarh, Dan-Adrian; Aspnes, James; King, Valerie; Saia, Jared
We describe a new randomized consensus protocol with expected message complexity O(n2log2n) when fewer than n/2 processes may fail by crashing. This is an almost-linear improvement over the best previously known protocol, and within logarithmic factors of a known Ω(n2) message lower bound. The protocol further ensures that no process sends more than O(n log3n) messages in expectation, which is again within logarithmic factors of optimal.We also present a generalization of the algorithm to an arbitrary number of failures t, which uses expected O(nt + t2log2t) total messages. Our protocol uses messages of size O(log n), and can therefore scale to large networks. We consider the problem of consensus in the challenging classic model. In this model, the adversary is adaptive; it can choose which processors crash at any point during the course of the algorithm. Further, communication is via asynchronous message passing: there is no known upper bound on the time to send a message from one processor to another, and all messages and coin flips are seen by the adversary. Our approach is to build a message-efficient, resilient mechanism for aggregating individual processor votes, implementing the message-passing equivalent of a weak shared coin. Roughly, in our protocol, a processor first announces its votes to small groups, then propagates them to increasingly larger groups as it generates more and more votes. To bound the number of messages that an individual process might have to send or receive, the protocol progressively increases the weight of generated votes. The main technical challenge is bounding the impact of votes that are still “in flight” (generated, but not fully propagated) on the final outcome of the shared coin, especially since such votes might have different weights. We achieve this by leveraging the structure of the algorithm, and a technical argument based on martingale concentration bounds. Overall, we show that it is possible to build an efficient message-passing implementation of a shared coin, and in the process (almost-optimally) solve the classic consensus problem in the asynchronous message-passing model.

Brief announcement: Are lock-free concurrent algorithms practically wait-free? - Alistarh, Dan-Adrian; Censor Hille, Keren; Shavit, Nir
Lock-free concurrent algorithms guarantee that some concurrent operation will always make progress in a finite number of steps. Yet programmers would prefer to treat concurrent code as if it were wait-free, guaranteeing that all operations always make progress. Unfortunately, designing wait-free algorithms is in general a complex undertaking, and the resulting algorithms are not always efficient, so most non-blocking commercial code is only lock-free, and the design of efficient wait-free algorithms has been left to the academic community. In [2], we suggest a solution to this problem. We show that, for a large class of lock-free algorithms, under scheduling conditions which approximate those found in commercial hardware architectures, lock-free algorithms behave as if they are wait-free. In other words, programmers can keep on designing simple lock-free algorithms instead of complex wait-free ones, and in practice, they will get wait-free progress. Our main contribution is a new way of analyzing a general class of lock-free algorithms under a stochastic scheduler. Our analysis relates the individual performance of processes with the global performance of the system using Markov chain lifting between a complex per-process chain and a simpler system progress chain. We show that lock-free algorithms are not only wait-free with probability 1, but that in fact a broad subset of lock-free algorithms can be closely bounded in terms of the average number of steps required until an operation completes.

The levelarray: A fast, practical long-lived renaming algorithm - Alistarh, Dan-Adrian; Kopinsky, Justin; Matveev, Alexander; Shavit, Nir
The long-lived renaming problem appears in shared-memory systems where a set of threads need to register and deregister frequently from the computation, while concurrent operations scan the set of currently registered threads. Instances of this problem show up in concurrent implementations of transactional memory, flat combining, thread barriers, and memory reclamation schemes for lock-free data structures. In this paper, we analyze a randomized solution for long-lived renaming. The algorithmic technique we consider, called the Level Array, has previously been used for hashing and one-shot (single-use) renaming. Our main contribution is to prove that, in long-lived executions, where processes may register and deregister polynomially many times, the technique guarantees constant steps on average and O (log log n) steps with high probability for registering, unit cost for deregistering, and O (n) steps for collect queries, where n is an upper bound on the number of processes that may be active at any point in time. We also show that the algorithm has the surprising property that it is self-healing: under reasonable assumptions on the schedule, operations running while the data structure is in a degraded state implicitly help the data structure re-balance itself. This subtle mechanism obviates the need for expensive periodic rebuilding procedures. Our benchmarks validate this approach, showing that, for typical use parameters, the average number of steps a process takes to register is less than two and the worst-case number of steps is bounded by six, even in executions with billions of operations. We contrast this with other randomized implementations, whose worst-case behavior we show to be unreliable, and with deterministic implementations, whose cost is linear in n.

Structure of the excitation spectrum for many-body quantum systems - Seiringer, Robert (Proceeding of the International Congress of Mathematicans)
Many questions concerning models in quantum mechanics require a detailed analysis of the spectrum of the corresponding Hamiltonian, a linear operator on a suitable Hilbert space. Of particular relevance for an understanding of the low-temperature properties of a system is the structure of the excitation spectrum, which is the part of the spectrum close to the spectral bottom. We present recent progress on this question for bosonic many-body quantum systems with weak two-body interactions. Such system are currently of great interest, due to their experimental realization in ultra-cold atomic gases. We investigate the accuracy of the Bogoliubov approximations, which predicts that the low-energy spectrum is made up of sums of elementary excitations, with linear dispersion law at low momentum. The latter property is crucial for the superfluid behavior the system.

Cryo electron microscopy of tubular arrays of HIV-1 Gag resolves structures essential for immature virus assembly - Bharata, Tanmay A; Menendez, Luis R; Hagena, Wim J; Luxd, Vanda; Igonete, Sebastien; Schorba, Martin; Florian Schur; Kraüsslich, Hans Georg; Briggsa, John A (PNAS)
The assembly of HIV-1 is mediated by oligomerization of the major structural polyprotein, Gag, into a hexameric protein lattice at the plasma membrane of the infected cell. This leads to budding and release of progeny immature virus particles. Subsequent proteolytic cleavage of Gag triggers rearrangement of the particles to form mature infectious virions. Obtaining a structural model of the assembled lattice of Gag within immature virus particles is necessary to understand the interactions that mediate assembly of HIV-1 particles in the infected cell, and to describe the substrate that is subsequently cleaved by the viral protease. An 8-Å resolution structure of an immature virus-like tubular array assembled from a Gag-derived protein of the related retrovirus Mason-Pfizer monkey virus (M-PMV) has previously been reported, and a model for the arrangement of the HIV-1 capsid (CA) domains has been generated based on homology to this structure. Here we have assembled tubular arrays of a HIV-1 Gag-derived protein with an immature-like arrangement of the C-terminal CA domains and have solved their structure by using hybrid cryo-EM and tomography analysis. The structure reveals the arrangement of the C-terminal domain of CA within an immature-like HIV-1 Gag lattice, and provides, to our knowledge, the first high-resolution view of the region immediately downstream of CA, which is essential for assembly, and is significantly different from the respective region in M-PMV. Our results reveal a hollow column of density for this region in HIV-1 that is compatible with the presence of a six-helix bundle at this position.

Generation of a canine anti-EGFR (ErbB-1) antibody for passive immunotherapy in dog cancer patients - Singer, J.; Fazekas, Judit; Wang, W.; Weichselbaumer, M.; Matz, M.; Mader, A.; Steinfellner, W.; Meitz, S.; Mechtcheriakova, D.; Sobanov, Y.; Willmann, M.; Stockner, T.; et al. (Molecular Cancer Therapeutics)
Passive immunotherapy with monoclonal antibodies represents a cornerstone of human anticancer therapies, but has not been established in veterinary medicine yet. As the tumor-associated antigen EGFR (ErbB-1) is highly conserved between humans and dogs, and considering the effectiveness of the anti-EGFR antibody cetuximab in human clinical oncology, we present here a “caninized” version of this antibody, can225IgG, for comparative oncology studies. Variable region genes of 225, the murine precursor of cetuximab, were fused with canine constant heavy gamma and kappa chain genes, respectively, and transfected into Chinese hamster ovary (CHO) DUKX-B11 cells. Of note, 480 clones were screened and the best clones were selected according to productivity and highest specificity in EGFR-coated ELISA. Upon purification with Protein G, the recombinant cetuximab-like canine IgG was tested for integrity, correct assembly, and functionality. Specific binding to the surface of EGFR-overexpressing cells was assessed by flow cytometry and immunofluorescence; moreover, binding to canine mammary tissue was demonstrated by immunohistochemistry. In cell viability and proliferation assays, incubation with can225IgG led to significant tumor cell growth inhibition. Moreover, this antibody mediated significant tumor cell killing via phagocytosis in vitro. We thus present here, for the first time, the generation of a canine IgG antibody and its hypothetical structure. On the basis of its cetuximab-like binding site, on the one hand, and the expression of a 91% homologous EGFR molecule in canine cancer, on the other hand, this antibody may be a promising research compound to establish passive immunotherapy in dog patients with cancer.

Crossing-over in a hypervariable species preferentially occurs in regions of high local similarity - Seplyarskiy, Vladimir B; Logacheva, Maria D; Penin, Aleksey A; Baranová, Maria A; Leushkin, Evgeny V; Demidenko, Natalia V; Klepikova, Anna V; Fyodor Kondrashov; Kondrashov, Alexey S; James, Timothy Y (Molecular Biology and Evolution)
Recombination between double-stranded DNA molecules is a key genetic process which occurs in a wide variety of organisms. Usually, crossing-over (CO) occurs during meiosis between genotypes with 98.0-99.9% sequence identity, because within-population nucleotide diversity only rarely exceeds 2%. However, some species are hypervariable and it is unclear how CO can occur between genotypes with less than 90% sequence identity. Here, we study CO in Schizophyllum commune, a hypervariable cosmopolitan basidiomycete mushroom, a frequently encountered decayer of woody substrates. We crossed two haploid individuals, from the United States and from Russia, and obtained genome sequences for their 17 offspring. The average genetic distance between the parents was 14%, making it possible to study CO at very high resolution. We found reduced levels of linkage disequilibrium between loci flanking the CO sites indicating that they are mostly confined to hotspots of recombination. Furthermore, CO events preferentially occurred in regions under stronger negative selection, in particular within exons that showed reduced levels of nucleotide diversity. Apparently, in hypervariable species CO must avoid regions of higher divergence between the recombining genomes due to limitations imposed by the mismatch repair system, with regions under strong negative selection providing the opportunity for recombination. These patterns are opposite to those observed in a number of less variable species indicating that population genomics of hypervariable species may reveal novel biological phenomena.

Long-Term asymmetrical acceleration of protein evolution after gene duplication - Rosello, Oriol P; Fyodor Kondrashov (Genome Biology and Evolution)
Rapid divergence of gene copies after duplication is thought to determine the fate of the copies and evolution of novel protein functions. However, data on howlong the gene copies continue to experience an elevated rate of evolution remain scarce. Standard theory of gene duplications based on some level of genetic redundancy of gene copies predicts that the period of accelerated evolutionmust end relatively quickly. Using a maximum-likelihood approach we estimate preduplication, initial postduplication, and recent postduplication rates of evolution that occurred in themammalian lineage.Wefind that both gene copies experience a similar in magnitude acceleration in their rate of evolution. The copy located in the original genomic position typically returns to the preduplication rates of evolution in a short period of time. The burst of faster evolution of the copy that is located in a new genomic position typically lasts longer. Furthermore, the fast-evolving copies on average continue to evolve faster than the preduplication rates far longer than predicted by standard theory of gene duplications.We hypothesize that the prolonged elevated rates of evolution are determined by functional properties that were acquired during, or soon after, the gene duplication event.

Duplication of a promiscuous transcription factor drives the emergence of a new regulatory network - Pougach, Ksenia S; Voet, Arnout R; Fyodor Kondrashov; Voordeckers, Karin; Christiaens, Joaquin F; Baying, Bianka; Bénès, Vladimı́r; Sakai, Ryo; Aerts, Jan A; Zhu, Bo; Van Dijck, Patrick; Verstrepen, Kevin J (Nature Communications)
The emergence of new genes throughout evolution requires rewiring and extension of regulatory networks. However, the molecular details of how the transcriptional regulation of new gene copies evolves remain largely unexplored. Here we show how duplication of a transcription factor gene allowed the emergence of two independent regulatory circuits. Interestingly, the ancestral transcription factor was promiscuous and could bind different motifs in its target promoters. After duplication, one paralogue evolved increased binding specificity so that it only binds one type of motif, whereas the other copy evolved a decreased activity so that it only activates promoters that contain multiple binding sites. Interestingly, only a few mutations in both the DNA-binding domains and in the promoter binding sites were required to gradually disentangle the two networks. These results reveal how duplication of a promiscuous transcription factor followed by concerted cis and trans mutations allows expansion of a regulatory network.

The ctenophore genome and the evolutionary origins of neural systems - Moroz, Leonid L; Kocot, Kevin M; Citarella, Mathew R; Dosung, Sohn; Norekian, Tigran P; Povolotskaya, Inna; Grigorenko, Anastasia P; Dailey, Christopher A; Berezikov, Eugene; Buckley, Katherine M; Ptitsyn, Andrey A; Reshetov, Denis A; et al. (Nature)
The origins of neural systems remain unresolved. In contrast to other basal metazoans, ctenophores (comb jellies) have both complex nervous and mesoderm-derived muscular systems. These holoplanktonic predators also have sophisticated ciliated locomotion, behaviour and distinct development. Here we present the draft genome of Pleurobrachia bachei, Pacific sea gooseberry, together with ten other ctenophore transcriptomes, and show that they are remarkably distinct from other animal genomes in their content of neurogenic, immune and developmental genes. Our integrative analyses place Ctenophora as the earliest lineage within Metazoa. This hypothesis is supported by comparative analysis of multiple gene families, including the apparent absence of HOX genes, canonical microRNA machinery, and reduced immune complement in ctenophores. Although two distinct nervous systems are well recognized in ctenophores, many bilaterian neuron-specific genes and genes of 'classical' neurotransmitter pathways either are absent or, if present, are not expressed in neurons. Our metabolomic and physiological data are consistent with the hypothesis that ctenophore neural systems, and possibly muscle specification, evolved independently from those in other animals.

Anti leprosy drug clofazimine inhibits growth of triple-negative breast cancer cells via inhibition of canonical Wnt signaling - Koval, Alexey V; Vlasov, Peter K; Shichkova, Polina; Khunderyakova, S; Markov, Yury; Panchenko, J; Volodina, A; Fyodor Kondrashov; Katanaev, Vladimir L (Biochemical Pharmacology)
Research on existing drugs often discovers novel mechanisms of their action and leads to the expansion of their therapeutic scope and subsequent remarketing. The Wnt signaling pathway is of the immediate therapeutic relevance, as it plays critical roles in cancer development and progression. However, drugs which disrupt this pathway are unavailable despite the high demand. Here we report an attempt to identify antagonists of the Wnt-FZD interaction among the library of the FDA-approved drugs. We performed an in silico screening which brought up several potential antagonists of the ligand-receptor interaction. 14 of these substances were tested using the TopFlash luciferase reporter assay and four of them identified as active and specific inhibitors of the Wnt3a-induced signaling. However, further analysis through GTP-binding and β-catenin stabilization assays showed that the compounds do not target the Wnt-FZD pair, but inhibit the signaling at downstream levels. We further describe the previously unknown inhibitory activity of an anti-leprosy drug clofazimine in the Wnt pathway and provide data demonstrating its efficiency in suppressing growth of Wnt-dependent triple-negative breast cancer cells. These data provide a basis for further investigations of the efficiency of clofazimine in treatment of Wnt-dependent cancers.

A structural perspective of compensatory evolution - Ivankov, Dmitry; Finkelstein, Alexei; Kondrashov, Fyodor (Current Opinion in Structural Biology)
The study of molecular evolution is important because it reveals how protein functions emerge and evolve. Recently, several types of studies indicated that substitutions in molecular evolution occur in a compensatory manner, whereby the occurrence of a substitution depends on the amino acid residues at other sites. However, a molecular or structural basis behind the compensation often remains obscure. Here, we review studies on the interface of structural biology and molecular evolution that revealed novel aspects of compensatory evolution. In many cases structural studies benefit from evolutionary data while structural data often add a functional dimension to the study of molecular evolution.

Balance between apical membrane growth and luminal matrix resistance determines epithelial tubule shape - Dong, Bo; Hannezo, Edouard B; Hayashi, Shigeo (Cell Reports)
The morphological stability of biological tubes is crucial for the efficient circulation of fluids and gases. Failure of this stability causes irregularly shaped tubes found in multiple pathological conditions. Here, we report that Drosophila mutants of the ESCRT III component Shrub/Vps32 exhibit a strikingly elongated sinusoidal tube phenotype. This is caused by excessive apical membrane synthesis accompanied by the ectopic accumulation and overactivation of Crumbs in swollen endosomes. Furthermore, we demonstrate that the apical extracellular matrix (aECM) of the tracheal tube is a viscoelastic material coupled with the apical membrane. We present a simple mechanical model in which aECM elasticity, apical membrane growth, and their interaction are three vital parameters determining the stability of biological tubes. Our findings demonstrate a mechanical role for the extracellular matrix and suggest that the interaction of the apical membrane and an elastic aECM determines the final morphology of biological tubes independent of cell shape.

Growth homeostatic regulation and stem cell dynamics in tissues - Hannezo, Edouard B; Prost, Jacques; Joanny, Jean (Journal of the Royal Society Interface)
The regulation of cell growth in animal tissues is a question of critical importance: most tissues contain different types of cells in interconversion and the fraction of each type has to be controlled in a precise way, by mechanisms that remain unclear. Here, we provide a theoretical framework for the homeostasis of stem-cell-containing epithelial tissues using mechanical equations, which describe the size of the tissue and kinetic equations, which describe the interconversions of the cell populations. We show that several features, such as the evolution of stem cell fractions during intestinal development, the shape of a developing intestinal wall, as well as the increase in the proliferative compartment in cancer initiation, can be studied and understood from generic modelling which does not rely on a particular regulatory mechanism. Finally, inspired by recent experiments, we propose a model where cell division rates are regulated by the mechanical stresses in the epithelial sheet. We show that pressure-controlled growth can, in addition to the previous features, also explain with few parameters the formation of stem cell compartments as well as the morphologies observed when a colonic crypt becomes cancerous. We also discuss optimal strategies of wound healing, in connection with experiments on the cornea.

Theory of epithelial sheet morphology in three dimensions - Hannezo, Edouard B; Prost, Jacques; Joanny, Jean (PNAS)
Morphogenesis during embryo development requires the coordination of mechanical forces to generate the macroscopic shapes of organs. We propose a minimal theoretical model, based on cell adhesion and actomyosin contractility, which describes the various shapes of epithelial cells and the bending and buckling of epithelial sheets, as well as the relative stability of cellular tubes and spheres. We show that, to understand these processes, a full 3D description of the cells is needed, but that simple scaling laws can still be derived. The morphologies observed in vivo can be understood as stable points of mechanical equations and the transitions between them are either continuous or discontinuous. We then focus on epithelial sheet bending, a ubiquitous morphogenetic process. We calculate the curvature of an epithelium as a function of actin belt tension as well as of cell-cell and and cell-substrate tension. The model allows for a comparison of the relative stabilities of spherical or cylindrical cellular structures (acini or tubes). Finally, we propose a unique type of buckling instability of epithelia, driven by a flattening of individual cell shapes, and discuss experimental tests to verify our predictions.

Coherent operations and screening in multielectron spin qubits - Higginbotham, Andrew P; Kuemmeth, Ferdinand; Hanson, Micah; Gossard, Arthur; Marcus, Charles (APS Physics, Physical Review Letters)
Multielectron spin qubits are demonstrated, and performance examined by comparing coherent exchange oscillations in coupled single-electron and multielectron quantum dots, measured in the same device. Fast (>1 GHz) exchange oscillations with a quality factor Q∼15 are found for the multielectron case, compared to Q∼2 for the single-electron case, the latter consistent with experiments in the literature. A model of dephasing that includes voltage and hyperfine noise is developed that is in good agreement with both single- and multielectron data, though in both cases additional exchange-independent dephasing is needed to obtain quantitative agreement across a broad parameter range.

Correlative light- and electron microscopy with chemical tags - Perkovic, Mario; Kunz, Michael; Endesfelder, Ulrike; Bunse, Stefanie; Wigge, Christoph; Yu, Zhou; Hodirnau, Victor-Valentin; Scheffer, Margot P.; Seybert, Anja; Malkusch, Sebastian; Schuman, Erin M.; Heilemann, Mike; et al. (Journal of Structural Biology)
Correlative microscopy incorporates the specificity of fluorescent protein labeling into high-resolution electron micrographs. Several approaches exist for correlative microscopy, most of which have used the green fluorescent protein (GFP) as the label for light microscopy. Here we use chemical tagging and synthetic fluorophores instead, in order to achieve protein-specific labeling, and to perform multicolor imaging. We show that synthetic fluorophores preserve their post-embedding fluorescence in the presence of uranyl acetate. Post-embedding fluorescence is of such quality that the specimen can be prepared with identical protocols for scanning electron microscopy (SEM) and transmission electron microscopy (TEM); this is particularly valuable when singular or otherwise difficult samples are examined. We show that synthetic fluorophores give bright, well-resolved signals in super-resolution light microscopy, enabling us to superimpose light microscopic images with a precision of up to 25 nm in the x–y plane on electron micrographs. To exemplify the preservation quality of our new method we visualize the molecular arrangement of cadherins in adherens junctions of mouse epithelial cells.

Antilocalization of coulomb blockade in a Ge/Si nanowire - Higginbotham, Andrew P; Kuemmeth, Ferdinand; Larsen, Thorvald; Fitzpatrick, Mattias; Yao, Jun; Yan, Hao; Lieber, Charles; Marcus, Charles (APS Physics, Physical Review Letters)
The distribution of Coulomb blockade peak heights as a function of magnetic field is investigated experimentally in a Ge-Si nanowire quantum dot. Strong spin-orbit coupling in this hole-gas system leads to antilocalization of Coulomb blockade peaks, consistent with theory. In particular, the peak height distribution has its maximum away from zero at zero magnetic field, with an average that decreases with increasing field. Magnetoconductance in the open-wire regime places a bound on the spin-orbit length (lso < 20 nm), consistent with values extracted in the Coulomb blockade regime (lso < 25 nm).

Transition probability between TF expression states when Dbx2 inhibits Nkx2.2 - Lovrics, Anna; Gao, Yu; Juhász, Bianka; Bock, István; Byrne, Helen M.; Dinnyés, András; Kovács, Krisztián