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 289 records · Page 16Linked to original sources
PubMed2004

Functional topology in a network of protein interactions.

MOTIVATION: The building blocks of biological networks are individual protein-protein interactions (PPIs). The cumulative PPI data set in Saccharomyces cerevisiae now exceeds 78 000. Studying the network of these interactions will provide valuable insight into the inner workings of cells. RESULTS: We performed a systematic graph theory-based analysis of this PPI network to construct computational models for describing and predicting the properties of lethal mutations and proteins participating in genetic interactions, functional groups, protein complexes and signaling pathways. Our analysis suggests that lethal mutations are not only highly connected within the network, but they also satisfy an additional property: their removal causes a disruption in network structure. We also provide evidence for the existence of alternate paths that bypass viable proteins in PPI networks, while such paths do not exist for lethal mutations. In addition, we show that distinct functional classes of proteins have differing network properties. We also demonstrate a way to extract and iteratively predict protein complexes and signaling pathways. We evaluate the power of predictions by comparing them with a random model, and assess accuracy of predictions by analyzing their overlap with MIPS database. CONCLUSIONS: Our models provide a means for understanding the complex wiring underlying cellular function, and enable us to predict essentiality, genetic interaction, function, protein complexes and cellular pathways. This analysis uncovers structure-function relationships observable in a large PPI network.

Algorithms↗
PubMed2025

SPC: a SPectral Component approach leveraging Identity-by-Descent graphs to address recent population structure in genomic analysis.

Population structure is a well-known confounder in statistical genetics, particularly in genome-wide association studies (GWAS), where it can lead to inflated test statistics and spurious associations. Traditional methods, such as principal components (PCs), commonly used to adjust for population structure, are limited in capturing fine-scale, non-linear patterns that arise from recent demographic events - patterns that are crucial for understanding rare variant effects. To address this challenge, we propose a novel method called SPectral Components (SPCs), which leverages identity-by-descent (IBD) graphs to capture and transform local, non-linear fine-scale population structure into continuous representations that can be seamlessly integrated into genetic analysis pipelines. Using both simulated datasets and empirical data from the UK Biobank (N ≈ 420,000), we demonstrate that SPCs outperform PCs in adjusting for fine-scale population structure. In simulations, SPCs explained over 90% of the fine-scale population structure with fewer components, while PCs captured less than 5%. In the UK Biobank, SPCs reduced the inflation of p-values in the GWAS of an environmental-driven phenotype by 12% compared to PCs, while maintaining a similar performance to PCs in height, a highly heritable phenotype. Additionally, SPCs improved rare variant association analyses, reducing genomic inflation (e.g., from 7.6 to 1.2 in one analysis), and provided more accurate heritability estimates. Spatial autocorrelation analysis further confirmed the ability of SPCs to account for environmental effects, reducing Moran's I for both environmental and heritable phenotypes more effectively than PCs. Overall, our findings demonstrate that SPCs provide a robust, scalable adjustment for recent population structure, offering a powerful alternative or complement to PCs in large-scale biobank studies.

GWAS↗
PubMed2005

threo-2-(2,6-dimethoxyphenoxy)-1-(4-hydroxy-3,5-dimethoxyphenyl)propane-1,3-diol: a conformational study.

In the crystal structure of the title compound, C19H24O8, the molecules adopt a conformation in which the bulky 2,6-dimethoxyphenoxy and 4-hydroxy-3,5-dimethoxyphenyl groups are almost as far apart as possible. The C(aryl)...C(aryl) distance is 4.8766 (19) A, which is close to the calculated maximum value (4.92 A). The C(aryl)-C-C-O(aryloxy) torsion angle is 173.76 (11) degrees and the C(benzylic)-C-O-C(aryl) torsion angle is 149.09 (11) degrees. The conformation is compared with those of related lignin model compounds. The hydrogen-bonding pattern is discussed in terms of graph-set theory.

Crystallography, X-Ray↗
PubMedDate not supplied

Crest lines for surface segmentation and flattening.

