Metabolic network alignment in large scale by network compression

Metabolic network alignment is a system scale comparative analysis that discovers important similarities and differences across different metabolisms and organisms. Although the problem of aligning metabolic networks has been considered in the past, the computational complexity of the existing solutions has so far limited their use to moderately sized networks. In this paper, we address the problem of aligning two metabolic networks, particularly when both of them are too large to be dealt with using existing methods. We develop a generic framework that can significantly improve the scale of the networks that can be aligned in practical time. Our framework has three major phases, namely the compression phase, the alignment phase and the refinement phase. For the first phase, we develop an algorithm which transforms the given networks to a compressed domain where they are summarized using fewer nodes, termed supernodes, and interactions. In the second phase, we carry out the alignment in the compressed domain using an existing network alignment method as our base algorithm. This alignment results in supernode mappings in the compressed domain, each of which are smaller instances of network alignment problem. In the third phase, we solve each of the instances using the base alignment algorithm to refine the alignment results. We provide a user defined parameter to control the number of compression levels which generally determines the tradeoff between the quality of the alignment versus how fast the algorithm runs. Our experiments on the networks from KEGG pathway database demonstrate that the compression method we propose reduces the sizes of metabolic networks by almost half at each compression level which provides an expected speedup of more than an order of magnitude. We also observe that the alignments obtained by only one level of compression capture the original alignment results with high accuracy. Together, these suggest that our framework results in alignments that are comparable to existing algorithms and can do this with practical resource utilization for large scale networks that existing algorithms could not handle. As an example of our method's performance in practice, the alignment of organism-wide metabolic networks of human (1615 reactions) and mouse (1600 reactions) was performed under three minutes by only using a single level of compression.     

Seed selection strategy in global network alignment without destroying the entire structures of functional modules

Background

Network alignment is one of the most common biological network comparison methods. Aligning protein-protein interaction (PPI) networks of different species is of great important to detect evolutionary conserved pathways or protein complexes across species through the identification of conserved interactions, and to improve our insight into biological systems. Global network alignment (GNA) problem is NP-complete, for which only heuristic methods have been proposed so far. Generally, the current GNA methods fall into global heuristic seed-and-extend approaches. These methods can not get the best overall consistent alignment between networks for the opinionated local seed. Furthermore These methods are lost in maximizing the number of aligned edges between two networks without considering the original structures of functional modules.

Methods

We present a novel seed selection strategy for global network alignment by constructing the pairs of hub nodes of networks to be aligned into multiple seeds. Beginning from every hub seed and using the membership similarity of nodes to quantify to what extent the nodes can participate in functional modules associated with current seed topologically we align the networks by modules. By this way we can maintain the functional modules are not damaged during the heuristic alignment process. And our method is efficient in resolving the fatal problem of most conventional algorithms that the initialization selected seeds have a direct influence on the alignment result. The similarity measures between network nodes (e.g., proteins) include sequence similarity, centrality similarity, and dynamic membership similarity and our algorithm can be called Multiple Hubs-based Alignment (MHA).

Results

When applying our seed selection strategy to several pairs of real PPI networks, it is observed that our method is working to strike a balance, extending the conserved interactions while maintaining the functional modules unchanged. In the case study, we assess the effectiveness of MHA on the alignment of the yeast and fly PPI networks. Our method outperforms state-of-the-art algorithms at detecting conserved functional modules and retrieves in particular 86% more conserved interactions than IsoRank.

Conclusions

We believe that our seed selection strategy will lead us to obtain more topologically and biologically similar alignment result. And it can be used as the reference and complement of other heuristic methods to seek more meaningful alignment results.

     

Decomposition of metabolic network into functional modules based on the global connectivity structure of reaction graph

