Abstract

We consider a two-edge connected, non-negatively real-weighted graph G with n vertices and m edges, and a single-source shortest paths tree (SPT) of G rooted at an arbitrary vertex. If an edge of the SPT is temporarily removed, a widely recognized approach to reconnect the vertices disconnected from the root consists of joining the two resulting subtrees by means of a single non-tree edge, called a swap edge. This allows to reduce consistently the set-up and computational costs which are incurred if one instead rebuilds a new optimal SPT from scratch. In the past, several optimality criteria have been considered to select a best possible swap edge, and here we restrict our attention to arguably the two most significant measures: the minimization of either the maximum or the average distance between the root and the disconnected vertices. For the former criteria, we present an \(O(m \log \alpha (m,n))\) time algorithm—where \(\alpha \) is the inverse of the Ackermann function—to find a best swap edge for every edge of the SPT, thus improving onto the previous \(O(m \log n)\) time algorithm. Concerning the latter criteria, we provide an \(O(m+n \log n)\) time algorithm for the special but important case where G is unweighted, which compares favourably with the \(O\left( m+n \, \alpha (n,n)\log ^2n\right) \) time bound that one would get by using the fastest algorithm known for the weighted case—once this is suitably adapted to the unweighted case.

by Simon D. Angus, Jonathan Newton

There is evidence that the sharing of intentions was an important factor in the evolution of humans’ unique cognitive abilities. Here, for the first time, we formally model the coevolution of jointly intentional behavior and cumulative culture, showing that rapid techno-cultural advance goes hand in hand with the emergence of the ability to participate in jointly intentional behavior. Conversely, in the absence of opportunities for significant techno-cultural improvement, the ability to undertake jointly intentional behavior is selected against. Thus, we provide a unified mechanism for the suppression or emergence of shared intentions and collaborative behavior in humans, as well as a potential cause of inter-species diversity in the prevalence of such behavior.

by Hsin-Hung Li, Marisa Carrasco, David J. Heeger

In interocular suppression, a suprathreshold monocular target can be rendered invisible by a salient competitor stimulus presented in the other eye. Despite decades of research on interocular suppression and related phenomena (e.g., binocular rivalry, flash suppression, continuous flash suppression), the neural processing underlying interocular suppression is still unknown. We developed and tested a computational model of interocular suppression. The model included two processes that contributed to the strength of interocular suppression: divisive normalization and attentional modulation. According to the model, the salient competitor induced a stimulus-driven attentional modulation selective for the location and orientation of the competitor, thereby increasing the gain of neural responses to the competitor and reducing the gain of neural responses to the target. Additional suppression was induced by divisive normalization in the model, similar to other forms of visual masking. To test the model, we conducted psychophysics experiments in which both the size and the eye-of-origin of the competitor were manipulated. For small and medium competitors, behavioral performance was consonant with a change in the response gain of neurons that responded to the target. But large competitors induced a contrast-gain change, even when the competitor was split between the two eyes. The model correctly predicted these results and outperformed an alternative model in which the attentional modulation was eye specific. We conclude that both stimulus-driven attention (selective for location and feature) and divisive normalization contribute to interocular suppression.

by Laurence Aitchison, Dan Bang, Bahador Bahrami, Peter E. Latham

Humans stand out from other animals in that they are able to explicitly report on the reliability of their internal operations. This ability, which is known as metacognition, is typically studied by asking people to report their confidence in the correctness of some decision. However, the computations underlying confidence reports remain unclear. In this paper, we present a fully Bayesian method for directly comparing models of confidence. Using a visual two-interval forced-choice task, we tested whether confidence reports reflect heuristic computations (e.g. the magnitude of sensory data) or Bayes optimal ones (i.e. how likely a decision is to be correct given the sensory data). In a standard design in which subjects were first asked to make a decision, and only then gave their confidence, subjects were mostly Bayes optimal. In contrast, in a less-commonly used design in which subjects indicated their confidence and decision simultaneously, they were roughly equally likely to use the Bayes optimal strategy or to use a heuristic but suboptimal strategy. Our results suggest that, while people’s confidence reports can reflect Bayes optimal computations, even a small unusual twist or additional element of complexity can prevent optimality.

by Serge Dmitrieff, François Nédélec

