On some metric properties of the systems of compartments

Rules for the enumeration of the strong components of a graph and for the calculation of its variable adjacency matrix are presented. A new method is given to calculate the transfer function of a graphy by analyzing the strong components of the graph, the elementary paths between two nodes, and the linear subgraphs.     

On some metric properties of the systems of compartments

Rules for the enumeration of the strong components of a graph and for the calculation of its variable adjacency matrix are presented. A new method is given to calculate the transfer function of a graphy by analyzing the strong components of the graph, the elementary paths between two nodes, and the linear subgraphs. This work was supported in part by the United States Atomic Energy Commission and the National Aeronautics and Space Administration.     

A Framework of Algorithms: Computing the Bias and Prestige of Nodes in Trust Networks

A trust network is a social network in which edges represent the trust relationship between two nodes in the network. In a trust network, a fundamental question is how to assess and compute the bias and prestige of the nodes, where the bias of a node measures the trustworthiness of a node and the prestige of a node measures the importance of the node. The larger bias of a node implies the lower trustworthiness of the node, and the larger prestige of a node implies the higher importance of the node. In this paper, we define a vector-valued contractive function to characterize the bias vector which results in a rich family of bias measurements, and we propose a framework of algorithms for computing the bias and prestige of nodes in trust networks. Based on our framework, we develop four algorithms that can calculate the bias and prestige of nodes effectively and robustly. The time and space complexities of all our algorithms are linear with respect to the size of the graph, thus our algorithms are scalable to handle large datasets. We evaluate our algorithms using five real datasets. The experimental results demonstrate the effectiveness, robustness, and scalability of our algorithms.     

Network of evolutionary processors with splicing rules and permitting context

In this paper we consider networks of evolutionary processors with splicing rules and permitting context (NEPPS) as language generating and computational devices. Such a network consists of several processors placed on the nodes of a virtual graph and are able to perform splicing (which is a biologically motivated operation) on the words present in that node, according to the splicing rules present there. Before applying the splicing operation on words, we check for the presence of certain symbols (permitting context) in the strings on which the rule is applied. Each node is associated with an input and output filter. When the filters are based on random context conditions, one gets the computational power of Turing machines with networks of size two. We also show how these networks can be used to solve NP-complete problems in linear time.     

Chokepoints in Mechanical Coupling Associated with Allosteric Proteins: The Pyruvate Kinase Example

Although the critical role of allostery in controlling enzymatic processes is well appreciated, there is a current dearth in our understanding of its underlying mechanisms, including communication between binding sites. One potential key aspect of intersite communication is the mechanical coupling between residues in a protein. Here, we introduce a graph-based computational approach to investigate the mechanical coupling between distant parts of a protein, highlighting effective pathways via which protein motion can transfer energy between sites. In this method, each residue is treated as a node on a weighted, undirected graph, in which the edges are defined by locally correlated motions of those residues and weighted by the strength of the correlation. The method was validated against experimental data on allosteric regulation in the human liver pyruvate kinase as obtained from full-protein alanine-scanning mutagenesis (systematic mutation) studies, as well as computational data on two G-protein-coupled receptors. The method provides semiquantitative information on the regulatory importance of specific structural elements. It is shown that these elements are key for the mechanical coupling between distant parts of the protein by providing effective pathways for energy transfer. It is also shown that, although there are a multitude of energy transfer pathways between distant parts of a protein, these pathways share a few common nodes that represent effective “chokepoints” for the communication.     

Connectivity and information transfer in flow networks: Two magic numbers in ecology?

An ecosystem can be visualized as a graph of certain preassigned trophic compartments; these nodes are then mutually connected through the internal exchanges of material and energy. The mathematical theory of information can be applied to such a graph in order to define two relevant indices: a measure of connectivity (the entropy H of the connections) and a measure of the degree of the “energetic” specialization (the internal transfer of informationI). The computation of these indices in stationary real cases suggests that the observed complexity of ecosystems is conditioned by two competing effects. The first can be interpreted as a “thermodynamical” principle related to the unavoidable irreversibility taking place inside the system, whereas the second can be taken as a “biological” principle concerned with the selection of some particular interactions: those which maximize the information circulating between the compartments.     

Prediction of lethal and synthetically lethal knock-outs in regulatory networks