We present a method for extracting feature curves called crest lines from a triangulated surface. Then, we calculate the geodesic Voronoi diagram of crest lines to segment the surface into several regions. Afterward, barycentric surface flattening using theory from graph embeddings is implemented and, using the Geodesic Voronoi diagram, we develop a faster surface flattening algorithm.

Algorithms↗
PubMedDate not supplied

[Several kinetic features of nitrogenase reactions].

The dependence of the nitrogen reduction rate on N2-concentration under high nitrogen pressures was measured. The reason for the sharp break of the Arrenius curves in nitrogenase reactions at 20 degrees C was examined. The influence of nitrogen on isotope effect catalyzed by nitrogenase was studied. The kinetic schemes that explain the peculiarities of the nitrogenase reactions were analyzed by the graph's theory. On the base of new conception of inhibitor-"interceptor" of electrons the literature data were discussed.

Binding Sites↗
PubMed2001

Random graphs with arbitrary degree distributions and their applications.

Recent work on the structure of social networks and the internet has focused attention on graphs with distributions of vertex degree that are significantly different from the Poisson degree distributions that have been widely studied in the past. In this paper we develop in detail the theory of random graphs with arbitrary degree distributions. In addition to simple undirected, unipartite graphs, we examine the properties of directed and bipartite graphs. Among other results, we derive exact expressions for the position of the phase transition at which a giant component first forms, the mean component size, the size of the giant component if there is one, the mean number of vertices a certain distance away from a randomly chosen vertex, and the average vertex-vertex distance within a graph. We apply our theory to some real-world graphs, including the world-wide web and collaboration graphs of scientists and Fortune 1000 company directors. We demonstrate that in some cases random graphs with appropriate distributions of vertex degree predict with surprising accuracy the behavior of the real world, while in others there is a measurable discrepancy between theory and reality, perhaps indicating the presence of additional social structure in the network that is not captured by the random graph.

Journal Article↗
PubMed1977

Food webs and the dimensionality of trophic niche space.

If the trophic niche of a kind of organism is a connected region in niche space, then it is possible for trophic niche overlaps to be described in a one-dimensional niche space if and only if the trophic niche overlap graph is an interval graph. An analysis of 30 food webs, using the combinatorial theory of interval graphs, suggests that a niche space of dimension 1 suffices, with unexpectedly high frequency and perhaps always, to describe the trophic niche overlaps implied by real food webs in single habitats. Consequently, real food webs fall in a small subset of the set of mathematically possible food webs. That real food webs are compatible with one-dimensional trophic niche spaces, more often than can be explained by chance alone, has not been noticed previously.

Journal Article↗
PubMed2000

Noise in hysteretic systems and stochastic processes on graphs

It is shown that the theory of stochastic diffusion processes on graphs is a natural tool for the analysis of noise in hysteretic systems. In particular, by using this theory, analytical expressions for stationary characteristics of random outputs of some hysteretic systems are derived.

Journal Article↗
PubMed2002

Leading off-diagonal correction to the form factor of large graphs.

Using periodic-orbit theory beyond the diagonal approximation we investigate the form factor, K(tau), of a generic quantum graph with mixing classical dynamics and time-reversal symmetry. We calculate the contribution from pairs of self-intersecting orbits that differ from each other only in the orientation of a single loop. In the limit of large graphs, these pairs produce a contribution -2tau(2) to the form factor which agrees with random-matrix theory.

Journal Article↗
PubMed1992

Schematic methods for probabilistic enzyme kinetics.

The theory of steady-state enzyme processes which avoids using the mass action law of chemical kinetics and consistently describes catalytic mechanisms by probabilistic concepts has recently been proposed (Mazur, 1991, J. theor. Biol. 148, 229-242). To facilitate the analysis of complex reaction graphs by this theory the possibility of constructing schematic rules similar to those used in classical kinetics is studied. It is found that due to the similarity of algebraic procedures the popular method of King & Altman can be applied in probabilistic kinetics in addition to the earlier proposed rule based on enumeration of cycles of the reaction graph. This similarity also allows one to adapt many other shortcut methods of classical kinetics for probabilistic reaction graphs. The paper considers separately the possibility of transforming reaction mechanisms so that the initial graph is replaced by a simpler but equivalent one. It is shown that there are few cases when a group of states can be replaced by one united state, with earlier known rules such as the rule of Cha for equilibrium stages being particular cases of a more general procedure. In addition a novel method is proposed which performs step-by-step reduction of any reaction graph. All the new methods can be adapted for traditional kinetics as well. The results obtained demonstrate that many schematic rules of classical kinetics are of probabilistic origin.

