Fast Generation of Sparse Random Kernel Graphs

The development of kernel-based inhomogeneous random graphs has provided models that are flexible enough to capture many observed characteristics of real networks, and that are also mathematically tractable. We specify a class of inhomogeneous random graph models, called random kernel graphs, that produces sparse graphs with tunable graph properties, and we develop an efficient generation algorithm to sample random instances from this model. As real-world networks are usually large, it is essential that the run-time of generation algorithms scales better than quadratically in the number of vertices n. We show that for many practical kernels our algorithm runs in time at most 𝒪(n(logn)²). As a practical example we show how to generate samples of power-law degree distribution graphs with tunable assortativity.     

Fitting a geometric graph to a protein-protein interaction network

Motivation: Finding a good network null model for protein–proteininteraction (PPI) networks is a fundamental issue. Such a modelwould provide insights into the interplay between network structureand biological function as well as into evolution. Also, network(graph) models are used to guide biological experiments anddiscover new biological features. It has been proposed thatgeometric random graphs are a good model for PPI networks. Ina geometric random graph, nodes correspond to uniformly randomlydistributed points in a metric space and edges (links) existbetween pairs of nodes for which the corresponding points inthe metric space are close enough according to some distancenorm. Computational experiments have revealed close matchesbetween key topological properties of PPI networks and geometricrandom graph models. In this work, we push the comparison furtherby exploiting the fact that the geometric property can be testedfor directly. To this end, we develop an algorithm that takesPPI interaction data and embeds proteins into a low-dimensionalEuclidean space, under the premise that connectivity informationcorresponds to Euclidean proximity, as in geometric-random graphs.We judge the sensitivity and specificity of the fit by computingthe area under the Receiver Operator Characteristic (ROC) curve.The network embedding algorithm is based on multi-dimensionalscaling, with the square root of the path length in a networkplaying the role of the Euclidean distance in the Euclideanspace. The algorithm exploits sparsity for computational efficiency,and requires only a few sparse matrix multiplications, givinga complexity of O(N²) where N is the number of proteins. Results: The algorithm has been verified in the sense that itsuccessfully rediscovers the geometric structure in artificiallyconstructed geometric networks, even when noise is added byre-wiring some links. Applying the algorithm to 19 publiclyavailable PPI networks of various organisms indicated that:(a) geometric effects are present and (b) two-dimensional Euclideanspace is generally as effective as higher dimensional Euclideanspace for explaining the connectivity. Testing on a high-confidenceyeast data set produced a very strong indication of geometricstructure (area under the ROC curve of 0.89), with this networkbeing essentially indistinguishable from a noisy geometric network.Overall, the results add support to the hypothesis that PPInetworks have a geometric structure. Availability: MATLAB code implementing the algorithm is availableupon request. Contact: natasha{at}ics.uci.edu Associate Editor: Olga Troyanskaya     

Network 'small-world-ness': a quantitative method for determining canonical network equivalence

Background

Many technological, biological, social, and information networks fall into the broad class of ‘small-world’ networks: they have tightly interconnected clusters of nodes, and a shortest mean path length that is similar to a matched random graph (same number of nodes and edges). This semi-quantitative definition leads to a categorical distinction (‘small/not-small’) rather than a quantitative, continuous grading of networks, and can lead to uncertainty about a network''s small-world status. Moreover, systems described by small-world networks are often studied using an equivalent canonical network model – the Watts-Strogatz (WS) model. However, the process of establishing an equivalent WS model is imprecise and there is a pressing need to discover ways in which this equivalence may be quantified.

Methodology/Principal Findings

We defined a precise measure of ‘small-world-ness’ S based on the trade off between high local clustering and short path length. A network is now deemed a ‘small-world’ if S>1 - an assertion which may be tested statistically. We then examined the behavior of S on a large data-set of real-world systems. We found that all these systems were linked by a linear relationship between their S values and the network size n. Moreover, we show a method for assigning a unique Watts-Strogatz (WS) model to any real-world network, and show analytically that the WS models associated with our sample of networks also show linearity between S and n. Linearity between S and n is not, however, inevitable, and neither is S maximal for an arbitrary network of given size. Linearity may, however, be explained by a common limiting growth process.

Conclusions/Significance

We have shown how the notion of a small-world network may be quantified. Several key properties of the metric are described and the use of WS canonical models is placed on a more secure footing.     

