The Forgiving Graph: a distributed data structure for low stretch under adversarial attack

We consider the problem of self-healing in peer-to-peer networks that are under repeated attack by an omniscient adversary. We assume that, over a sequence of rounds, an adversary either inserts a node with arbitrary connections or deletes an arbitrary node from the network. The network responds to each such change by quick “repairs,” which consist of adding or deleting a small number of edges. These repairs essentially preserve closeness of nodes after adversarial deletions, without increasing node degrees by too much, in the following sense. At any point in the algorithm, nodes v and w whose distance would have been l in the graph formed by considering only the adversarial insertions (not the adversarial deletions), will be at distance at most l log n in the actual graph, where n is the total number of vertices seen so far. Similarly, at any point, a node v whose degree would have been d in the graph with adversarial insertions only, will have degree at most 3d in the actual graph. Our distributed data structure, which we call the Forgiving Graph, has low latency and bandwidth requirements. The Forgiving Graph improves on the Forgiving Tree distributed data structure from Hayes et al. (2008) in the following ways: 1) it ensures low stretch over all pairs of nodes, while the Forgiving Tree only ensures low diameter increase; 2) it handles both node insertions and deletions, while the Forgiving Tree only handles deletions; 3) it requires only a very simple and minimal initialization phase, while the Forgiving Tree initially requires construction of a spanning tree of the network.

The Forgiving Graph:A distributed data structure for low stretch under adversarial attack

We consider the problem of self-healing in peer-to-peer networks that are under repeated attack by an omniscient adversary. We assume that, over a sequence of rounds, an adversary either inserts a node with arbitrary connections or deletes an arbitrary node from the network. The network responds to each such change by quick "repairs," which consist of adding or deleting a small number of edges. These repairs essentially preserve closeness of nodes after adversarial deletions,without increasing node degrees by too much, in the following sense. At any point in the algorithm, nodes v and w whose distance would have been - in the graph formed by considering only the adversarial insertions (not the adversarial deletions), will be at distance at most - log n in the actual graph, where n is the total number of vertices seen so far. Similarly, at any point, a node v whose degreewould have been d in the graph with adversarial insertions only, will have degree at most 3d in the actual graph. Our distributed data structure, which we call the Forgiving Graph, has low latency and bandwidth requirements. The Forgiving Graph improves on the Forgiving Tree distributed data structure from Hayes et al. (2008) in the following ways: 1) it ensures low stretch over all pairs of nodes, while the Forgiving Tree only ensures low diameter increase; 2) it handles both node insertions and deletions, while the Forgiving Tree only handles deletions; 3) it requires only a very simple and minimal initialization phase, while the Forgiving Tree initially requires construction of a spanning tree of the network. © Springer-Verlag 2012.

GPCR structure, function, drug discovery and crystallography: report from Academia-Industry International Conference (UK Royal Society) Chicheley Hall, 1-2 September 2014

G-protein coupled receptors (GPCRs) are the targets of over half of all prescribed drugs today. The UniProt database has records for about 800 proteins classified as GPCRs, but drugs have only been developed against 50 of these. Thus, there is huge potential in terms of the number of targets for new therapies to be designed. Several breakthroughs in GPCRs biased pharmacology, structural biology, modelling and scoring have resulted in a resurgence of interest in GPCRs as drug targets. Therefore, an international conference, sponsored by the Royal Society, with world-renowned researchers from industry and academia was recently held to discuss recent progress and highlight key areas of future research needed to accelerate GPCR drug discovery. Several key points emerged. Firstly, structures for all three major classes of GPCRs have now been solved and there is increasing coverage across the GPCR phylogenetic tree. This is likely to be substantially enhanced with data from x-ray free electron sources as they move beyond proof of concept. Secondly, the concept of biased signalling or functional selectivity is likely to be prevalent in many GPCRs, and this presents exciting new opportunities for selectivity and the control of side effects, especially when combined with increasing data regarding allosteric modulation. Thirdly, there will almost certainly be some GPCRs that will remain difficult targets because they exhibit complex ligand dependencies and have many metastable states rendering them difficult to resolve by crystallographic methods. Subtle effects within the packing of the transmembrane helices are likely to mask and contribute to this aspect, which may play a role in species dependent behaviour. This is particularly important because it has ramifications for how we interpret pre-clinical data. In summary, collaborative efforts between industry and academia have delivered significant progress in terms of structure and understanding of GPCRs and will be essential for resolving problems associated with the more difficult targets in the future.