Enzymes↗
PubMed2003

Accelerating screening of 3D protein data with a graph theoretical approach.

MOTIVATION: The Dictionary of Interfaces in Proteins (DIP) is a database collecting the 3D structure of interacting parts of proteins that are called patches. It serves as a repository, in which patches similar to given query patches can be found. The computation of the similarity of two patches is time consuming and traversing the entire DIP requires some hours. In this work we address the question of how the patches similar to a given query can be identified by scanning only a small part of DIP. The answer to this question requires the investigation of the distribution of the similarity of patches. RESULTS: The score values describing the similarity of two patches can roughly be divided into three ranges that correspond to different levels of spatial similarity. Interestingly, the two iso-score lines separating the three classes can be determined by two different approaches. Applying a concept of the theory of random graphs reveals significant structural properties of the data in DIP. These can be used to accelerate scanning the DIP for patches similar to a given query. Searches for very similar patches could be accelerated by a factor of more than 25. Patches with a medium similarity could be found 10 times faster than by brute-force search.

Algorithms↗
PubMed2005

Phase transitions in the neuropercolation model of neural populations with mixed local and non-local interactions.

We model the dynamical behavior of the neuropil, the densely interconnected neural tissue in the cortex, using neuropercolation approach. Neuropercolation generalizes phase transitions modeled by percolation theory of random graphs, motivated by properties of neurons and neural populations. The generalization includes (1) a noisy component in the percolation rule, (2) a novel depression function in addition to the usual arousal function, (3) non-local interactions among nodes arranged on a multi-dimensional lattice. This paper investigates the role of non-local (axonal) connections in generating and modulating phase transitions of collective activity in the neuropil. We derived a relationship between critical values of the noise level and non-locality parameter to control the onset of phase transitions. Finally, we propose a potential interpretation of ontogenetic development of the neuropil maintaining a dynamical state at the edge of criticality.

Algorithms↗
PubMed1999

The application of thermodynamic principles to histochemical and morphometric tissue research: principles and practical outline with focus on the glycosciences.

Physicochemical terms such as entropy or current of entropy are commonly used to refer solely to the description of reactions in the realm of chemistry and physics. Since these thermodynamic terms have a predictive value for the further course of development of such reactions, e.g., extent of a chemical reaction or affinity of molecular interactions, it is tempting to introduce the respective algorithms to biological problems. By combining quantitative morphology with the histochemical visualization of distinct cellular and textural properties such as nuclear DNA contents or intensity of histochemical staining, equations from the general theory of thermodynamics can be adapted. They permit appropriate calculations to be performed which introduce the entropy concept to the processing of the information collected by analysis of structures formed by histochemically labeling cells. The theory of weighted graphs offers the appropriate mathematical tools. Nuclei are defined as vertices. Their DNA contents measured by the integrated optical density or additional cellular features (for example staining intensity of applied immuno-/ligandohistochemical probes) define the associated weights and the minimum spanning tree as a derivative from Voronoi's theorem for the definition of the geometrical neighborhood. This technique is equivalent to syntactic structure analysis as developed by Lu and Fu (1978), Sanfeliu et al. (1981), Kayser and Schlegel (1982), and Kayser (1988). Assuming that the texture of a healthy tissue is displayed in the energetically most efficient and stable manner to perform the required biological functions, i.e., to maintain the lowest level of entropy, deviations from this level are reflected in differences in distances and weights between neighboring nuclei or cells. The measure of textural differences in relation to the normal appearance of an organ or tissue is denoted as structural entropy. Since organisms or their compartments are thermodynamically open systems, they are insufficiently described by the (structural) entropy. This parameter only provides a snapshot, with no information about the status of entropy changes from a directed exchange with the environment. The current of entropy, which is equivalent to the amount of entropy exported or imported through a boundary, is an appropriate measure of the "thermodynamic distance" of the system under consideration from its environment, as is readily appreciated for tumors. A solid tumor is a biological system embedded in another one (healthy tissue). Its current of entropy can be calculated if its boundary and proliferative activity are known. This parameter can be measured by histochemical methods (Ki-67 antibody) or from the cytometric characteristics (percentage of S-phase-related tumor cells), and the boundary can be measured by the volume fraction of the internal vessels and the size of the external surface of the tumor. Since biochemical factors will contribute to the generation and establishment of these structural and thermodynamic features at the level of tissue organization, histochemical studies can uncover the correlation with these parameter alterations. Taking glycohistochemical determinants as an example for this hypothesis, the potential value of combining the results of immuno-/ligandohistochemistry with the data derived from the cytometric or syntactic structure analysis measurements and from the calculations based on thermodynamic theorems is illustrated.