Nucleoside-specific suppression in MRL/MP +/+ mice

The induction of nucleoside-specific nonresponsiveness was further studied in the autoimmune strain MRL/MP +/+ (MRL/n). Experiments were undertaken to determine (i) whether nucleoside-conjugated spleen cells are able to induce specific nonresponsiveness to T-dependent nucleoside antigens in MRL/n mice, and (ii) whether periodic treatment with nucleoside-conjugated spleen cells would retard the development of spontaneous anti-DNA antibodies and associated indicators of autoimmunity. The results show that nonresponsiveness to nucleoside antigens is inducable in male, but not in female, MRL/n mice. Nonresponsiveness in male MRL/n was transferable and mediated by T cells. Treatment of male MRL/n mice with nucleoside-conjugated spleen cells (NSC) appeared to attenuate the progress of autoimmune symptoms in experimental animals. These results are discussed in the context of recent studies exploring the etiology of autoantibody production and the loss of self-tolerance in murine models of autoimmunity.     

Topology-based abstraction of complex biological systems: application to the Golgi apparatus

Many complex cellular processes involve major changes in topology and geometry. We have developed a method using topology-based geometric modelling in which the edge labels of an n-dimensional generalized map (a subclass of graphs) represent the relations between neighbouring biological compartments. We illustrate our method using two topological models of the Golgi apparatus. These models can be animated using transformation rules, which depend on geometric and/or biochemical data and which modify both these data and the topology. Both models constitute plausible topological representations of the Golgi apparatus, but only the model based on a recent hypothesis about the Golgi apparatus is fully compatible with data from electron microscopy. Finally, we outline how our method may help biologists to choose between different hypotheses.     

Unique Optimal Foldings of Proteins on a Triangular Lattice

Background: A problem for unique protein folding was raised in 1998: are there proteins having unique optimal foldings for all lengths in the hydrophobic-hydrophilic (hydrophobic-polar; HP) model? To such a question, it was proved that on a square lattice there are (i) closed chains of monomers having unique optimal foldings for all even lengths and (ii) open monomer chains having unique optimal foldings for all lengths divisible by four. In this article, we aim to extend the previous work on a square lattice to the optimal foldings of proteins on a triangular lattice by examining the uniqueness property or stability of HP chain folding. Method: We consider this protein folding problem on a triangular lattice using graph theory. For an HP chain with length n > 13, generally it is very time-consuming to enumerate all of its possible folding conformations. Hence, one can hardly know whether or not it has a unique optimal folding. A natural problem is to determine for what value of n there is an n-node HP chain that has a unique optimal folding on a triangular lattice. Results and conclusion: Using graph theory, this article proves that there are both closed and open chains having unique optimal foldings for all lengths >19 in a triangular lattice. This result is not only general from the theoretical viewpoint, but also can be expected to apply to areas of protein structure prediction and protein design because of their close relationship with the concept of energy state and designability.     

Inhibitory effects of hybrid liposomes on the growth of synoviocyte causing rheumatoid arthritis

Inhibitory effects of HL-n composed of 95 mol % l-α-dimyristoylphosphatidylcholin (DMPC) and 5 mol % polyoxyethylenedodecylether (C₁₂(EO)_n, n = 21, 23, or 25) on the growth of human rheumatoid arthritis (RA) fibroblast-like synoviocytes (HFLS-RA) in vitro were examined. Remarkably high inhibitory effects of HL-n on the growth of HFLS-RA cells were obtained. The induction of apoptosis by HL-n was revealed on the basis of TUNEL method. Furthermore, the therapeutic effects of HL-23 using mouse models of arthritis were investigated. Therapeutic effects without joint swelling were obtained in mouse models of RA treated with HL.     

A general mathematical performance model for wormhole-switched irregular networks

Irregular topologies are desirable network structures for building scalable cluster systems and very recently they have also been employed in SoC (system-on-chip) design. Many analytical models have been proposed in the literature to evaluate the performance of networks with different topologies such as hypercube, torus, mesh, hypermesh, Cartesian product networks, star graph, and k-ary n-cube; however, to the best of our knowledge, no mathematical model has been presented for irregular networks. Therefore, as an effort to fill this gap, this paper presents a comprehensive mathematical model for fully adaptive routing in wormhole-switched irregular networks. Moreover, since our approach holds no assumption for the network topology, the proposed analytical model covers all the aforementioned models (i.e. it covers both regular and irregular topologies). Furthermore, the model makes no preliminary assumption about the deadlock-free routing algorithm applied to the network. Finally, besides the generality of the model regarding the topology and routing algorithm, our analysis shows that the analytical model exhibits high accuracy which enables it to be used for almost all topologies with all traffic loads.     

