Search PubMed⌕ Search

SEARCH · Search PubMed

Results for “Network graphs”

Search indexed PubMed citations on genomics, clinical trials, systematic reviews and public health. Explore titles, authors and supplied subject terms, then open the PubMed record.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 289 records · Page 16Linked to original sources
PubMed2004

LGL: creating a map of protein function with an algorithm for visualizing very large biological networks.

Networks are proving to be central to the study of gene function, protein-protein interaction, and biochemical pathway data. Visualization of networks is important for their study, but visualization tools are often inadequate for working with very large biological networks. Here, we present an algorithm, called large graph layout (LGL), which can be used to dynamically visualize large networks on the order of hundreds of thousands of vertices and millions of edges. LGL applies a force-directed iterative layout guided by a minimal spanning tree of the network in order to generate coordinates for the vertices in two or three dimensions, which are subsequently visualized and interactively navigated with companion programs. We demonstrate the use of LGL in visualizing an extensive protein map summarizing the results of approximately 21 billion sequence comparisons between 145579 proteins from 50 genomes. Proteins are positioned in the map according to sequence homology and gene fusions, with the map ultimately serving as a theoretical framework that integrates inferences about gene function derived from sequence homology, remote homology, gene fusions, and higher-order fusions. We confirm that protein neighbors in the resulting map are functionally related, and that distinct map regions correspond to distinct cellular systems, enabling a computational strategy for discovering proteins' functions on the basis of the proteins' map positions. Using the map produced by LGL, we infer general functions for 23 uncharacterized protein families.

Algorithms↗
PubMed2005

Metabolic PathFinding: inferring relevant pathways in biochemical networks.

