Search PubMed⌕ Search

SEARCH · Search PubMed

Results for “graph theory”

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 127 records · Page 7Linked to original sources
PubMed2005

SpectralNET--an application for spectral graph analysis and visualization.

BACKGROUND: Graph theory provides a computational framework for modeling a variety of datasets including those emerging from genomics, proteomics, and chemical genetics. Networks of genes, proteins, small molecules, or other objects of study can be represented as graphs of nodes (vertices) and interactions (edges) that can carry different weights. SpectralNET is a flexible application for analyzing and visualizing these biological and chemical networks. RESULTS: Available both as a standalone .NET executable and as an ASP.NET web application, SpectralNET was designed specifically with the analysis of graph-theoretic metrics in mind, a computational task not easily accessible using currently available applications. Users can choose either to upload a network for analysis using a variety of input formats, or to have SpectralNET generate an idealized random network for comparison to a real-world dataset. Whichever graph-generation method is used, SpectralNET displays detailed information about each connected component of the graph, including graphs of degree distribution, clustering coefficient by degree, and average distance by degree. In addition, extensive information about the selected vertex is shown, including degree, clustering coefficient, various distance metrics, and the corresponding components of the adjacency, Laplacian, and normalized Laplacian eigenvectors. SpectralNET also displays several graph visualizations, including a linear dimensionality reduction for uploaded datasets (Principal Components Analysis) and a non-linear dimensionality reduction that provides an elegant view of global graph structure (Laplacian eigenvectors). CONCLUSION: SpectralNET provides an easily accessible means of analyzing graph-theoretic metrics for data modeling and dimensionality reduction. SpectralNET is publicly available as both a .NET application and an ASP.NET web application from http://chembank.broad.harvard.edu/resources/. Source code is available upon request.

Algorithms↗
PubMed1996

Cellular sociology applied to neuroendocrine tumors of the lung: quantitative model of neoplastic architecture.

This paper reports on cellular sociology, which consists of modeling tissular architecture based on graph theory. Voronoi's diagram was chosen to build the models. This diagram derives from a cell neighborhood concept and generates parameters which objectively represent tissue architecture. Minimal spanning tree (MST) is probably the more frequently used among graphs and successfully discriminates different grades of pathological process. However, Voronoi's diagram is more comprehensive and a more complete representation of architecture with the advantage of stability. The lung neuroendocrine tumor classification is far from being consensual, especially for lesions which don't fall in with typical carcinoid and small cell carcinoma groups. By comparing architectural models of 20 neuroendocrine tumors of the lung, this work supports the morphologic spectrum concept of these tumors and also supports the recently proposed concept of large-cell neuroendocrine tumors of the lung. Finally, architectural parameters separate small-cell-lung carcinomas from neuroendocrine non-small-cell lung carcinomas.

Carcinoid Tumor↗
PubMed2006

Network and graph analyses of folding free energy surfaces.

Protein folding is governed by a complex free energy surface whose entropic contributions are relevant because of the large number of degrees of freedom involved. Such complexity, in particular the conformational heterogeneity of the denatured state, is hidden in projections onto one or two order parameters (e.g. fraction of native contacts and/or radius of gyration), which usually results in relatively smooth surfaces. Recent approaches borrowed from network and graph theory have yielded quantitative unprojected representations of the free energy surfaces of a beta-hairpin and a three-stranded beta-sheet peptide using equilibrium folding-unfolding molecular dynamics simulations. Interestingly, the network and graph analyses of these structured peptides have revealed a very heterogeneous denatured state ensemble. It includes high-enthalpy, high-entropy conformations with fluctuating non-native secondary structure, as well as low-enthalpy, low-entropy traps.

Computational Biology↗
PubMedDate not supplied

UMLS-based conceptual queries to biomedical information databases: an overview of the project ARIANE. Unified Medical Language System.