Networks, epidemics and vaccination through contact tracing

We consider a (social) network whose structure can be represented by a simple random graph having a pre-specified degree distribution. A Markovian susceptible-infectious-removed (SIR) epidemic model is defined on such a social graph. We then consider two real-time vaccination models for contact tracing during the early stages of an epidemic outbreak. The first model considers vaccination of each friend of an infectious individual (once identified) independently with probability ρ. The second model is related to the first model but also sets a bound on the maximum number an infectious individual can infect before being identified. Expressions are derived for the influence on the reproduction number of these vaccination models. We give some numerical examples and simulation results based on the Poisson and heavy-tail degree distributions where it is shown that the second vaccination model has a bigger advantage compared to the first model for the heavy-tail degree distribution.     

A Simple Algorithm for Finding All k-Edge-Connected Components

The problem of finding k-edge-connected components is a fundamental problem in computer science. Given a graph G = (V, E), the problem is to partition the vertex set V into {V ₁, V ₂,…, V _h}, where each V _i is maximized, such that for any two vertices x and y in V _i, there are k edge-disjoint paths connecting them. In this paper, we present an algorithm to solve this problem for all k. The algorithm preprocesses the input graph to construct an Auxiliary Graph to store information concerning edge-connectivity among every vertex pair in O(Fn) time, where F is the time complexity to find the maximum flow between two vertices in graph G and n = ∣V∣. For any value of k, the k-edge-connected components can then be determined by traversing the auxiliary graph in O(n) time. The input graph can be a directed or undirected, simple graph or multigraph. Previous works on this problem mainly focus on fixed value of k.     

Feasibility constraints on the elastic expansion of ecosystem models

Stable n-species ecosystem models may be expanded into larger (n + 1)-species stable models when an invading species is introduced. Such invasions are referred to as being successful due to the elasticity of the original community. Elasticity is dependent upon the interaction terms of both the original community members and the invading species. Feasibility constraints for elasticity and inelasticity are presented here for these terms in the context of a generalized ecosystem model where invasion causes only minor displacements in equilibrium population densities.     

Cooperative response of chemically excitable membrane. II. Two-state models and their limitations

Various types of two-state models, classified by the type of direct receptorionophore coupling, were formulated based on the previously presented generalized two-state model of cooperativity (Kijima &; Kijima, 1978) and their dose-response relationships were examined. Hill coefficient at the mid-point of dose-response curve n_H^o the measure of the cooperativity of curves, is restricted for partial agonists in any two-state models because n_H^o is expressed by the product of two terms, one of which decreases when the other increases. In the independent gating unit model in which the channel opens only when the independent gating units are all in the activated state, the restriction of n_H^o is the most stringent: it never exceeds 2. In 2 ÷ 1·39 even for full agonist. It appears to be incompatible with most of the cooperative responses observed on chemically excitable membrane. In the basic model or one protomer-one channel model, n_H^o never exceeds 2·0 when 〈p〉_∞, the maximum fraction of open-channel, is less than $\text{2}\text{3}$. In the cooperative gating unit model, n_H^o is the least restricted, which is less than 2·8 when 〈p〉_∞ ≤ 0·5, but if the number of gating units, N in a receptor is practically reasonably small (N ≤ 12), n_H^o ≤ 2·0 when 〈p〉_∞ ≤ 0·58. It is discussed whether or not several representative drug-receptive membranes can be accounted for by two-state models. Response of the insect sugar receptor is out of the above limitations of two-state models and can be accounted for by three-state model. The origin of cooperative interaction can be inferred by the shapes of dose-response curves. Cooperative dose-response curves of two dimensional lattices or oligomerc systems with large number of protomers weakly interacting by long range forces bend upward more markedly at lower region than the curves of strongly interacting oligomers, when curves with the same n_H^o are compared.     

Not all scale-free networks are born equal: the role of the seed graph in PPI network evolution