Extended Tree Augmented Naive Classifier

This work proposes an extended version of the well-known tree-augmented naive Bayes (TAN) classifier where the structure learning step is performed without requiring features to be connected to the class. Based on a modification of Edmonds’ algorithm, our structure learning procedure explores a superset of the structures that are considered by TAN, yet achieves global optimality of the learning score function in a very efficient way (quadratic in the number of features, the same complexity as learning TANs). A range of experiments show that we obtain models with better accuracy than TAN and comparable to the accuracy of the state-of-the-art classifier averaged one-dependence estimator.

Lack of genetic structure and evidence for long-distance dispersal in ash (Fraxinus excelsior) populations under threat from an emergent fungal pathogen: implications for restorative planting

Genetic analysis on populations of European ash (Fraxinus excelsior) throughout Ireland was carried out to determine the levels and patterns of genetic diversity in naturally seeded trees in ash woodlands and hedgerows, with the aim of informing conservation and replanting strategies in the face of potential loss of trees as a result of ash dieback. Samples from 33 sites across Northern Ireland and three sites in the Republic of Ireland were genotyped for eight nuclear and ten chloroplast microsatellites. Levels of diversity were high (mean A R = 10.53; mean H O = 0.709; mean H E = 0.765) and were similar to those in Great Britain and continental Europe, whilst levels of population genetic differentiation based on nuclear microsatellites were extremely low (Φ ST = 0.0131). Levels of inbreeding (mean F IS = 0.067) were significantly lower than those reported for populations from Great Britain. Fine-scale analysis of seed dispersal indicated potential for dispersal over hundreds of metres. Our results suggest that ash woodlands across Ireland could be treated as a single management unit, and thus native material from anywhere in Ireland could be used as a source for replanting. In addition, high potential for dispersal has implications for recolonization processes post-ash dieback (Chalara fraxinea) infection, and could aid in our assessment of the capacity of ash to shift its range in response to global climate change.

Coastal upwelling drives intertidal assemblage structure and trophic ecology

ecosystems. Coastal oceanic upwelling, for example, has been associated with elevatedbiomass and abundance patterns of certain functional groups, e.g., corticated macroalgae.In the upwelling system of Northern Chile, we examined measures of intertidal macrobenthiccomposition, structure and trophic ecology across eighteen shores varying in theirproximity to two coastal upwelling centres, in a hierarchical sampling design (spatial scalesof >1 and >10 km). The influence of coastal upwelling on intertidal communities was confirmedby the stable isotope values (δ13C and δ15N) of consumers, including a dominantsuspension feeder, grazers, and their putative resources of POM, epilithic biofilm, andmacroalgae. We highlight the utility of muscle δ15N from the suspension feeding mussel,Perumytilus purpuratus, as a proxy for upwelling, supported by satellite data and previousstudies. Where possible, we used corrections for broader-scale trends, spatial autocorrelation,ontogenetic dietary shifts and spatial baseline isotopic variation prior to analysis. Ourresults showed macroalgal assemblage composition, and benthic consumer assemblagestructure, varied significantly with the intertidal influence of coastal upwelling, especiallycontrasting bays and coastal headlands. Coastal topography also separated differences inconsumer resource use. This suggested that coastal upwelling, itself driven by coastlinetopography, influences intertidal communities by advecting nearshore phytoplankton populationsoffshore and cooling coastal water temperatures. We recommend the isotopic valuesof benthic organisms, specifically long-lived suspension feeders, as in situ alternativesto offshore measurements of upwelling influence

Latent and Explicit Authority in Hierarchical Organizations

We consider the problem of the exercise of authority within social production organizations, embedding the decision makers into a structure of formal authority relationships. We distinguish two types of behavior. First, we introduce an equilibrium notion implementing latent authority under which subordinates submit themselves to authority even though such authority is not en- forced explicitly. Second, we compare this with a non-cooperative equilibrium concept describing explicit exercise of authority. We show that for low enough enforcement costs both forms of authority will be exercised in equilibrium, but for higher enforcement costs latent authority will be exercised while explicit authority will not.

Impacts of invasive browsers on demographic rates and forest structure in New Zealand

Background/Question/Methods

Assessing the large scale impact of deer populations on forest structure and composition is important because of their increasing abundance in many temperate forests. Deer are invasive animals and sometimes thought to be responsible for immense damage to New Zealand’s forests. We report demographic changes taking place among 40 widespread indigenous tree species over 20 years, following a period of record deer numbers in the 1950s and a period of extensive hunting and depletion of deer populations during the 1960s and 1970s.