OBJECTIVE: The aim of the project ARIANE is to model and implement seamless, natural, and easy-to-use interfaces with various kinds of heterogeneous biomedical information databases. DESIGN: A conceptual model of some of the Unified Medical Language System (UMLS) knowledge sources has been developed to help end users to query information databases. A query is represented by a conceptual graph that translates the deep structure of an end-user's interest in a topic. A computational model exploits this conceptual model to build a query interactively represented as query graph. A query graph is then matched to the data graph built with data issued from each record of a database by means of a pattern-matching (projection) rule that applies to conceptual graphs. RESULTS: Prototypes have been implemented to test the feasibility of the model with different kinds of information databases. Three cases are studied: 1) information in records is structured according to the UMLS knowledge sources; 2) information is able to be structured without error in the frame of the UMLS knowledge; 3) information cannot be structured. In each case the pattern-matching is processed by the projection rule according to the structure of information that has been implemented in the databases. CONCLUSION: The conceptual graphs theory provides with a homogeneous and powerful formalism able to represent both concepts, instances of concepts in medical contexts, and associations by means of relationships, and to represent data at different levels of details. The conceptual-graphs formalism allows powerful capabilities to operate a semantic integration of information databases using the UMLS knowledge sources.

Databases as Topic↗
PubMed1988

Representing and defining patterns by graphs: applications to sol-gel patterns and to cytoskeleton.

The problems of interdisciplinary interests--applying methods of graph theory to sol-gel patterns and to cytoskeleton--are discussed. The importance of sol-gel transition phenomena in living cells and the possibility of periodic sol-gel transition phenomena are briefly reviewed. Representing patterns by graphs and using graph probabilistic representation for calculating structure-property relationships are discussed and applied to sol-gel transition patterns.

Biometry↗
PubMed2002

Analysis of voids in crystal structures: the methods of 'dual' crystal chemistry.

The theoretical basics of the analysis of voids in crystal structures by means of Voronoi-Dirichlet polyhedra (VDP) and of the graph theory are stated. Topological relations are considered between VDPs and atomic domains in a crystal field. These relations allow the separation of two non-intersecting topological subspaces in a crystal structure, whose connectednesses are defined by two finite 'reduced' graphs. The first, 'direct', subspace includes the atoms (VDP centres) and the network of interatomic bonds (VDP faces), the second, 'dual', one comprises the void centres (VDP vertices) and the system of channels (VDP edges) between them. Computer methods of geometrical-topological analysis of the 'dual' subspace are developed and implemented within the program package TOPOS. They are designed for automatically restoring the system of channels, visualizing and sizing voids and void conglomerates, dimensional analysis of continuous void systems, and comparative topological analysis of 'dual' subspaces for various substances. The methods of analysis of 'dual' and 'direct' subspaces are noted to differ from each other only in some details that allows the term 'dual' crystal chemistry to be introduced. The efficiency of the methods is shown with the analysis of compounds of different chemical nature: simple substances, ionic structures, superionic conductors, zeolites, clathrates, organic supramolecular complexes.

Journal Article↗
PubMed2006

Graph theoretic properties of networks formed by the Delaunay tessellation of protein structures.

The Delaunay tessellation of several sets of real and simplified model protein structures has been used to explore graph theoretic properties of residue contact networks. The system of contacts defined by residues joined by edges in the Delaunay simplices can be thought of as a graph or network and analyzed using techniques from elementary graph theory and the theory of complex networks. Such analysis indicates that protein contact networks have small world character, but technically are not small world networks. This approach also indicates that networks formed by native structures and by most misfolded decoys can be differentiated by their respective graph properties. The characteristic features of residue contact networks can be used for the detection of structural elements in proteins, such as the ubiquitous closed loops consisting of 22-32 consecutive residues, where terminal residues are Delaunay neighbors.

Binding Sites↗
PubMed2005

Global analysis of the phase calibration operation.

A global approach to phase calibration is presented. The corresponding theoretical framework calls on elementary concepts of algebraic graph theory (spanning tree of maximal weight, cycles) and algebraic number theory (lattice, nearest lattice point). The traditional approach can thereby be better understood. In radio imaging and in optical interferometry, the self-calibration procedures must often be conducted with much care. The analysis presented should then help in finding a better compromise between the coverage of the calibration graph (which must be as complete as possible) and the quality of the solution (which must of course be reliable).