The (asymptotic) degree distributions of the best-known “scale-free” network models are all similar and are independent of the seed graph used; hence, it has been tempting to assume that networks generated by these models are generally similar. In this paper, we observe that several key topological features of such networks depend heavily on the specific model and the seed graph used. Furthermore, we show that starting with the “right” seed graph (typically a dense subgraph of the protein–protein interaction network analyzed), the duplication model captures many topological features of publicly available protein–protein interaction networks very well.     

An energetic evaluation of a “Smith” collagen microfibril model

An energy minimized three-dimensional structure of a collagen microfibril template was constructed based on the five-stranded model of Smith (1968), using molecular modeling methods and Kollman force fields (Weiner and Kollman, 1981). For this model, individual molecules were constructed with three identical polypeptide chains ((Gly-Pro-Pro) _n , (Gly-Prop-Hyp) _n , or (Gly-Ala-Ala) _n , wheren=4, 12, and 16) coiled into a right-handed triple-helical structure. The axial distance between adjacent amino acid residues is about 0.29 nm per polypeptide chain, and the pitch of each chain is approximately 3.3 residues. The microfibril model consists of five parallel triple helices packed so that a left-handed superhelical twist exists. The structural characteristics of the computed microfibril are consistent with those obtained for collagen by X-ray diffraction and electron microscopy. The energy minimized Smith microfibril model for (Gly-Pro-Pro)₁₂ has an axial length of about 10.2 nm (for a 36 amino acid residue chain), which gives an estimated D-spacing (234 amino acids per chain) of approximately 66.2 nm. Studies of the microfibril models (Gly-Pro-Pro)₁₂, (Gly-Pro-Hyp)₁₂, and (Gly-Ala-Ala)₁₂ show that nonbonded van der Waals interactions are important for microfibril formation, while electrostatic interactions contribute to the stability of the microfibril structure and determine the specificity by which collagen molecules pack within the microfibril.     

n − 3, but not n − 6 lipid particle uptake requires cell surface anchoring

Omega-3 (n − 3) fatty acids are emerging as bioactive agents protective against cardiovascular disease. However, their cellular delivery pathways are poorly defined. Here we questioned whether the uptake of n − 3 triglyceride-rich particles (TGRP) is mediated by cell surface proteoglycans (PG) using LDL receptor (LDLR)+/+ and LDLR−/− cell models. LDLR+/+ but not LDLR−/− cells showed higher n − 6 over n − 3 TGRP uptake. Removal of cell surface proteins and receptors by pronase markedly enhanced the uptake of n − 3 but not n − 6 TGRP. Lactoferrin blockage of apoE-mediated pathways decreased the uptake of n − 6 TGRP by up to 85% (p < 0.05) but had insignificant effect on n − 3 TGRP uptake. PG removal by sodium chlorate in LDLR+/+ cells substantially reduced n − 3 TGRP uptake but had little effect on n − 6 TGRP uptake. Thus, while n − 6 TGRP uptake is preferentially mediated by LDLR-dependent pathways, the uptake of n − 3 TGRP depends more on PG and non-LDLR cell surface anchoring.     

Cole-Moore superposition and kinetic models for the potassium conductance of nerve fiber membranes

Restrictions imposed by “Cole-Moore superposition” on a class of models for the potassium conductance of nerve fiber membranes are studied. The models studied assume that: (1) different potassium transfer sites on the membrane are not coupled; (2) each site is characterized by a set of states |α>, α = 0, …, N, each of energy E_α, and degeneracy, r_α. (3) The time dependence is described by kinetic equations.It is rigorously shown that: (a) there is superposition if, and only if, in going from one equilibrium state to another, the system passes only through equilibrium states. (b) Condition (a) is satisfied only if: (i) the energy levels are equally spaced, (ii) the state |n> is [N!/n!(N-n)!]-fold degenerate, and (iii) only transitions between nearest neighbor levels are allowed.     

Interference in Genetic Crossing over and Chromosome Mapping

This paper proposes a general model for interference in genetic crossing over. The model assumes serial occurrence of chiasmata, visualized as a renewal process along the paired (or pairing) chromosomes. This process is described as an underlying Poisson process in which the 1st, n + 1th, 2n + 1th, etc., events are to be interpreted as realized chiasmata. Chromatid interference is described in terms of the probabilities that two successive chiasmata involve two, three or four different chromatids. Several characteristics of this model, e.g., the cytological and genetic mapping function and the density of chiasmata along the chromosomes, are discussed. Some aspects of other interference models are briefly discussed.     

