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.     

Mathematical modeling of the malignancy of cancer using graph evolution

We report a novel computational method based on graph evolution process to model the malignancy of brain cancer called glioma. In this work, we analyze the phases that a graph passes through during its evolution and demonstrate strong relation between the malignancy of cancer and the phase of its graph. From the photomicrographs of tissues, which are diagnosed as normal, low-grade cancerous and high-grade cancerous, we construct cell-graphs based on the locations of cells; we probabilistically generate an edge between every pair of cells depending on the Euclidean distance between them. For a cell-graph, we extract connectivity information including the properties of its connected components in order to analyze the phase of the cell-graph. Working with brain tissue samples surgically removed from 12 patients, we demonstrate that cell-graphs generated for different tissue types evolve differently and that they exhibit different phase properties, which distinguish a tissue type from another.     

Why everything is connected to everything else

In Earth surface systems (ESS), everything is connected to everything else, an aphorism often called the First Law of Ecology and of geography. Such linkages are not always direct and unmediated, but many ESS, represented as networks of interacting components, attain or approach full, direct connectivity among components. The question is how and why this happens at the system or network scale. The crowded landscape concept dictates that linkages and connections among ESS components are inevitable. The connection selection concept holds that the linkages among components are (often) advantageous to the network and are selected for, and thereby preserved and enhanced. These network advantages are illustrated via algebraic graph theory. For a given number of components in an ESS, as the number of links or connections increases, spectral radius, graph energy, and algebraic connectivity increase. While the advantages (if any) of increased complexity are unclear, higher spectral radii are directly correlated with higher graph energy. The greater graph energy is associated with more intense feedback in the system, and tighter coupling among components. This in turn reflects advantageous properties of more intense cycling of water, nutrients, and minerals, as well as multiple potential degrees of freedom for individual components to respond to changes. The increase of algebraic connectivity reflects a greater ability or tendency for the network to respond to changes in concert.     

Clique-based data mining for related genes in a biomedical database

Background  

Progress in the life sciences cannot be made without integrating biomedical knowledge on numerous genes in order to help formulate hypotheses on the genetic mechanisms behind various biological phenomena, including diseases. There is thus a strong need for a way to automatically and comprehensively search from biomedical databases for related genes, such as genes in the same families and genes encoding components of the same pathways. Here we address the extraction of related genes by searching for densely-connected subgraphs, which are modeled as cliques, in a biomedical relational graph.     

Laplacian Eigenfunctions Learn Population Structure

Principal components analysis has been used for decades to summarize genetic variation across geographic regions and to infer population migration history. More recently, with the advent of genome-wide association studies of complex traits, it has become a commonly-used tool for detection and correction of confounding due to population structure. However, principal components are generally sensitive to outliers. Recently there has also been concern about its interpretation. Motivated from geometric learning, we describe a method based on spectral graph theory. Regarding each study subject as a node with suitably defined weights for its edges to close neighbors, one can form a weighted graph. We suggest using the spectrum of the associated graph Laplacian operator, namely, Laplacian eigenfunctions, to infer population structure. In simulations and real data on a ring species of birds, Laplacian eigenfunctions reveal more meaningful and less noisy structure of the underlying population, compared with principal components. The proposed approach is simple and computationally fast. It is expected to become a promising and basic method for population genetics and disease association studies.     

Signalling Network Construction for Modelling Plant Defence Response

Plant defence signalling response against various pathogens, including viruses, is a complex phenomenon. In resistant interaction a plant cell perceives the pathogen signal, transduces it within the cell and performs a reprogramming of the cell metabolism leading to the pathogen replication arrest. This work focuses on signalling pathways crucial for the plant defence response, i.e., the salicylic acid, jasmonic acid and ethylene signal transduction pathways, in the Arabidopsis thaliana model plant. The initial signalling network topology was constructed manually by defining the representation formalism, encoding the information from public databases and literature, and composing a pathway diagram. The manually constructed network structure consists of 175 components and 387 reactions. In order to complement the network topology with possibly missing relations, a new approach to automated information extraction from biological literature was developed. This approach, named Bio3graph, allows for automated extraction of biological relations from the literature, resulting in a set of (component1, reaction, component2) triplets and composing a graph structure which can be visualised, compared to the manually constructed topology and examined by the experts. Using a plant defence response vocabulary of components and reaction types, Bio3graph was applied to a set of 9,586 relevant full text articles, resulting in 137 newly detected reactions between the components. Finally, the manually constructed topology and the new reactions were merged to form a network structure consisting of 175 components and 524 reactions. The resulting pathway diagram of plant defence signalling represents a valuable source for further computational modelling and interpretation of omics data. The developed Bio3graph approach, implemented as an executable language processing and graph visualisation workflow, is publically available at http://ropot.ijs.si/bio3graph/and can be utilised for modelling other biological systems, given that an adequate vocabulary is provided.     