MOTIVATION: Metabolic networks are organized in a modular, hierarchical manner. Methods for a rational decomposition of the metabolic network into relatively independent functional subsets are essential to better understand the modularity and organization principle of a large-scale, genome-wide network. Network decomposition is also necessary for functional analysis of metabolism by pathway analysis methods that are often hampered by the problem of combinatorial explosion due to the complexity of metabolic network. Decomposition methods proposed in literature are mainly based on the connection degree of metabolites. To obtain a more reasonable decomposition, the global connectivity structure of metabolic networks should be taken into account. RESULTS: In this work, we use a reaction graph representation of a metabolic network for the identification of its global connectivity structure and for decomposition. A bow-tie connectivity structure similar to that previously discovered for metabolite graph is found also to exist in the reaction graph. Based on this bow-tie structure, a new decomposition method is proposed, which uses a distance definition derived from the path length between two reactions. An hierarchical classification tree is first constructed from the distance matrix among the reactions in the giant strong component of the bow-tie structure. These reactions are then grouped into different subsets based on the hierarchical tree. Reactions in the IN and OUT subsets of the bow-tie structure are subsequently placed in the corresponding subsets according to a 'majority rule'. Compared with the decomposition methods proposed in literature, ours is based on combined properties of the global network structure and local reaction connectivity rather than, primarily, on the connection degree of metabolites. The method is applied to decompose the metabolic network of Escherichia coli. Eleven subsets are obtained. More detailed investigations of the subsets show that reactions in the same subset are really functionally related. The rational decomposition of metabolic networks, and subsequent studies of the subsets, make it more amenable to understand the inherent organization and functionality of metabolic networks at the modular level. SUPPLEMENTARY INFORMATION: http://genome.gbf.de/bioinformatics/     

Mycobacterium tuberculosis functional network analysis by global subcellular protein profiling

Trends in increased tuberculosis infection and a fatality rate of approximately 23% have necessitated the search for alternative biomarkers using newly developed postgenomic approaches. Here we provide a systematic analysis of Mycobacterium tuberculosis (Mtb) by directly profiling its gene products. This analysis combines high-throughput proteomics and computational approaches to elucidate the globally expressed complements of the three subcellular compartments (the cell wall, membrane, and cytosol) of Mtb. We report the identifications of 1044 proteins and their corresponding localizations in these compartments. Genome-based computational and metabolic pathways analyses were performed and integrated with proteomics data to reconstruct response networks. From the reconstructed response networks for fatty acid degradation and lipid biosynthesis pathways in Mtb, we identified proteins whose involvements in these pathways were not previously suspected. Furthermore, the subcellular localizations of these expressed proteins provide interesting insights into the compartmentalization of these pathways, which appear to traverse from cell wall to cytoplasm. Results of this large-scale subcellular proteome profile of Mtb have confirmed and validated the computational network hypothesis that functionally related proteins work together in larger organizational structures.     

Path matching and graph matching in biological networks.

We develop algorithms for the following path matching and graph matching problems: (i) given a query path p and a graph G, find a path p' that is most similar to p in G; (ii) given a query graph G (0) and a graph G, find a graph G (0)' that is most similar to G (0) in G. In these problems, p and G (0) represent a given substructure of interest to a biologist, and G represents a large network in which the biologist desires to find a related substructure. These algorithms allow the study of common substructures in biological networks in order to understand how these networks evolve both within and between organisms. We reduce the path matching problem to finding a longest weighted path in a directed acyclic graph and show that the problem of finding top k suboptimal paths can be solved in polynomial time. This is in contrast with most previous approaches that used exponential time algorithms to find simple paths which are practical only when the paths are short. We reduce the graph matching problem to finding highest scoring subgraphs in a graph and give an exact algorithm to solve the problem when the query graph G (0) is of moderate size. This eliminates the need for less accurate heuristic or randomized algorithms.We show that our algorithms are able to extract biologically meaningful pathways from protein interaction networks in the DIP database and metabolic networks in the KEGG database. Software programs implementing these techniques (PathMatch and GraphMatch) are available at http://faculty.cs.tamu.edu/shsze/pathmatch and http://faculty.cs.tamu.edu/shsze/graphmatch.     

Segmentation of tissue architecture by distance graph matching.

BACKGROUND: Characterization of tissues can be based on the topographical relationship between the cells. Such characterization should be insensitive to distortions intrinsic to the acquisition of biological preparation. In this paper, a method for the robust segmentation of tissues based on the spatial distribution of cells is proposed. MATERIALS AND METHODS: The neighborhood of each cell in the tissue is modeled by the distances to the surrounding cells. Comparison with an example or prototype neighborhood reveals topographical similarity between tissue and prototype. Processing of all cells in the tissue extracts the regions with tissue architecture similar to the given example. RESULTS: Comparison with other topographical-segmentation methods shows that the proposed method is better suited for partitioning tissue architecture. As an example, the quantification of the structural integrity in rat hippocampi after ischemia is demonstrated. In contrast to other methods, the algorithm correlates well with expert evaluation. CONCLUSIONS: The present method reduces the nonbiological variation in the analysis of tissue sections and thus improves confidence in the result. The method can be applied to any field where regular patterns have to be detected, as long as the directional distribution of neighbors may be neglected.     