The complex interactions involved in regulation of a cell’s function are captured by its interaction graph. More often than not, detailed knowledge about enhancing or suppressive regulatory influences and cooperative effects is lacking and merely the presence or absence of directed interactions is known. Here, we investigate to which extent such reduced information allows to forecast the effect of a knock-out or a combination of knock-outs. Specifically, we ask in how far the lethality of eliminating nodes may be predicted by their network centrality, such as degree and betweenness, without knowing the function of the system. The function is taken as the ability to reproduce a fixed point under a discrete Boolean dynamics. We investigate two types of stochastically generated networks: fully random networks and structures grown with a mechanism of node duplication and subsequent divergence of interactions. On all networks we find that the out-degree is a good predictor of the lethality of a single node knock-out. For knock-outs of node pairs, the fraction of successors shared between the two knocked-out nodes (out-overlap) is a good predictor of synthetic lethality. Out-degree and out-overlap are locally defined and computationally simple centrality measures that provide a predictive power close to the optimal predictor.     

An Algorithm to Automatically Generate the Combinatorial Orbit Counting Equations

Graphlets are small subgraphs, usually containing up to five vertices, that can be found in a larger graph. Identification of the graphlets that a vertex in an explored graph touches can provide useful information about the local structure of the graph around that vertex. Actually finding all graphlets in a large graph can be time-consuming, however. As the graphlets grow in size, more different graphlets emerge and the time needed to find each graphlet also scales up. If it is not needed to find each instance of each graphlet, but knowing the number of graphlets touching each node of the graph suffices, the problem is less hard. Previous research shows a way to simplify counting the graphlets: instead of looking for the graphlets needed, smaller graphlets are searched, as well as the number of common neighbors of vertices. Solving a system of equations then gives the number of times a vertex is part of each graphlet of the desired size. However, until now, equations only exist to count graphlets with 4 or 5 nodes. In this paper, two new techniques are presented. The first allows to generate the equations needed in an automatic way. This eliminates the tedious work needed to do so manually each time an extra node is added to the graphlets. The technique is independent on the number of nodes in the graphlets and can thus be used to count larger graphlets than previously possible. The second technique gives all graphlets a unique ordering which is easily extended to name graphlets of any size. Both techniques were used to generate equations to count graphlets with 4, 5 and 6 vertices, which extends all previous results. Code can be found at https://github.com/IneMelckenbeeck/equation-generator and https://github.com/IneMelckenbeeck/graphlet-naming.     

Information Transfer and Criticality in the Ising Model on the Human Connectome

We implement the Ising model on a structural connectivity matrix describing the brain at two different resolutions. Tuning the model temperature to its critical value, i.e. at the susceptibility peak, we find a maximal amount of total information transfer between the spin variables. At this point the amount of information that can be redistributed by some nodes reaches a limit and the net dynamics exhibits signature of the law of diminishing marginal returns, a fundamental principle connected to saturated levels of production. Our results extend the recent analysis of dynamical oscillators models on the connectome structure, taking into account lagged and directional influences, focusing only on the nodes that are more prone to became bottlenecks of information. The ratio between the outgoing and the incoming information at each node is related to the the sum of the weights to that node and to the average time between consecutive time flips of spins. The results for the connectome of 66 nodes and for that of 998 nodes are similar, thus suggesting that these properties are scale-independent. Finally, we also find that the brain dynamics at criticality is organized maximally to a rich-club w.r.t. the network of information flows.     

Planning and Sequencing Heuristics for Feature-Based Control of Holonic Machining Equipment

The intelligent manufacturing system program was proposed by Japan in 1989. Five participating regions—Australia, Canada, the European Community, Japan, and the United States—currently are involved in developing 21st century manufacturing technology through an investment of US $1.2 billion over 10 years. Korea joined the program and will start work on one of the six ongoing projects, holonic manufacturing systems (HMSs). The objective of the paper is to develop the control architecture of the holonic machining unit (HMU) for construction of the HMSs and to present some planning and sequencing heuristics for feature-based control of the HMU. Further, the paper provides the HMU's functionality using the IDEF0 function modeling method. The basic operation of the decision maker among the HMU's functions is to determine an efficient feature sequence in real time from the nonlinear feature graph used to represent a process plan. To this end, two methodologies are applied sequentially to managing a nonlinear process plan: removal of the OR nodes and then grouping and sequencing the features in the feature graph. Markov chain theory is used to compute the path preference indicator for removing the OR nodes, that is, for selecting the best path among those surrounded by OR nodes. The resulting graph is the AND graph, from which the feature type nodes are formed into sequenced groups. The CNC codes associated with the features in each group are combined and downloaded to the CNC machine. The development of the methodologies can help manufacturers efficiently cope with unexpected failures encountered during computer-automated machining.     

A grid layout algorithm for automatic drawing of biochemical networks