Journal Article↗
PubMed2005

tRNA structure from a graph and quantum theoretical perspective.

One of the objectives of theoretical biochemistry is to find a suitable representation of molecules allowing us to encode what we know about their structures, interactions and reactivity. Particularly, tRNA structure is involved in some processes like aminoacylation and genetic code translation, and for this reason these molecules represent a biochemical object of the utmost importance requiring characterization. We propose here two fundamental aspects for characterizing and modeling them. The first takes into consideration the connectivity patterns, i.e. the set of linkages between atoms or molecular fragments (a key tool for this purpose is the use of graph theory), and the second one requires the knowledge of some properties related to the interactions taking place within the molecule, at least in an approximate way, and perhaps of its reactivity in certain means. We used quantum mechanics to achieve this goal; specifically, we have used partial charges as a manifestation of the reply to structural changes. These charges were appropriately modified to be used as weighted factors for elements constituting the molecular graph. This new graph-tRNA context allow us to detect some structure-function relationships.

Base Sequence↗
PubMed2004

Architectural analysis of oral cancer, dysplastic, and normal epithelia.

BACKGROUND: We present a novel, automated, and quantitative approach to evaluate local epithelial tissue architecture based on mathematical graph theory. METHODS: Four hundred forty-one images of three diagnostic classes of oral epithelium (normal, dysplastic, and neoplastic) were analysed. The epithelial compartment was partitioned into exclusive areas associated with each nucleus to approach the theoretical cell extents. The spatial arrangement of cells in neighbourhoods of two sizes was characterised by constructing graph networks based on the cell centroids and recording 29 statistical properties. We analysed 104,627 and 67,590 neighbourhoods of diameters 37.5 and 75 microm, respectively. RESULTS: The discrimination power of the architectural descriptors was evaluated by using discriminant analysis. The best neighbourhood discrimination rate was 75% for normal versus carcinoma. For the pooled data, discrimination into three classes based on largest number of neighbourhoods associated with each class was 100% correct. Case-wise, discrimination rates were 67%, 100%, and 80% correct for normal, premalignant, and malignant. When considering two classes, discrimination rates was 89% (normal) and 100% (malignant) correct, with 71% of premalignant cases assigned to the malignant class. CONCLUSIONS: The results indicate that unbiased and reproducible quantification of tissue architectural features is possible and may provide valuable morphological information for diagnostic purposes.

Cytodiagnosis↗
PubMed2004

Complexity analysis of yeast proteome network.

Topological and compositional complexity of protein-protein networks is assessed in a variety of ways making use of graph theory and information theory. The methodology used is borrowed from mathematical chemistry and includes complexity descriptors such as substructure count, overall connectivity, walk count, and information on various vertex distributions. The approach is applied to the (incomplete) proteome of Saccharomyces cerevisiae containing 232 protein complexes of a total of 1,440 proteins. The proteome network and each of its nine functional subsets of protein complexes are disconnected graphs, containing a number of noninteracting species and a major component. A weighted edge between two vertices in these graphs stands for the number of shared proteins between the respective complexes. The major component is a highly connected, 'small-world' network, in which the average vertex distance between protein complexes does not exceed 2.2 (2.4 for the entire proteome), whereas the maximum distance does not exceed 4 (or 5 for the proteome). The vertex degree distribution in the major proteome component with 199 complexes follows the power law P(k) approximately k(-gamma), with gamma approximately = 1.7. The analysis of the functional organization of the yeast proteome has shown that, for any pair of biological functions, there always exist many proteins that can perform both functions. The potential application of the quantitative proteome descriptors discussed includes quantitative relationships between the structure and biological action of dynamic protein complexes in changing environment, identification of targets for markers/drugs, as well as system analysis and comparative studies of proteomes.

Fungal Proteins↗
PubMedDate not supplied

Decision analysis: theory and methods in clinical development and monitoring of clinical trials.