Discovering disease-genes by topological features in human protein-protein interaction network

MOTIVATION: Mining the hereditary disease-genes from human genome is one of the most important tasks in bioinformatics research. A variety of sequence features and functional similarities between known human hereditary disease-genes and those not known to be involved in disease have been systematically examined and efficient classifiers have been constructed based on the identified common patterns. The availability of human genome-wide protein-protein interactions (PPIs) provides us with new opportunity for discovering hereditary disease-genes by topological features in PPIs network. RESULTS: This analysis reveals that the hereditary disease-genes ascertained from OMIM in the literature-curated (LC) PPIs network are characterized by a larger degree, tendency to interact with other disease-genes, more common neighbors and quick communication to each other whereas those properties could not be detected from the network identified from high-throughput yeast two-hybrid mapping approach (EXP) and predicted interactions (PDT) PPIs network. KNN classifier based on those features was created and on average gained overall prediction accuracy of 0.76 in cross-validation test. Then the classifier was applied to 5262 genes on human genome and predicted 178 novel disease-genes. Some of the predictions have been validated by biological experiments.     

Discovering functional gene expression patterns in the metabolic network of Escherichia coli with wavelets transforms

Background  

Microarray technology produces gene expression data on a genomic scale for an endless variety of organisms and conditions. However, this vast amount of information needs to be extracted in a reasonable way and funneled into manageable and functionally meaningful patterns. Genes may be reasonably combined using knowledge about their interaction behaviour. On a proteomic level, biochemical research has elucidated an increasingly complete image of the metabolic architecture, especially for less complex organisms like the well studied bacterium Escherichia coli.     

Functional classification of protein structures by local structure matching in graph representation

As a result of high‐throughput protein structure initiatives, over 14,400 protein structures have been solved by Structural Genomics (SG) centers and participating research groups. While the totality of SG data represents a tremendous contribution to genomics and structural biology, reliable functional information for these proteins is generally lacking. Better functional predictions for SG proteins will add substantial value to the structural information already obtained. Our method described herein, Graph Representation of Active Sites for Prediction of Function (GRASP‐Func), predicts quickly and accurately the biochemical function of proteins by representing residues at the predicted local active site as graphs rather than in Cartesian coordinates. We compare the GRASP‐Func method to our previously reported method, Structurally Aligned Local Sites of Activity (SALSA), using the Ribulose Phosphate Binding Barrel (RPBB), 6‐Hairpin Glycosidase (6‐HG), and Concanavalin A‐like Lectins/Glucanase (CAL/G) superfamilies as test cases. In each of the superfamilies, SALSA and the much faster method GRASP‐Func yield similar correct classification of previously characterized proteins, providing a validated benchmark for the new method. In addition, we analyzed SG proteins using our SALSA and GRASP‐Func methods to predict function. Forty‐one SG proteins in the RPBB superfamily, nine SG proteins in the 6‐HG superfamily, and one SG protein in the CAL/G superfamily were successfully classified into one of the functional families in their respective superfamily by both methods. This improved, faster, validated computational method can yield more reliable predictions of function that can be used for a wide variety of applications by the community.     

一种融合表达谱相关性信息的激活子网辨识算法

传统表达谱数据分析方法集中于寻找差异表达基因和共表达基因集合,没有考虑基因表达产物之间已知的相互作用.近年来在系统生物学的研究中发展了将基因表达谱与蛋白质相互作用网络进行整合分析的方法.现有方法未能综合考虑基因表达差异性和相关性信息,容易导致辨识结果中重要功能分子缺失且生物学功能相关度不高.提出一种融合表达谱差异性和相关性信息的激活子网辨识算法,能够在蛋白质相互作用网络中辨识高功能相关度的激活子网.应用到人免疫缺陷病毒HIV-1感染过程的研究,结果表明,该算法可以有效避免仅考虑基因表达差异性所引入的偏差,揭示了高相关性低表达差异基因在相关通路中的关键性作用.     

Protein interaction network topology uncovers melanogenesis regulatory network components within functional genomics datasets

Background  