Comparative Study of Injury Models for Studying Muscle Regeneration in Mice

Background

A longstanding goal in regenerative medicine is to reconstitute functional tissus or organs after injury or disease. Attention has focused on the identification and relative contribution of tissue specific stem cells to the regeneration process. Relatively little is known about how the physiological process is regulated by other tissue constituents. Numerous injury models are used to investigate tissue regeneration, however, these models are often poorly understood. Specifically, for skeletal muscle regeneration several models are reported in the literature, yet the relative impact on muscle physiology and the distinct cells types have not been extensively characterised.

Methods

We have used transgenic Tg:Pax7nGFP and Flk1^GFP/+ mouse models to respectively count the number of muscle stem (satellite) cells (SC) and number/shape of vessels by confocal microscopy. We performed histological and immunostainings to assess the differences in the key regeneration steps. Infiltration of immune cells, chemokines and cytokines production was assessed in vivo by Luminex^®.

Results

We compared the 4 most commonly used injury models i.e. freeze injury (FI), barium chloride (BaCl₂), notexin (NTX) and cardiotoxin (CTX). The FI was the most damaging. In this model, up to 96% of the SCs are destroyed with their surrounding environment (basal lamina and vasculature) leaving a “dead zone” devoid of viable cells. The regeneration process itself is fulfilled in all 4 models with virtually no fibrosis 28 days post-injury, except in the FI model. Inflammatory cells return to basal levels in the CTX, BaCl₂ but still significantly high 1-month post-injury in the FI and NTX models. Interestingly the number of SC returned to normal only in the FI, 1-month post-injury, with SCs that are still cycling up to 3-months after the induction of the injury in the other models.

Conclusions

Our studies show that the nature of the injury model should be chosen carefully depending on the experimental design and desired outcome. Although in all models the muscle regenerates completely, the trajectories of the regenerative process vary considerably. Furthermore, we show that histological parameters are not wholly sufficient to declare that regeneration is complete as molecular alterations (e.g. cycling SCs, cytokines) could have a major persistent impact.     

Loss of FADS2 Function Severely Impairs the Use of HeLa Cells as an In Vitro Model for Host Response Studies Involving Fatty Acid Effects

Scope

Established epithelial cell lines equipped with pattern recognition receptors such as the Toll-like receptor (TLR)-2 are common tools for immune response studies on invading pathogens, e.g. the obligate intracellular species of Chlamydia. Moreover, such models are widely used to elucidate fatty acid-mediated immune effects. In several transformed cell lines, however, unusual loss of metabolic functions was described. The cell lines A549 and HeLa are poorly characterized in this respect. Therefore, we comparatively assessed the metabolic capacity of A549 and HeLa prior to proposed application as in vitro model for fatty acid effects on chlamydial infection.

Methodology/Principal Findings

We incubated both cell lines either with substrates (C18∶2n−6 or C18∶3n−3) or products (C18∶3n−6, C18∶4n−3) of fatty acid desaturase-2 (FADS2), and analysed the fatty acid profiles after 24 h and 72 h by gas chromatography. Based on these data, we suspected that the complete discontinuation of normal biosynthesis of long-chain polyunsaturated fatty acids (LC-PUFA) in HeLa was due to loss of FADS2 function. Consequently, prostaglandin E2 (PGE2) formation was less inducible by TLR2 stimulation in HeLa, likely as a result of not only insufficient supply of precursors but also weak cyclooxygenase-2 (COX-2) response. In accordance, Chlamydia infection rates were consistently lower in HeLa than in A549. Sequence analysis revealed no alteration within the FADS2 gene in HeLa. The FADS2 expression level, however, was significantly lower and, in contrast to A549, not regulated by C18∶2n−6. A549 exhibited regular fatty acid metabolism and enzyme functionality.

Conclusions/Significance

Our data show that HeLa cells considerably differ from A549 at several stages of fatty acid metabolism. The poor metabolic potential of HeLa, mainly concerning FADS2 upstream of COX-2 function, calls into question whether these cells represent a good model to unveil fatty acid or downstream eicosanoid effects in the course of intracellular bacterial infection.