Our knowledge of metabolism can be represented as a network comprising several thousands of nodes (compounds and reactions). Several groups applied graph theory to analyse the topological properties of this network and to infer metabolic pathways by path finding. This is, however, not straightforward, with a major problem caused by traversing irrelevant shortcuts through highly connected nodes, which correspond to pool metabolites and co-factors (e.g. H2O, NADP and H+). In this study, we present a web server implementing two simple approaches, which circumvent this problem, thereby improving the relevance of the inferred pathways. In the simplest approach, the shortest path is computed, while filtering out the selection of highly connected compounds. In the second approach, the shortest path is computed on the weighted metabolic graph where each compound is assigned a weight equal to its connectivity in the network. This approach significantly increases the accuracy of the inferred pathways, enabling the correct inference of relatively long pathways (e.g. with as many as eight intermediate reactions). Available options include the calculation of the k-shortest paths between two specified seed nodes (either compounds or reactions). Multiple requests can be submitted in a queue. Results are returned by email, in textual as well as graphical formats (available in http://www.scmbb.ulb.ac.be/pathfinding/).

Algorithms↗
PubMed2003

Network participation indices: characterizing component roles for information processing in neural networks.

We propose a set of indices that characterize-on the basis of connectivity data-how a network node participates in a larger network and what roles it may take given the specific sub-network of interest. These Network Participation Indices are derived from simple graph theoretic measures and have the interesting property of linking local features of individual network components to distributed properties that arise within the network as a whole. We use connectivity data on large-scale cortical networks to demonstrate the virtues of this approach and highlight some interesting features that had not been brought up in previously published material. Some implications of our approach for defining network characteristics relevant to functional segregation and functional integration, for example, from functional imaging studies are discussed.

Mental Processes↗
PubMed2003

Network bipartivity.

Systems with two types of agents with a preference for heterophilous interaction produce networks that are more or less close to bipartite. We propose two measures quantifying the notion of bipartivity. The two measures-one well known and natural, but computationally intractable, and the other computationally less complex, but also less intuitive-are examined on model networks that continuously interpolate between bipartite graphs and graphs with many odd circuits. We find that the bipartivity measures increase as we tune the control parameters of the test networks to intuitively increase the bipartivity, and thus conclude that the measures are quite relevant. We also measure and discuss the values of our bipartivity measures for empirical social networks (constructed from professional collaborations, Internet communities, and field surveys). Here we find, as expected, that networks arising from romantic online interaction have high, and professional collaboration networks have low, bipartivity values. In some other cases, probably due to low average degree of the network, the bipartivity measures cannot distinguish between romantic and friendship oriented interaction.

Journal Article↗
PubMed2003

Bio-array images processing and genetic networks modelling.

The new tools available for gene expression studies are essentially the bio-array methods using a large variety of physical detectors (isotopes, fluorescent markers, ultrasounds...). Here we present first rapidly an image-processing method independent of the detector type, dealing with the noise and with the peaks overlapping, the peaks revealing the detector activity (isotopic in the presented example), correlated with the gene expression. After this primary step of bio-array image processing, we can extract information about causal influence (activation or inhibition) a gene can exert on other genes, leading to clusters of genes co-expression in which we extract an interaction matrix M and an associated interaction graph G explaining the genetic regulatory dynamics correlated to the studied tissue function. We give two examples of such interaction matrices and graphs (the flowering genetic regulatory network of Arabidopsis thaliana and the lytic/lysogenic operon of the phage Mu) and after some theoretical rigorous results recently obtained concerning the asymptotic states generated by the genetic networks having a given interaction matrix and reciprocally concerning the minimal (in the sense of having a minimal number of non-zero coefficients) matrices having given stationary stable states.

Arabidopsis↗
PubMed2005

Extraction of biological interaction networks from scientific literature.

Biology can be regarded as a science of networks: interactions between various biological entities (eg genes, proteins, metabolites) on different levels (eg gene regulation, cell signalling) can be represented as graphs and, thus, analysis of such networks might shed new light on the function of biological systems. Such biological networks can be obtained from different sources. The extraction of networks from text is an important technique that requires the integration of several different computational disciplines. This paper summarises the most important steps in network extraction and reviews common approaches and solutions for the extraction of biological networks from scientific literature.

Abstracting and Indexing↗
PubMed2002

Range-dependent random graphs and their application to modeling large small-world Proteome datasets.

In this paper we consider the problem of characterizing and modeling large-scale networks using classes of range-dependent graphs which possess appropriate small-world properties. The application we have in mind is to bioinformatics, where methods of rapid protein identification mean that such proteome datasets, listing various observed protein-protein associations, will become more and more prevalent. We introduce a class of range-dependent graphs, governed by a power law relating intervertex range to edge probability, which are amenable to analysis, and for which macroscopic graph parameters are given by explicit forms. We show how these may be employed in representing a given network using a maximum likelihood approach. This in turn annotates every given edge with its range, representing the tendency for such an association to be transitive. We apply this technique to published proteome data, and demonstrate that known protein associations are thus identified.

Journal Article↗
PubMed1997

Classification of rhythmic patterns in the stomatogastric ganglion.

A large class of neural pattern generators change their rhythmic output under the influence of neuromodulators. We present a method for identifying the variety of rhythmic patterns generated by small neural networks. The technique provides a tool for investigating the biological mechanisms responsible for pattern generation and pattern switching. Discrete methods based on transition graphs are applied to dynamic biological networks to generate sets of possible rhythmic behaviours. A measure is introduced onto the set of rhythms to quantify their differences and organize the set according to clusters of similar rhythms. Each cluster represents a different operational mode of the network. Examples are drawn from the stomatogastric ganglion, a well studied network that controls the muscles in the foregut of crustaceans. Classes of rhythms are found that correspond to experimentally observed patterns, and other classes of rhythms are found that have not yet been observed. Predictions are made for the rhythmic output of the stomatogastric ganglion under specific manipulations of parameters in the biological network.

Animals↗
PubMed2006

Biological context networks: a mosaic view of the interactome.

Network models are a fundamental tool for the visualization and analysis of molecular interactions occurring in biological systems. While broadly illuminating the molecular machinery of the cell, graphical representations of protein interaction networks mask complex patterns of interaction that depend on temporal, spatial, or condition-specific contexts. In this paper, we introduce a novel graph construct called a biological context network that explicitly captures these changing patterns of interaction from one biological context to another. We consider known gene ontology biological process and cellular component annotations as a proxy for context, and show that aggregating small process-specific protein interaction sub-networks leads to the emergence of observed scale-free properties. The biological context model also provides the basis for characterizing proteins in terms of several context-specific measures, including 'interactive promiscuity,' which identifies proteins whose interacting partners vary from one context to another. We show that such context-sensitive measures are significantly better predictors of knockout lethality than node degree, reaching better than 70% accuracy among the top scoring proteins.

Protein Interaction Mapping↗
PubMed2005

The net of life: reconstructing the microbial phylogenetic network.

It has previously been suggested that the phylogeny of microbial species might be better described as a network containing vertical and horizontal gene transfer (HGT) events. Yet, all phylogenetic reconstructions so far have presented microbial trees rather than networks. Here, we present a first attempt to reconstruct such an evolutionary network, which we term the "net of life". We use available tree reconstruction methods to infer vertical inheritance, and use an ancestral state inference algorithm to map HGT events on the tree. We also describe a weighting scheme used to estimate the number of genes exchanged between pairs of organisms. We demonstrate that vertical inheritance constitutes the bulk of gene transfer on the tree of life. We term the bulk of horizontal gene flow between tree nodes as "vines", and demonstrate that multiple but mostly tiny vines interconnect the tree. Our results strongly suggest that the HGT network is a scale-free graph, a finding with important implications for genome evolution. We propose that genes might propagate extremely rapidly across microbial species through the HGT network, using certain organisms as hubs.

Algorithms↗
PubMed2003

Predicting protein function from protein/protein interaction data: a probabilistic approach.

MOTIVATION: The development of experimental methods for genome scale analysis of molecular interaction networks has made possible new approaches to inferring protein function. This paper describes a method of assigning functions based on a probabilistic analysis of graph neighborhoods in a protein-protein interaction network. The method exploits the fact that graph neighbors are more likely to share functions than nodes which are not neighbors. A binomial model of local neighbor function labeling probability is combined with a Markov random field propagation algorithm to assign function probabilities for proteins in the network. RESULTS: We applied the method to a protein-protein interaction dataset for the yeast Saccharomyces cerevisiae using the Gene Ontology (GO) terms as function labels. The method reconstructed known GO term assignments with high precision, and produced putative GO assignments to 320 proteins that currently lack GO annotation, which represents about 10% of the unlabeled proteins in S. cerevisiae.

Algorithms↗
PubMedDate not supplied

Graph-theoretical analysis of tunneling electron transfer in large polycyclic aromatic hydrocarbon networks.

Effect of a single nitrogen atom substitution to a number of large polycyclic aromatic hydrocarbon (PAH) molecules was calculated systematically, and it was found that especially in parallelogram-type PAH abnormal electron transfer (called tunneling electron transfer, TET) was observed. That is, fairly large amount of pi-electron is withdrawn to an electronegative nitrogen atom from almost the farthest end of a conjugated aromatic hydrocarbon molecule, leaving almost no change in the interior of the molecule. This change can be simulated by the Kekulé structure counting for subgraphs of the parent molecule.

Journal Article↗
PubMed2004

Delays, connection topology, and synchronization of coupled chaotic maps.

We consider networks of coupled maps where the connections between units involve time delays. We show that, similar to the undelayed case, the synchronization of the network depends on the connection topology, characterized by the spectrum of the graph Laplacian. Consequently, scale-free and random networks are capable of synchronizing despite the delayed flow of information, whereas regular networks with nearest-neighbor connections and their small-world variants generally exhibit poor synchronization. On the other hand, connection delays can actually be conducive to synchronization, so that it is possible for the delayed system to synchronize where the undelayed system does not. Furthermore, the delays determine the synchronized dynamics, leading to the emergence of a wide range of new collective behavior which the individual units are incapable of producing in isolation.

Journal Article↗
PubMed2005

A high-order graph generating self-organizing structure.

A large class of neural network models have their units organized in a lattice with fixed topology or generate their topology during the learning process. These network models can be used as neighborhood preserving map of the input manifold, but such a structure is difficult to manage since these maps are graphs with a number of nodes that is just one or two orders of magnitude less than the number of input points (i.e., the complexity of the map is comparable with the complexity of the manifold) and some hierarchical algorithms were proposed in order to obtain a high-level abstraction of these structures. In this paper a general structure capable to extract high order information from the graph generated by a large class of self-organizing networks is presented. This algorithm will allow to build a two layers hierarchical structure starting from the results obtained by using the suitable neural network for the distribution of the input data. Moreover the proposed algorithm is also capable to build a topology preserving map if it is trained using a graph that is also a topology preserving map.

Algorithms↗
PubMed2006

Virtual identification of essential proteins within the protein interaction network of yeast.

Topological analysis of large scale protein-protein interaction networks (PINs) is important for understanding the organizational and functional principles of individual proteins. The number of interactions that a protein has in a PIN has been observed to be correlated with its indispensability. Essential proteins generally have more interactions than the nonessential ones. We show here that the lethality associated with removal of a protein from the yeast proteome correlates with different centrality measures of the nodes in the PIN, such as the closeness of a protein to many other proteins, or the number of pairs of proteins which need a specific protein as an intermediary in their communications, or the participation of a protein in different protein clusters in the PIN. These measures are significantly better than random selection in identifying essential proteins in a PIN. Centrality measures based on graph spectral properties of the network, in particular the subgraph centrality, show the best performance in identifying essential proteins in the yeast PIN. Subgraph centrality gives important structural information about the role of individual proteins, and permits the selection of possible targets for rational drug discovery through the identification of essential proteins in the PIN.

Proteome↗
PubMed2006

Construction of phylogenetic trees by kernel-based comparative analysis of metabolic networks.

BACKGROUND: To infer the tree of life requires knowledge of the common characteristics of each species descended from a common ancestor as the measuring criteria and a method to calculate the distance between the resulting values of each measure. Conventional phylogenetic analysis based on genomic sequences provides information about the genetic relationships between different organisms. In contrast, comparative analysis of metabolic pathways in different organisms can yield insights into their functional relationships under different physiological conditions. However, evaluating the similarities or differences between metabolic networks is a computationally challenging problem, and systematic methods of doing this are desirable. Here we introduce a graph-kernel method for computing the similarity between metabolic networks in polynomial time, and use it to profile metabolic pathways and to construct phylogenetic trees. RESULTS: To compare the structures of metabolic networks in organisms, we adopted the exponential graph kernel, which is a kernel-based approach with a labeled graph that includes a label matrix and an adjacency matrix. To construct the phylogenetic trees, we used an unweighted pair-group method with arithmetic mean, i.e., a hierarchical clustering algorithm. We applied the kernel-based network profiling method in a comparative analysis of nine carbohydrate metabolic networks from 81 biological species encompassing Archaea, Eukaryota, and Eubacteria. The resulting phylogenetic hierarchies generally support the tripartite scheme of three domains rather than the two domains of prokaryotes and eukaryotes. CONCLUSION: By combining the kernel machines with metabolic information, the method infers the context of biosphere development that covers physiological events required for adaptation by genetic reconstruction. The results show that one may obtain a global view of the tree of life by comparing the metabolic pathway structures using meta-level information rather than sequence information. This method may yield further information about biological evolution, such as the history of horizontal transfer of each gene, by studying the detailed structure of the phylogenetic tree constructed by the kernel-based method.

Archaeal Proteins↗
PubMed2001

A model for the emergence of cooperation, interdependence, and structure in evolving networks.

Evolution produces complex and structured networks of interacting components in chemical, biological, and social systems. We describe a simple mathematical model for the evolution of an idealized chemical system to study how a network of cooperative molecular species arises and evolves to become more complex and structured. The network is modeled by a directed weighted graph whose positive and negative links represent "catalytic" and "inhibitory" interactions among the molecular species, and which evolves as the least populated species (typically those that go extinct) are replaced by new ones. A small autocatalytic set, appearing by chance, provides the seed for the spontaneous growth of connectivity and cooperation in the graph. A highly structured chemical organization arises inevitably as the autocatalytic set enlarges and percolates through the network in a short analytically determined timescale. This self organization does not require the presence of self-replicating species. The network also exhibits catastrophes over long timescales triggered by the chance elimination of "keystone" species, followed by recoveries.

Animals↗
PubMed2006

The brainstem reticular formation is a small-world, not scale-free, network.

Recently, it has been demonstrated that several complex systems may have simple graph-theoretic characterizations as so-called 'small-world' and 'scale-free' networks. These networks have also been applied to the gross neural connectivity between primate cortical areas and the nervous system of Caenorhabditis elegans. Here, we extend this work to a specific neural circuit of the vertebrate brain--the medial reticular formation (RF) of the brainstem--and, in doing so, we have made three key contributions. First, this work constitutes the first model (and quantitative review) of this important brain structure for over three decades. Second, we have developed the first graph-theoretic analysis of vertebrate brain connectivity at the neural network level. Third, we propose simple metrics to quantitatively assess the extent to which the networks studied are small-world or scale-free. We conclude that the medial RF is configured to create small-world (implying coherent rapid-processing capabilities), but not scale-free, type networks under assumptions which are amenable to quantitative measurement.

Animals↗