Results/Conclusions

Across a network of 578 plots there was an overall 13% reduction in sapling density of our study species with most remaining constant and a few declining dramatically. The effect of suppressed recruitment when deer populations were high was evident in the small tree size class (30 – 80 mm dbh). Stem density decreased by 15% and species with the greatest annual decreases in small tree density were those which have the highest rates of sapling recovery in exclosures indicating that deer were responsible. Densities of large canopy trees have remained relatively stable. There were imbalances between mortality and recruitment rates for 23 of the 40 species, 7 increasing and 16 in decline. These changes were again linked with sapling recovery in exclosures; species which recovered most rapidly following deer exclusion had the greatest net recruitment deficit across the wider landscape, indicating recruitment suppression by deer as opposed to mortality induced by disturbance and other herbivores. Species are not declining uniformly across all populations and no species are in decline across their entire range. Therefore we predict that with continued deer presence some forests will undergo compositional changes but that none of the species tested will become nationally extinct.

Impacts of invasive browsers on demographic rates and forest structure in New Zealand. Available from: http://www.researchgate.net/publication/267285500_Impacts_of_invasive_browsers_on_demographic_rates_and_forest_structure_in_New_Zealand [accessed Oct 9, 2015].

Learning Extended Tree Augmented Naive Structures

This work proposes an extended version of the well-known tree-augmented naive Bayes (TAN) classifier where the structure learning step is performed without requiring features to be connected to the class. Based on a modification of Edmonds' algorithm, our structure learning procedure explores a superset of the structures that are considered by TAN, yet achieves global optimality of the learning score function in a very efficient way (quadratic in the number of features, the same complexity as learning TANs). We enhance our procedure with a new score function that only takes into account arcs that are relevant to predict the class, as well as an optimization over the equivalent sample size during learning. These ideas may be useful for structure learning of Bayesian networks in general. A range of experiments shows that we obtain models with better prediction accuracy than naive Bayes and TAN, and comparable to the accuracy of the state-of-the-art classifier averaged one-dependence estimator (AODE). We release our implementation of ETAN so that it can be easily installed and run within Weka.

Learning Bounded Tree-Width Bayesian Networks via Sampling

Learning Bayesian networks with bounded tree-width has attracted much attention recently, because low tree-width allows exact inference to be performed efficiently. Some existing methods [12, 14] tackle the problem by using k-trees to learn the optimal Bayesian network with tree-width up to k. In this paper, we propose a sampling method to efficiently find representative k-trees by introducing an Informative score function to characterize the quality of a k-tree. The proposed algorithm can efficiently learn a Bayesian network with tree-width at most k. Experiment results indicate that our approach is comparable with exact methods, but is much more computationally efficient.

Implication of modified molecular structure of lipid through heat-related process to fatty acids supply in Brassica carinata seed.

This study was conducted to explore the effect of different autoclave heating times (30, 60 and 90 min) on fatty acids supply and molecular stability in Brassica carinata seed. Multivariate spectral analyses and correlation analyses were also carried out in our study. The results showed that autoclaving treatments significantly decreased the total fatty acids content in a linear fashion in B. carinata seed as heating time increased. Reduced concentrations were also observed in C18:3n3, C20:1, C22:1n9, monounsaturated fatty acids (MUFA), polyunsaturated fatty acids (PUFA), omega 3 (ω-3) and 9 (ω-9) fatty acids. Correspondingly, the heated seeds showed dramatic reductions in all the peak intensities within lipid-related spectral regions. Results from agglomerative hierarchical cluster analysis (AHCA) and principal component analysis (PCA) indicated that the raw oilseed had completely different structural make-up from the autoclaved seeds in both CH3 and CH2 asymmetric and symmetric stretching region (ca. 2999–2800 cm−1) and lipid ester Cdouble bond; length as m-dashO carbonyl region (ca. 1787–1706 cm−1). However, the oilseeds heated for 30, 60 and 90 min were not grouped into separate classes or ellipses in all the lipid-related regions, indicating that there still exhibited similarities in lipid biopolymer conformations among autoclaved B. carinata seeds. Moreover, strong correlations between spectral information and fatty acid compositions observed in our study could imply that lipid-related spectral parameters might have a potential to predict some fatty acids content in oilseed samples, i.e. B. carinata. However, more data from large sample size and diverse range would be necessary and helpful to draw up a final conclusion.