RNA-mediated interference (RNAi)-based functional genomics is a systems-level approach to identify novel genes that control biological phenotypes. Existing computational approaches can identify individual genes from RNAi datasets that regulate a given biological process. However, currently available methods cannot identify which RNAi screen "hits" are novel components of well-characterized biological pathways known to regulate the interrogated phenotype. In this study, we describe a method to identify genes from RNAi datasets that are novel components of known biological pathways. We experimentally validate our approach in the context of a recently completed RNAi screen to identify novel regulators of melanogenesis.     

Microbial response to simulated global change is phylogenetically conserved and linked with functional potential

The high diversity of microbial communities hampers predictions about their responses to global change. Here we investigate the potential for using a phylogenetic, trait-based framework to capture the response of bacteria and fungi to global change manipulations. Replicated grassland plots were subjected to 3+ years of drought and nitrogen fertilization. The responses of leaf litter bacteria and fungi to these simulated changes were significantly phylogenetically conserved. Proportional changes in abundance were highly correlated among related organisms, such that relatives with approximately 5% ribosomal DNA genetic distance showed similar responses to the treatments. A microbe''s change in relative abundance was significantly correlated between the treatments, suggesting a compromise between numerical abundance in undisturbed environments and resistance to change in general, independent of disturbance type. Lineages in which at least 90% of the microbes shared the same response were circumscribed at a modest phylogenetic depth (τ_D 0.014–0.021), but significantly larger than randomized simulations predict. In several clades, phylogenetic depth of trait consensus was higher. Fungal response to drought was more conserved than was response to nitrogen fertilization, whereas bacteria responded equally to both treatments. Finally, we show that a bacterium''s response to the manipulations is correlated with its potential functional traits (measured here as the number of glycoside hydrolase genes encoding the capacity to degrade different types of carbohydrates). Together, these results suggest that a phylogenetic, trait-based framework may be useful for predicting shifts in microbial composition and functioning in the face of global change.     

Discovering functional small molecules in the gut microbiome

The human microbiome has emerged as a source of bacterially produced, functional small molecules that help regulate health and disease, and their discovery and annotation has become a popular research topic. Identifying these molecules provides an essential step in unraveling the molecular mechanisms underlying biological outcomes. The relevance of specific bacterial members of the microbiome has been demonstrated in a variety of correlative studies, and there are many possible paths from these correlations to the responsible metabolites. Herein, we summarize two studies that have recently identified gut microbiome metabolites that modulate immune responses or promote physical activity. Aside from the deep insights gained, these studies provide blueprints for successfully uncovering the molecules and mechanisms that control important physiological pathways.     

Discovering functional interaction patterns in protein-protein interaction networks

Background  

In recent years, a considerable amount of research effort has been directed to the analysis of biological networks with the availability of genome-scale networks of genes and/or proteins of an increasing number of organisms. A protein-protein interaction (PPI) network is a particular biological network which represents physical interactions between pairs of proteins of an organism. Major research on PPI networks has focused on understanding the topological organization of PPI networks, evolution of PPI networks and identification of conserved subnetworks across different species, discovery of modules of interaction, use of PPI networks for functional annotation of uncharacterized proteins, and improvement of the accuracy of currently available networks.     

High-throughput subtomogram alignment and classification by Fourier space constrained fast volumetric matching

Cryo-electron tomography allows the visualization of macromolecular complexes in their cellular environments in close-to-live conditions. The nominal resolution of subtomograms can be significantly increased when individual subtomograms of the same kind are aligned and averaged. A vital step for such a procedure are algorithms that speedup subtomogram alignment and improve its accuracy to allow reference-free subtomogram classifications. Such methods will facilitate automation of tomography analysis and overall high throughput in the data processing. Building on previous work, here we propose a fast rotational alignment method that uses the Fourier equivalent form of a popular constrained correlation measure that considers missing wedge corrections and density variances in the subtomograms. The fast rotational search is based on 3D volumetric matching, which improves the rotational alignment accuracy in particular for highly distorted subtomograms with low SNR and tilt angle ranges in comparison to fast rotational matching of projected 2D spherical images. We further integrate our fast rotational alignment method in a reference-free iterative subtomogram classification scheme, and propose a local feature enhancement strategy in the classification process. As a proof of principle, we can demonstrate that the automatic method can successfully classify a large number of experimental subtomograms without the need of a reference structure.