中国地方品种鸡的分类研究

中国鸡种资源极为丰富,中国历史上形成的许多优良地方品种鸡,对中国养鸡事业发展和世界养鸡业都曾做出过重要贡献。为充分利用我国地方鸡种资源遗传潜力和杂种优势,本文利用图论主成分分类法与系统聚类法根据20项指标研究了中国30个地方品种鸡的分类问题,分类结果比较符合实际,特别是图论主成分分类图直观清楚,生物学含意明确,对中国鸡种资源和基因库的利用有实际参考价值。     

RNA Graph Partitioning for the Discovery of RNA Modularity: A Novel Application of Graph Partition Algorithm to Biology

Graph representations have been widely used to analyze and design various economic, social, military, political, and biological networks. In systems biology, networks of cells and organs are useful for understanding disease and medical treatments and, in structural biology, structures of molecules can be described, including RNA structures. In our RNA-As-Graphs (RAG) framework, we represent RNA structures as tree graphs by translating unpaired regions into vertices and helices into edges. Here we explore the modularity of RNA structures by applying graph partitioning known in graph theory to divide an RNA graph into subgraphs. To our knowledge, this is the first application of graph partitioning to biology, and the results suggest a systematic approach for modular design in general. The graph partitioning algorithms utilize mathematical properties of the Laplacian eigenvector (µ2) corresponding to the second eigenvalues (λ2) associated with the topology matrix defining the graph: λ2 describes the overall topology, and the sum of µ2′s components is zero. The three types of algorithms, termed median, sign, and gap cuts, divide a graph by determining nodes of cut by median, zero, and largest gap of µ2′s components, respectively. We apply these algorithms to 45 graphs corresponding to all solved RNA structures up through 11 vertices (∼220 nucleotides). While we observe that the median cut divides a graph into two similar-sized subgraphs, the sign and gap cuts partition a graph into two topologically-distinct subgraphs. We find that the gap cut produces the best biologically-relevant partitioning for RNA because it divides RNAs at less stable connections while maintaining junctions intact. The iterative gap cuts suggest basic modules and assembly protocols to design large RNA structures. Our graph substructuring thus suggests a systematic approach to explore the modularity of biological networks. In our applications to RNA structures, subgraphs also suggest design strategies for novel RNA motifs.     

A linear-time algorithm for computing inversion distance between signed permutations with an experimental study.

Hannenhalli and Pevzner gave the first polynomial-time algorithm for computing the inversion distance between two signed permutations, as part of the larger task of determining the shortest sequence of inversions needed to transform one permutation into the other. Their algorithm (restricted to distance calculation) proceeds in two stages: in the first stage, the overlap graph induced by the permutation is decomposed into connected components; then, in the second stage, certain graph structures (hurdles and others) are identified. Berman and Hannenhalli avoided the explicit computation of the overlap graph and gave an O(nalpha(n)) algorithm, based on a Union-Find structure, to find its connected components, where alpha is the inverse Ackerman function. Since for all practical purposes alpha(n) is a constant no larger than four, this algorithm has been the fastest practical algorithm to date. In this paper, we present a new linear-time algorithm for computing the connected components, which is more efficient than that of Berman and Hannenhalli in both theory and practice. Our algorithm uses only a stack and is very easy to implement. We give the results of computational experiments over a large range of permutation pairs produced through simulated evolution; our experiments show a speed-up by a factor of 2 to 5 in the computation of the connected components and by a factor of 1.3 to 2 in the overall distance computation.     

Easy methods to study the smart energetic TNT/CL-20 co-crystal

2,4,6,8,10,12-hexanitro-2,4,6,8,10,12-hexaazaisowurtzitane (CL-20) is a high-energy nitramine explosive with high mechanical sensitivity. 2,4,6-trinitrotoluene (TNT) is insensitive but by no means a high performance explosive. To reveal the significant importance and smart-material functionality of the energetic-energetic co-crystals, the stability, mechanical and explosive properties TNT/CL-20 co-crystal, TNT crystal and CL-20 crystal were studied. Non-hydrogen bonded non-covalent interactions govern the structures of energetic-energetic co-crystals. However, it is very difficult to accurately calculate the non-covalent intermolecular interaction energies. In this paper, the local conformation and the intricate non-covalent interactions were effectively mapped and analyzed from the electron density (ρ) and its derivatives. The results show that the two components TNT and CL-20 are connected mainly by nitro–aromatic interactions, and nitro–nitro interactions. The steric interactions in TNT/CL-20 could not be confronted with the attractive interactions. Moreover, the scatter graph of TNT crystal reveals the reason why TNT is brittle. The detailed electrostatic potential analysis predicted that the detonation velocities (D) and impact sensitivity for the compounds both increase in the sequence of CL-20 > TNT/CL-20 co-crystal > TNT. Additionally, TNT/CL-20 co-crystal has better malleability than its pure components. This demonstrates the capacity and the feasibility of realizing explosive smart materials by co-crystallization, even if strong hydrogen bonding schemes are generally lacking in energetic materials.