Decision analysis has been widely used in business, first in operational research, later in economic studies. It is now spreading to medical training. We review methodology of decision analysis which is simple, rational and based on the environmental conditions. When clinical judgments are uncertain, the most appropriate strategy is helped by the use of standard/bayesian probabilities quantifying the risks of each strategy, and the design of decision trees visualizing each outcome. If the probabilities are not suitable, other mathematical concepts such as Markov process are interesting but are still being worked on. Multicriteria analysis, a branch of graph theory, is also a flexible and reliable tool allowing differentiation and ordering strategies. It also takes into account the psychological characteristic of the decision makers. We then illustrate decision analysis by describing computerized systems for monitoring clinical trials, fitted to control the trial data able to estimate the different strategies.

Clinical Medicine↗
PubMed2006

Correlated fragile site expression allows the identification of candidate fragile genes involved in immunity and associated with carcinogenesis.

BACKGROUND: Common fragile sites (cfs) are specific regions in the human genome that are particularly prone to genomic instability under conditions of replicative stress. Several investigations support the view that common fragile sites play a role in carcinogenesis. We discuss a genome-wide approach based on graph theory and Gene Ontology vocabulary for the functional characterization of common fragile sites and for the identification of genes that contribute to tumour cell biology. RESULTS: Common fragile sites were assembled in a network based on a simple measure of correlation among common fragile site patterns of expression. By applying robust measurements to capture in quantitative terms the non triviality of the network, we identified several topological features clearly indicating departure from the Erdos-Renyi random graph model. The most important outcome was the presence of an unexpected large connected component far below the percolation threshold. Most of the best characterized common fragile sites belonged to this connected component. By filtering this connected component with Gene Ontology, statistically significant shared functional features were detected. Common fragile sites were found to be enriched for genes associated to the immune response and to mechanisms involved in tumour progression such as extracellular space remodeling and angiogenesis. Moreover we showed how the internal organization of the graph in communities and even in very simple subgraphs can be a starting point for the identification of new factors of instability at common fragile sites. CONCLUSION: We developed a computational method addressing the fundamental issue of studying the functional content of common fragile sites. Our analysis integrated two different approaches. First, data on common fragile site expression were analyzed in a complex networks framework. Second, outcomes of the network statistical description served as sources for the functional annotation of genes at common fragile sites by means of the Gene Ontology vocabulary. Our results support the hypothesis that fragile sites serve a function; we propose that fragility is linked to a coordinated regulation of fragile genes expression.

Cells, Cultured↗
PubMed2006

Disturbed functional connectivity in brain tumour patients: evaluation by graph analysis of synchronization matrices.

OBJECTIVE: Cerebral functions are based on the functional interactions between multiple distinct specialized regions of the brain. Functional interactions require anatomical connections as well as the synchronization of brain oscillations. The present work aims at evaluating the impact of brain tumours on spatial patterns of functional connectivity of the brain measured at rest by MEG. METHODS: We analyzed the statistical dependency (by computing the synchronization likelihood (SL, a measure of generalized synchronization)) between MEG signals at rest, in 17 patients with a brain tumour and in 15 healthy controls. Following an approach that derives from graph theory, we also analyzed the architectural properties of the networks by computing two parameters from the SL matrix, the cluster coefficient C and the characteristic path length L. RESULTS: Alterations in synchronization levels were found in the patients and were not focal but involved intra-hemispheric connectivity. Effects were different considering the frequencies sub-bands, predominating in a decrease in high frequencies bands for long-distance connections and an increase in slower bands for local connectivity. In addition, graph analysis reveals changes in the normal "small-world" network architecture in addition to changes in synchronization levels with some differences according to the studied frequency sub-bands. CONCLUSIONS: Brain tumours alter the functional connectivity and the "network" architecture of the brain. These alterations are not focal and effects are different considering the frequencies sub-bands. SIGNIFICANCE: These neurophysiological changes may contribute to the cognitive alterations observed in patients with brain tumours.

Adult↗
PubMed2001

The use of Hasse diagrams as a potential approach for inverse QSAR.