MOTIVATION: Visualization is indispensable in the research of complex biochemical networks. Available graph layout algorithms are not adequate for satisfactorily drawing such networks. New methods are required to visualize automatically the topological architectures and facilitate the understanding of the functions of the networks. RESULTS: We propose a novel layout algorithm to draw complex biochemical networks. A network is modeled as a system of interacting nodes on squared grids. A discrete cost function between each node pair is designed based on the topological relation and the geometric positions of the two nodes. The layouts are produced by minimizing the total cost. We design a fast algorithm to minimize the discrete cost function, by which candidate layouts can be produced efficiently. A simulated annealing procedure is used to choose better candidates. Our algorithm demonstrates its ability to exhibit cluster structures clearly in relatively compact layout areas without any prior knowledge. We developed Windows software to implement the algorithm for CADLIVE. AVAILABILITY: All materials can be freely downloaded from http://kurata21.bio.kyutech.ac.jp/grid/grid_layout.htm; http://www.cadlive.jp/ SUPPLEMENTARY INFORMATION: http://kurata21.bio.kyutech.ac.jp/grid/grid_layout.htm; http://www.cadlive.jp/     

Robust Spectral Clustering Using Statistical Sub-Graph Affinity Model

Spectral clustering methods have been shown to be effective for image segmentation. Unfortunately, the presence of image noise as well as textural characteristics can have a significant negative effect on the segmentation performance. To accommodate for image noise and textural characteristics, this study introduces the concept of sub-graph affinity, where each node in the primary graph is modeled as a sub-graph characterizing the neighborhood surrounding the node. The statistical sub-graph affinity matrix is then constructed based on the statistical relationships between sub-graphs of connected nodes in the primary graph, thus counteracting the uncertainty associated with the image noise and textural characteristics by utilizing more information than traditional spectral clustering methods. Experiments using both synthetic and natural images under various levels of noise contamination demonstrate that the proposed approach can achieve improved segmentation performance when compared to existing spectral clustering methods.     

Quantitative inheritance in pea: lines with several mutant genes for the number of sterile nodes

The number of sterile nodes of 81 families of nonfasciated recombinants derived from hybrids between fasciated and nonfasciated lines, are compared with those of 17 control groups consisting of homozygous plants only. As the homozygous lines and recombinants usually show the low variation of only±1 sterile node with standard deviations (SD) of 0.25 to maximally 0.83, a minimum number of four genes was deduced from the 14 clearly distinguishable phenotypes obtained by recombination. Further recombinants with statistical mean values between the ones already obtained can possibly be derived from these fasciated mutants. A more optimistic prognosis (taking into account also the ratios of segregating to nonsegregating plants in random samples of several succeeding generations) would suggest 5 to 6 mutant genes, but some results point to a mutator gene repeatedly generating several phenotypes.     

On the distribution of the general irreversiblen-compartmental model having time-dependent transition probabilities

The cumulant generating function and first two moments are derived for the stochastic distribution of units in a general irreversiblen-compartment model with time-dependent transition probabilities. In this model, a unit in the first compartment can transfer to any one of the remainingn−1 compartments and a unit in the second compartment can transfer to any of the remainingn−2 compartments and so on. In addition, a unit can enter or leave the system through any compartment. The work is related to previous research and a numerical example is given.     

Frequency Response and Gap Tuning for Nonlinear Electrical Oscillator Networks

We study nonlinear electrical oscillator networks, the smallest example of which consists of a voltage-dependent capacitor, an inductor, and a resistor driven by a pure tone source. By allowing the network topology to be that of any connected graph, such circuits generalize spatially discrete nonlinear transmission lines/lattices that have proven useful in high-frequency analog devices. For such networks, we develop two algorithms to compute the steady-state response when a subset of nodes are driven at the same fixed frequency. The algorithms we devise are orders of magnitude more accurate and efficient than stepping towards the steady-state using a standard numerical integrator. We seek to enhance a given network''s nonlinear behavior by altering the eigenvalues of the graph Laplacian, i.e., the resonances of the linearized system. We develop a Newton-type method that solves for the network inductances such that the graph Laplacian achieves a desired set of eigenvalues; this method enables one to move the eigenvalues while keeping the network topology fixed. Running numerical experiments using three different random graph models, we show that shrinking the gap between the graph Laplacian''s first two eigenvalues dramatically improves a network''s ability to (i) transfer energy to higher harmonics, and (ii) generate large-amplitude signals. Our results shed light on the relationship between a network''s structure, encoded by the graph Laplacian, and its function, defined in this case by the presence of strongly nonlinear effects in the frequency response.     

Subvoxel Accurate Graph Search Using Non-Euclidean Graph Space