Endocytosis is an essential process by which cells internalize a piece of plasma membrane and material from the outside. In cells with turgor, pressure opposes membrane deformations, and increases the amount of force that has to be generated by the endocytic machinery. To determine this force, and calculate the shape of the membrane, we used physical theory to model an elastic surface under pressure. Accurate fits of experimental profiles are obtained assuming that the coated membrane is highly rigid and preferentially curved at the endocytic site. The forces required from the actin machinery peaks at the onset of deformation, indicating that once invagination has been initiated, endocytosis is unlikely to stall before completion. Coat proteins do not lower the initiation force but may affect the process by the curvature they induce. In the presence of isotropic curvature inducers, pulling the tip of the invagination can trigger the formation of a neck at the base of the invagination. Hence direct neck constriction by actin may not be required, while its pulling role is essential. Finally, the theory shows that anisotropic curvature effectors stabilize membrane invaginations, and the loss of crescent-shaped BAR domain proteins such as Rvs167 could therefore trigger membrane scission.

by Juan A. Delgado-SanMartin, Jennifer I. Hare, Alessandro P. S. de Moura, James W. T. Yates

Xenografts -as simplified animal models of cancer- differ substantially in vasculature and stromal architecture when compared to clinical tumours. This makes mathematical model-based predictions of clinical outcome challenging. Our objective is to further understand differences in tumour progression and physiology between animal models and the clinic. To achieve that, we propose a mathematical model based upon tumour pathophysiology, where oxygen -as a surrogate for endocrine delivery- is our main focus. The Oxygen-Driven Model (ODM), using oxygen diffusion equations, describes tumour growth, hypoxia and necrosis. The ODM describes two key physiological parameters. Apparent oxygen uptake rate (kR′) represents the amount of oxygen cells seem to need to proliferate. The more oxygen they appear to need, the more the oxygen transport. kR′ gathers variability from the vasculature, stroma and tumour morphology. Proliferating rate (kp) deals with cell line specific factors to promote growth. The KH,KN describe the switch of hypoxia and necrosis. Retrospectively, using archived data, we looked at longitudinal tumour volume datasets for 38 xenografted cell lines and 5 patient-derived xenograft-like models. Exploration of the parameter space allows us to distinguish 2 groups of parameters. Group 1 of cell lines shows a spread in values of kR′ and lower kp, indicating that tumours are poorly perfused and slow growing. Group 2 share the value of the oxygen uptake rate (kR′) and vary greatly in kp, which we interpret as having similar oxygen transport, but more tumour intrinsic variability in growth. However, the ODM has some limitations when tested in explant-like animal models, whose complex tumour-stromal morphology may not be captured in the current version of the model. Incorporation of stroma in the ODM will help explain these discrepancies. We have provided an example. The ODM is a very simple -and versatile- model suitable for the design of preclinical experiments, which can be modified and enhanced whilst maintaining confidence in its predictions.

by Christian L. Vestergaard, Mathieu Génois

Stochastic simulations are one of the cornerstones of the analysis of dynamical processes on complex networks, and are often the only accessible way to explore their behavior. The development of fast algorithms is paramount to allow large-scale simulations. The Gillespie algorithm can be used for fast simulation of stochastic processes, and variants of it have been applied to simulate dynamical processes on static networks. However, its adaptation to temporal networks remains non-trivial. We here present a temporal Gillespie algorithm that solves this problem. Our method is applicable to general Poisson (constant-rate) processes on temporal networks, stochastically exact, and up to multiple orders of magnitude faster than traditional simulation schemes based on rejection sampling. We also show how it can be extended to simulate non-Markovian processes. The algorithm is easily applicable in practice, and as an illustration we detail how to simulate both Poissonian and non-Markovian models of epidemic spreading. Namely, we provide pseudocode and its implementation in C++ for simulating the paradigmatic Susceptible-Infected-Susceptible and Susceptible-Infected-Recovered models and a Susceptible-Infected-Recovered model with non-constant recovery rates. For empirical networks, the temporal Gillespie algorithm is here typically from 10 to 100 times faster than rejection sampling.

Journal of the American Chemical SocietyDOI: 10.1021/jacs.5b09555

Journal of the American Chemical SocietyDOI: 10.1021/jacs.5b09117

Journal of the American Chemical SocietyDOI: 10.1021/jacs.5b08556

Journal of the American Chemical SocietyDOI: 10.1021/jacs.5b08915

Journal of the American Chemical SocietyDOI: 10.1021/jacs.5b05694

Journal of the American Chemical SocietyDOI: 10.1021/jacs.5b09738

Journal of the American Chemical SocietyDOI: 10.1021/jacs.5b09894