Quantitative structure-activity relationships are often based on standard multidimensional statistical analyses and sophisticated local and global molecular descriptors. Here, the aim is to develop a tool helpful to define a molecule or a class of molecules which fulfills pre-described properties, i.e., an Inverse QSAR approach. If highly sophisticated descriptors are used in QSAR, the structure and then the synthesis recipe may be hard to derive. Thus, descriptors, from which the synthesis recipe can be easily derived, seem appropriate to be included within this study. However, if descriptors simple enough to be useful for defining syntheses recipes of chemicals were used, the accuracy of a numeric expression may fail. This paper suggests a method, based on very simple elements of the theory of partially ordered sets, to find a qualitative basis for the relationship between such fairly simple descriptors on the one side and a series of ecotoxicological properties, on the other side. The partial order ranking method assumes neither linearity nor certain statistical distribution properties. Therefore the method may be more general compared to many standard statistical techniques. A series of chlorinated aliphatic compounds has been used as an illustrative example and a comparison with more sophisticated descriptors derived from quantum chemistry and graph theory is given. Among the results, it was disclosed that only for algae lethal concentration, as one of the four ecotoxicological properties, the synthesis specific predictors seem to be good estimators. For all other ecotoxicological properties quantum chemical descriptors appear as the more suitable estimators.

Ecosystem↗
PubMedDate not supplied

Counterexamples in chemical ring perception.

Ring information is a large part of the structural topology used to identify and characterize molecular structures. It is hence of crucial importance to obtain this information for a variety of tasks in computational chemistry. Many different approaches for "ring perception", i.e., the extraction of cycles from a molecular graph, have been described. The chemistry literature on this topic, however, reports a surprisingly large number of incorrect statements about the properties of chemically relevant ring sets and, in particular, about the mutual relationships of different sets of cycles in a graph. In part these problems seem to have arisen from a sometimes rather idiosyncratic terminology for notions that are fairly standard in graph theory. In this contribution we translate the definitions of concepts such as the Smallest Set of Smallest Rings, Essential Set of Essential Rings, Extended Set of Smallest Rings, Set of Smallest Cycles at Edges, Set of Elementary Rings, K-rings, and beta-rings into a more widely used mathematical language. We then outline the basic properties of different cycle sets and provide numerous counterexamples to incorrect claims in the published literature. These counterexamples may have a serious practical impact because at least some of them are molecular graphs of well-known molecules. As a consequence, we propose a catalog of desirable properties for chemically useful sets of rings.

Journal Article↗
PubMed2003

Global snapshot of a protein interaction network-a percolation based approach.

MOTIVATION: Biologically significant information can be revealed by modeling large-scale protein interaction data using graph theory based network analysis techniques. However, the methods that are currently being used draw conclusions about the global features of the network from local connectivity data. A more systematic approach would be to define global quantities that measure (1) how strongly a protein ties with the other parts of the network and (2) how significantly an interaction contributes to the integrity of the network, and connect them with phenotype data from other sources. In this paper, we introduce such global connectivity measures and develop a stochastic algorithm based upon percolation in random graphs to compute them. RESULTS: We show that, in terms of global connectivities, the distribution of essential proteins is distinct from the background. This observation highlights a fundamental difference between the essential and the non-essential proteins in the network. We also find that the interaction data obtained from different experimental methods such as immunoprecipitation and two-hybrid techniques contribute differently to network integrities. Such difference between different experimental methods can provide insight into the systematic bias present among these techniques. SUPPLEMENTARY INFORMATION: The full list of our results can be found in the supplemental web site http://www.nas.nasa.gov/Groups/SciTech/nano/msamanta/projects/percolation/index.php

Algorithms↗
PubMed2005

Graph operations and synchronization of complex networks.

The effects of graph operations on the synchronization of coupled dynamical systems are studied. The operations range from addition or deletion of links to various ways of combining networks and generating larger networks from simpler ones. Methods from graph theory are used to calculate or estimate the eigenvalues of the Laplacian operator, which determine the synchronizability of continuous or discrete time dynamics evolving on the network. Results are applied to explain numerical observations on random, scale-free, and small-world networks. An interesting feature is that, when two networks are combined by adding links between them, the synchronizability of the resulting network may worsen as the synchronizability of the individual networks is improved. Similarly, adding links to a network may worsen its synchronizability, although it decreases the average distance in the graph.

Journal Article↗