A unified representation of multiprotein complex data for modeling interaction networks

The protein interaction network presents one perspective for understanding cellular processes. Recent experiments employing high-throughput mass spectrometric characterizations have resulted in large data sets of physiologically relevant multiprotein complexes. We present a unified representation of such data sets based on an underlying bipartite graph model that is an advance over existing models of the network. Our unified representation allows for weighting of connections between proteins shared in more than one complex, as well as addressing the higher level organization that occurs when the network is viewed as consisting of protein complexes that share components. This representation also allows for the application of the rigorous MinMaxCut graph clustering algorithm for the determination of relevant protein modules in the networks. Statistically significant annotations of clusters in the protein-protein and complex-complex networks using terms from the Gene Ontology indicate that this method will be useful for posing hypotheses about uncharacterized components of protein complexes or uncharacterized relationships between protein complexes.     

Taxonomy with confidence

There are essentially three ways in which four species may be related in a phylogenetic tree graph. It is usual to compute for each of these three possibilities the smallest number of mutations that could have brought about the observed distribution of characteristics among the four species. The graph that minimizes this number is then preferred. In fact, the hypothesis that the graph chosen in this way is correct may be accepted with confidence if the minimum is strong in a sense described here. In principle, the theory could be extended to treat sets of more than four species.     

Identification of side-chain clusters in protein structures by a graph spectral method.

This paper presents a novel method to detect side-chain clusters in protein three-dimensional structures using a graph spectral approach. Protein side-chain interactions are represented by a labeled graph in which the nodes of the graph represent the Cbeta atoms and the edges represent the distance between the Cbeta atoms. The distance information and the non-bonded connectivity of the residues are represented in the form of a matrix called the Laplacian matrix. The constructed matrix is diagonalized and clustering information is obtained from the vector components associated with the second lowest eigenvalue and cluster centers are obtained from the vector components associated with the top eigenvalues. The method uses global information for clustering and a single numeric computation is required to detect clusters of interest. The approach has been adopted here to detect a variety of side-chain clusters and identify the residue which makes the largest number of interactions among the residues forming the cluster (cluster centers). Detecting such clusters and cluster centers are important from a protein structure and folding point of view. The crucial residues which are important in the folding pathway as determined by PhiF values (which is a measure of the effect of a mutation on the stability of the transition state of folding) as obtained from protein engineering methods, can be identified from the vector components corresponding to the top eigenvalues. Expanded clusters are detected near the active and binding site of the protein, supporting the nucleation condensation hypothesis for folding. The method is also shown to detect domains in protein structures and conserved side-chain clusters in topologically similar proteins.     

土壤动物知识图谱构建理论、方法与技术——以浙江天目山土壤螨类为例

土壤动物学面临以全新知识体系为科学研究框架的变革时期,其核心内容是以数据驱动为主要特征的人工智能技术方法。目前广泛应用的基于数据库的数据处理分析方法,面临着数据多源异构、快速增长和处理能力不足之间的矛盾。基于快速发展的大数据科学和人工智能技术的数据挖掘方法在解决前述矛盾中有突出优势,但需要依赖一个强大的领域知识库,然而土壤动物领域知识图谱的研究十分匮乏。土壤动物知识图谱是一个具有有向图结构的知识库,其中图的节点代表与土壤动物相关的实体或概念,图的边代表实体或概念之间的各种语义关系。提出了土壤动物知识图谱的定义、内涵、理论模型和构建方法,以浙江天目山土壤螨类多样性为例,分析了构建山地土壤动物知识图谱的技术方法;以土壤动物多样性研究关注的物种分布、物种共存、环境条件对物种的影响作用为例,探讨了基于山地土壤动物知识图谱可以解决的相关科学问题。研究表明,土壤动物知识图谱在解决生物多样性重要科学问题方面具有独特的潜力和优势,有力推动了土壤动物学、信息科学和数据科学交叉的土壤动物信息学的发展。     

Disruption of cell wall fatty acid biosynthesis in <Emphasis Type="Italic">Mycobacterium tuberculosis</Emphasis> using a graph theoretic approach