Journal of the American Chemical SocietyDOI: 10.1021/jacs.5b09572

Background: Numerous tools have been developed to predict the fitness effects (i.e., neutral, deleterious, or beneficial) of genetic variants on corresponding proteins. However, prediction in terms of whether a variant causes the variant bearing protein to lose the original function or gain new function is also needed for better understanding of how the variant contributes to disease/cancer. To address this problem, the present work introduces and computationally defines four types of functional outcome of a variant: gain, loss, switch, and conservation of function. The deployment of multiple hidden Markov models is proposed to computationally classify mutations by the four functional impact types. Results: The functional outcome is predicted for over a hundred thyroid stimulating hormone receptor (TSHR) mutations, as well as cancer related mutations in oncogenes or tumor suppressor genes. The results show that the proposed computational method is effective in fine grained prediction of the functional outcome of a mutation, and can be used to help elucidate the molecular mechanism of disease/cancer causing mutations. The program is freely available at http://bioinformatics.cs.vt.edu/zhanglab/HMMvar/download.php. Conclusion: This work is the first to computationally define and predict functional impact of mutations, loss, switch, gain, or conservation of function. These fine grained predictions can be especially useful for identifying mutations that cause or are linked to cancer.

Systems biologists aim to decipher the structure and dynamics of signaling and regulatory networks underpinning cellular responses; synthetic biologists can use this insight to alter existing networks or engineer de novo ones. Both tasks will benefit from an understanding of which structural and dynamic features of networks can emerge from evolutionary processes, through which intermediary steps these arise, and whether they embody general design principles. As natural evolution at the level of network dynamics is difficult to study, in silico evolution of network models can provide important insights. However, current tools used for in silico evolution of network dynamics are limited to ad hoc computer simulations and models. Here we introduce BioJazz, an extendable, user-friendly tool for simulating the evolution of dynamic biochemical networks. Unlike previous tools for in silico evolution, BioJazz allows for the evolution of cellular networks with unbounded complexity by combining rule-based modeling with an encoding of networks that is akin to a genome. We show that BioJazz can be used to implement biologically realistic selective pressures and allows exploration of the space of network architectures and dynamics that implement prescribed physiological functions. BioJazz is provided as an open-source tool to facilitate its further development and use. Source code and user manuals are available at: http://oss-lab.github.io/biojazz and http://osslab.lifesci.warwick.ac.uk/BioJazz.aspx.

A simple and efficient strategy for Bacterial Artificial Chromosome (BAC) recombineering based on co-selection is described. We show that it is possible to efficiently modify two positions of a BAC simultaneously by co-transformation of a single-stranded DNA oligo and a double-stranded selection cassette. The use of co-selection BAC recombineering reduces the DNA manipulation needed to make a conditional knockout gene targeting vector to only two steps: a single round of BAC modification followed by a retrieval step.

Access to genome-wide data provides the opportunity to address questions concerning the ability of transcription factors (TFs) to assemble in distinct macromolecular complexes. Here, we introduce the PAnDA (Protein And DNA Associations) approach to characterize DNA associations with human TFs using expression profiles, protein–protein interactions and recognition motifs. Our method predicts TF binding events with >0.80 accuracy revealing cell-specific regulatory patterns that can be exploited for future investigations. Even when the precise DNA-binding motifs of a specific TF are not available, the information derived from protein-protein networks is sufficient to perform high-confidence predictions (area under the ROC curve of 0.89). PAnDA is freely available at http://service.tartaglialab.com/new_submission/panda.

Elucidating the dynamic organization of nuclear RNA foci is important for understanding and manipulating these functional sites of gene expression in both physiological and pathological states. However, such studies have been difficult to establish in vivo as a result of the absence of suitable RNA imaging methods. Here, we describe a high-resolution fluorescence RNA imaging method, ECHO-liveFISH, to label endogenous nuclear RNA in living mice and chicks. Upon in vivo electroporation, exciton-controlled sequence-specific oligonucleotide probes revealed focally concentrated endogenous 28S rRNA and U3 snoRNA at nucleoli and poly(A) RNA at nuclear speckles. Time-lapse imaging reveals steady-state stability of these RNA foci and dynamic dissipation of 28S rRNA concentrations upon polymerase I inhibition in native brain tissue. Confirming the validity of this technique in a physiological context, the in vivo RNA labeling did not interfere with the function of target RNA nor cause noticeable cytotoxicity or perturbation of cellular behavior.