Animals↗
PubMed2005

Bayesian networks and probabilistic reasoning about scientific evidence when there is a lack of data.

Bayesian networks (BNs) are a kind of graphical model that formally combines elements of graph and probability theory. BNs are a mathematically and statistically rigorous technique allowing their user to define a pictorial representation of assumed dependencies and influences among a set of variables deemed to be relevant for a particular inferential problem. The formalism allows one to process newly acquired evidence according to the rules of probability calculus. Applications of BNs have been reported in various forensic disciplines. However, there seems to be some reluctance to consider BNs as a more general framework for representing and evaluating sources of uncertainties associated with scientific evidence. Notably, BNs are widely thought of as an essentially numerical method, requiring "exact" numbers with a high "accuracy". The present paper aims to draw the reader's attention to the point that the availability of hard numerical data is not a necessary requirement for using BNs in forensic science. An abstraction of quantitative BNs, known as qualitative probabilistic networks (QPNs), and sensitivity analyses are presented and their potential applications discussed. As a main difference to their quantitative counterpart, QPNs contain qualitative probabilistic relationships instead of numerical relations. Sensitivity analyses consist of varying the probabilities assigned to one or more variables and evaluating the effect on one or more other variables of interest. Both QPNs and sensitivity analyses appear to be useful concepts that permit one to work in contexts with acute lack of numerical data and where reasoning consistent with the laws of probability should nevertheless be performed.

Journal Article↗
PubMed1972

Enzyme kinetics. Systematic generation of valid King-Altman patterns.

One of the most generally applicable algorithms for the derivation of steady-state rate equations for complex enzyme reaction mechanisms is that of King and Altman. Several modifications of this algorithm have been suggested; however, each requires the generation of numerous valid and invalid patterns and the subsequent elimination of those that are invalid. A method is presented, employing topological theory of linear graphs, for the systematic generation of only those patterns which are valid. This method is readily adaptable to use on a digital computer. An independent method for the calculation of the number of valid patterns is also presented. This calculation can be used to substantiate the accuracy of the patterns obtained. This calculation is also adaptable to computerization. Examples are included to demonstrate both the generation of patterns and the calculation of their number for specific enzyme mechanisms.

Computers↗
PubMed2006

Integrating multi-attribute similarity networks for robust representation of the protein space.

MOTIVATION: A global view of the protein space is essential for functional and evolutionary analysis of proteins. In order to achieve this, a similarity network can be built using pairwise relationships among proteins. However, existing similarity networks employ a single similarity measure and therefore their utility depends highly on the quality of the selected measure. A more robust representation of the protein space can be realized if multiple sources of information are used. RESULTS: We propose a novel approach for analyzing multi-attribute similarity networks by combining random walks on graphs with Bayesian theory. A multi-attribute network is created by combining sequence and structure based similarity measures. For each attribute of the similarity network, one can compute a measure of affinity from a given protein to every other protein in the network using random walks. This process makes use of the implicit clustering information of the similarity network, and we show that it is superior to naive, local ranking methods. We then combine the computed affinities using a Bayesian framework. In particular, when we train a Bayesian model for automated classification of a novel protein, we achieve high classification accuracy and outperform single attribute networks. In addition, we demonstrate the effectiveness of our technique by comparison with a competing kernel-based information integration approach.

Algorithms↗