Fatty acid biosynthesis of Mycobacterium tuberculosis was analyzed using graph theory and influential (impacting) proteins were identified. The graphs (digraphs) representing this biological network provide information concerning the connectivity of each protein or metabolite in a given pathway, providing an insight into the importance of various components in the pathway, and this can be quantitatively analyzed. Using a graph theoretic algorithm, the most influential set of proteins (sets of {1, 2, 3}, etc.), which when eliminated could cause a significant impact on the biosynthetic pathway, were identified. This set of proteins could serve as drug targets. In the present study, the metabolic network of Mycobacterium tuberculosis was constructed and the fatty acid biosynthesis pathway was analyzed for potential drug targeting. The metabolic network was constructed using the KEGG LIGAND database and subjected to graph theoretical analysis. The nearness index of a protein was used to determine the influence of the said protein on other components in the network, allowing the proteins in a pathway to be ordered according to their nearness indices. A method for identifying the most strategic nodes to target for disrupting the metabolic networks is proposed, aiding the development of new drugs to combat this deadly disease.     

Interrelations of Graph Distance Measures Based on Topological Indices

In this paper, we derive interrelations of graph distance measures by means of inequalities. For this investigation we are using graph distance measures based on topological indices that have not been studied in this context. Specifically, we are using the well-known Wiener index, Randić index, eigenvalue-based quantities and graph entropies. In addition to this analysis, we present results from numerical studies exploring various properties of the measures and aspects of their quality. Our results could find application in chemoinformatics and computational biology where the structural investigation of chemical components and gene networks is currently of great interest.     

Uncovering operational interactions in genetic networks using asynchronous Boolean dynamics

Biological networks of large dimensions, with their diagram of interactions, are often well represented by a Boolean model with a family of logical rules. The state space of a Boolean model is finite, and its asynchronous dynamics are fully described by a transition graph in the state space. In this context, a model reduction method will be developed for identifying the active or operational interactions responsible for a given dynamic behaviour. The first step in this procedure is the decomposition of the asynchronous transition graph into its strongly connected components, to obtain a “reduced” and hierarchically organized graph of transitions. The second step consists of the identification of a partial graph of interactions and a sub-family of logical rules that remain operational in a given region of the state space. This model reduction method and its usefulness are illustrated by an application to a model of programmed cell death. The method identifies two mechanisms used by the cell to respond to death-receptor stimulation and decide between the survival and apoptotic pathways.     

A graph-theory algorithm for rapid protein side-chain prediction

Fast and accurate side-chain conformation prediction is important for homology modeling, ab initio protein structure prediction, and protein design applications. Many methods have been presented, although only a few computer programs are publicly available. The SCWRL program is one such method and is widely used because of its speed, accuracy, and ease of use. A new algorithm for SCWRL is presented that uses results from graph theory to solve the combinatorial problem encountered in the side-chain prediction problem. In this method, side chains are represented as vertices in an undirected graph. Any two residues that have rotamers with nonzero interaction energies are considered to have an edge in the graph. The resulting graph can be partitioned into connected subgraphs with no edges between them. These subgraphs can in turn be broken into biconnected components, which are graphs that cannot be disconnected by removal of a single vertex. The combinatorial problem is reduced to finding the minimum energy of these small biconnected components and combining the results to identify the global minimum energy conformation. This algorithm is able to complete predictions on a set of 180 proteins with 34342 side chains in <7 min of computer time. The total chi(1) and chi(1 + 2) dihedral angle accuracies are 82.6% and 73.7% using a simple energy function based on the backbone-dependent rotamer library and a linear repulsive steric energy. The new algorithm will allow for use of SCWRL in more demanding applications such as sequence design and ab initio structure prediction, as well addition of a more complex energy function and conformational flexibility, leading to increased accuracy.     

Paired de bruijn graphs: a novel approach for incorporating mate pair information into genome assemblers

The recent proliferation of next generation sequencing with short reads has enabled many new experimental opportunities but, at the same time, has raised formidable computational challenges in genome assembly. One of the key advances that has led to an improvement in contig lengths has been mate pairs, which facilitate the assembly of repeating regions. Mate pairs have been algorithmically incorporated into most next generation assemblers as various heuristic post-processing steps to correct the assembly graph or to link contigs into scaffolds. Such methods have allowed the identification of longer contigs than would be possible with single reads; however, they can still fail to resolve complex repeats. Thus, improved methods for incorporating mate pairs will have a strong effect on contig length in the future. Here, we introduce the paired de Bruijn graph, a generalization of the de Bruijn graph that incorporates mate pair information into the graph structure itself instead of analyzing mate pairs at a post-processing step. This graph has the potential to be used in place of the de Bruijn graph in any de Bruijn graph based assembler, maintaining all other assembly steps such as error-correction and repeat resolution. Through assembly results on simulated perfect data, we argue that this can effectively improve the contig sizes in assembly.