Graph search is attractive for the quantitative analysis of volumetric medical images, and especially for layered tissues, because it allows globally optimal solutions in low-order polynomial time. However, because nodes of graphs typically encode evenly distributed voxels of the volume with arcs connecting orthogonally sampled voxels in Euclidean space, segmentation cannot achieve greater precision than a single unit, i.e. the distance between two adjoining nodes, and partial volume effects are ignored. We generalize the graph to non-Euclidean space by allowing non-equidistant spacing between nodes, so that subvoxel accurate segmentation is achievable. Because the number of nodes and edges in the graph remains the same, running time and memory use are similar, while all the advantages of graph search, including global optimality and computational efficiency, are retained. A deformation field calculated from the volume data adaptively changes regional node density so that node density varies with the inverse of the expected cost. We validated our approach using optical coherence tomography (OCT) images of the retina and 3-D MR of the arterial wall, and achieved statistically significant increased accuracy. Our approach allows improved accuracy in volume data acquired with the same hardware, and also, preserved accuracy with lower resolution, more cost-effective, image acquisition equipment. The method is not limited to any specific imaging modality and readily extensible to higher dimensions.     

Antigen modulation of the immune response. V. Generation of large memory cells in antigen draining lymph nodes.

We have studied the distribution of memory B cell subpopulations by using 1g velocity sedimentation and adoptive transfer. When the non-antigen-draining mesenteric lymph nodes were examined 4 weeks after intraperitoneal immunization with DNPBGG, large memory cells were present in only very low numbers. However, when the draining parathymic nodes were removed, a significant enrichment of large memory cell activity was seen. When these results were corrected for the cell yields in each 1g separated fraction we found that 59% of the total memory cells were small, 36% medium and 5% large in the mesenteric lymph node preparations and 40% were small, 46% medium and 14% large in the parathymic lymph node suspensions. When popliteal lymph nodes were removed after footpad immunization, 32% of the total memory cell activity was in the small cell fraction while 49% was in the medium fraction and 18% in the large cell fraction. Control experiments were also run to show that the shift in the velocity sedimentation profile of the various memory cell populations was not an artifact of the adoptive transfer system nor a result of selective antigen triggering.From these results it would appear that the size distribution of memory cells depends upon the source of cells studied, large memory cells being found predominantly only in lymph nodes draining the site of antigen injection. Since the large memory cells can also be found in the thoracic duct lymph after footpad immunization but not after intraperitoneal immunization, it is suggested that the larger cells can circulate to other lymphoid tissues but cannot recirculate.     

TSAR,a new graph–theoretical approach to computational modeling of protein side‐chain flexibility: Modeling of ionization properties of proteins

A new graph–theoretical approach called thermodynamic sampling of amino acid residues (TSAR) has been elaborated to explicitly account for the protein side chain flexibility in modeling conformation‐dependent protein properties. In TSAR, a protein is viewed as a graph whose nodes correspond to structurally independent groups and whose edges connect the interacting groups. Each node has its set of states describing conformation and ionization of the group, and each edge is assigned an array of pairwise interaction potentials between the adjacent groups. By treating the obtained graph as a belief‐network—a well‐established mathematical abstraction—the partition function of each node is found. In the current work we used TSAR to calculate partition functions of the ionized forms of protein residues. A simplified version of a semi‐empirical molecular mechanical scoring function, borrowed from our Lead Finder docking software, was used for energy calculations. The accuracy of the resulting model was validated on a set of 486 experimentally determined pK_a values of protein residues. The average correlation coefficient (R) between calculated and experimental pK_a values was 0.80, ranging from 0.95 (for Tyr) to 0.61 (for Lys). It appeared that the hydrogen bond interactions and the exhaustiveness of side chain sampling made the most significant contribution to the accuracy of pK_a calculations. Proteins 2011; © 2011 Wiley‐Liss, Inc.     

Cube-Cut: Vertebral Body Segmentation in MRI-Data through Cubic-Shaped Divergences

In this article, we present a graph-based method using a cubic template for volumetric segmentation of vertebrae in magnetic resonance imaging (MRI) acquisitions. The user can define the degree of deviation from a regular cube via a smoothness value Δ. The Cube-Cut algorithm generates a directed graph with two terminal nodes (s-t-network), where the nodes of the graph correspond to a cubic-shaped subset of the image’s voxels. The weightings of the graph’s terminal edges, which connect every node with a virtual source s or a virtual sink t, represent the affinity of a voxel to the vertebra (source) and to the background (sink). Furthermore, a set of infinite weighted and non-terminal edges implements the smoothness term. After graph construction, a minimal s-t-cut is calculated within polynomial computation time, which splits the nodes into two disjoint units. Subsequently, the segmentation result is determined out of the source-set. A quantitative evaluation of a C++ implementation of the algorithm resulted in an average Dice Similarity Coefficient (DSC) of 81.33% and a running time of less than a minute.