SEARCH · PubMed Health

Results for “Graph”

Explore indexed PubMed citations for clinical trials, systematic reviews and public health research. Read source abstracts and follow each citation to its original PubMed record.

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

At least 415 records · Page 23Linked to original sources

PubMed2005

Analyzing protein lists with large networks: edge-count probabilities in random graphs with given expected degrees.

We present an analytical framework to analyze lists of proteins with large undirected graphs representing their known functional relationships. We consider edge-count variables such as the number of interactions between a protein and a list, the size of a subgraph induced by a list, and the number of interactions bridging two lists. We derive approximate analytical expressions for the probability distributions of these variables in a model of a random graph with given expected degrees. Probabilities obtained with the analytical expressions are used to mine a protein interaction network for functional modules, characterize the connectedness of protein functional categories, and measure the strength of relations between modules.

Algorithms↗

PubMed2006

De novo analysis of peptide tandem mass spectra by spectral graph partitioning.

We report on a new de novo peptide sequencing algorithm that uses spectral graph partitioning. In this approach, relationships between m/z peaks are represented by attractive and repulsive springs, and the vibrational modes of the spring system are used to infer information about the peaks (such as "likely b-ion" or "likely y-ion"). We demonstrate the effectiveness of this approach by comparison with other de novo sequencers on test sets of ion-trap and QTOF spectra, including spectra of mixtures of peptides. On all datasets, we outperform the other sequencers. Along with spectral graph theory techniques, the new de novo sequencer EigenMS incorporates another improvement of independent interest: robust statistical methods for recalibration of time-of-flight mass measurements. Robust recalibration greatly outperforms simple least-squares recalibration, achieving about three times the accuracy for one QTOF dataset.

Algorithms↗

PubMed1994

An algorithm based on graph theory for the assembly of contigs in physical mapping of DNA.

An algorithm is described for mapping DNA contigs based on an interval graph (IG) representation. In general terms, the input to the algorithm is a set of binary overlapping relations among finite intervals spread along a real line, from which the algorithm generates sets of ordered overlapping fragments spanning that line. The implications of a more general case of the IG, called a probe interval graph (PIG), in which only a subset of cosmids are used as probes, are also discussed. In the specific case of cosmids hybridizing to regions of a YAC, the algorithm takes cross-hybridization information using the cosmids as probes, and orders them along the YAC; if gaps exist due to insufficient coverage of cosmid contigs along the length of the YAC, repetitive use of the algorithm generates sets of ordered overlapping fragments. Both the IG and the PIG can expose problems caused by false overlaps, such as hybridizations due to repetitive elements. The algorithm, has been coded in C; CPU time is essentially linear with respect to the number of cosmids analyzed. Results are presented for the application of a PIG to cosmid contig assembly along a human chromosome 13-specific YAC. An alignment of 67 cosmids spanning a YAC took 0.28 seconds of CPU time on a Convex 220 computer.

Algorithms↗

PubMed1999

Revealing hidden interval graph structure in STS-content data.

MOTIVATION: STS-content data for genomic mapping contain numerous errors and anomalies resulting in cross-links among distant regions of the genome. Identification of contigs within the data is an important and difficult problem. RESULTS: This paper introduces a graph algorithm which creates a simplified view of STS-content data. The shape of the resulting structure graph provides a quality check - coherent data produce a straight line, while anomalous data produce branches and loops. In the latter case, it is sometimes possible to disentangle the various paths into subsets of the data covering contiguous regions of the genome, i.e. contigs. These straight subgraphs can then be analyzed in standard ways to construct a physical map. A theoretical basis for the method is presented along with examples of its application to current STS data from human genome centers. AVAILABILITY: Freely available on request.

Algorithms↗

PubMed2025

monarchr: an R package for querying biomedical knowledge graphs.

SUMMARY: Biomedical knowledge graphs (KGs) aggregate and provide a wealth of information, linking genes and their variants, diseases, phenotypes, and much more. While these data are available in raw and API-hosted form, to date, functionality for working with KGs in the R programming language has been limited. We introduce monarchr, a package for querying and manipulating KG data. Support for the expansive Monarch Initiative KG is built in, and monarchr can accommodate any KG in the Knowledge Graph eXchange (KGX) format. This tidy-inspired interface offers researchers an intuitive, iterative approach to querying and visualizing KG data. AVAILABILITY AND IMPLEMENTATION: Source code, documentation, and installation instructions are available at https://github.com/monarch-initiative/monarchr.

Software↗

PubMed2026

EPIC: Event Prototyping via Information Constrained graph learning for personalized cancer driver gene prediction.

MOTIVATION: Precision oncology relies on accurately distinguishing patient-specific driver mutations from the vast background of passenger alterations. While graph-based computational methods have emerged as powerful tools for this task, they often struggle to preserve the distinct genomic context of individual mutations within complex biological networks. Consequently, subtle patient-specific driver signals are frequently obscured by dominant topological patterns, critically impeding the identification of individualized oncogenic events essential for personalized cancer therapy. RESULTS: To address this, we propose EPIC, a novel framework for Event Prototyping via Information Constrained Graph Learning. Unlike traditional node-centric approaches, EPIC redefines driver prediction as a metric learning task in an event embedding space. We introduce an information-constrained learning strategy that imposes explicit geometric constraints on feature variance, effectively preventing feature collapse and ensuring that low-frequency driver signals are distinctively preserved. Experiments on large-scale cancer cohorts demonstrate that EPIC significantly outperforms established baselines. Notably, the model prioritizes low-frequency driver variants typically overlooked by population-based methods, mapping them to critical oncogenic mechanisms associated with drug resistance and metastasis. Furthermore, clinical actionability analysis confirms that EPIC substantially expands the patient population eligible for targeted therapies. EPIC provides a robust and context-aware solution for personalized cancer driver discovery, bridging the gap between genomic data and actionable therapeutic insights. AVAILABILITY AND IMPLEMENTATION: The source code and datasets are available at https://github.com/spcho-dev/EPIC.

Humans↗

PubMed2026

VirBinn improves viral genome binning from metagenomic Hi-C through graph diffusion.

MOTIVATION: Metagenomic Hi-C provides in situ proximity signals that can improve genome binning and enable virus-host-association analysis. However, viral genome recovery remains difficult because virus-virus Hi-C contact matrices are extremely sparse. Viral genomes are small, often low-abundance, and frequently assemble into short contigs, leaving many true within-genome links unobserved and causing viral bins to fragment. RESULTS: We present VirBinn, a graph-diffusion framework for viral binning from metagenomic Hi-C. VirBinn enhances virus-virus connectivity through two complementary mechanisms: random-walk-with-restart enhancement on the sparse virus-virus contact graph and host-guided diffusion that propagates viral seeds through the host network to infer indirect virus-virus associations. The enhanced views are integrated and clustered using Leiden community detection to produce viral metagenome-assembled genomes (vMAGs). On dataset-specific simulation benchmarks with ground truth, VirBinn consistently recovers more high-quality vMAGs than Hi-C-based and shotgun-based baselines and substantially increases the number of near-complete genomes. On four real metagenomic Hi-C datasets spanning human gut, pig gut, sheep gut (long-read assembly), and wastewater, VirBinn yields more high-completeness vMAGs under CheckV and produces bins with strong within-cluster contact support. Finally, host linkage analysis using reconstructed host MAGs reveals habitat-specific host-association patterns and plausible host taxonomic profiles. AVAILABILITY AND IMPLEMENTATION: VirBinn is available at https://github.com/dyxstat/VirBinn. The scripts to reproduce the results and figures in this article are available at https://github.com/dyxstat/Reproduce_VirBinn.

Genome, Viral↗

PubMed2026

GT-Mamba: a Topology-Aware Graph-State space model for robust and interpretable epigenetic age prediction.

MOTIVATION: Current epigenetic clocks face a trade-off between predictive accuracy and biological interpretability, often relying on dataset-specific correction to generalize across cohorts. We propose GT-Mamba, a novel architecture that integrates a Structure-Aware Graph Transformer with the Mamba state space model. This design captures CpG topological correlations and genome-wide long-range dependencies. RESULTS: GT-Mamba demonstrates strong out-of-the-box robustness across heterogeneous independent validation cohorts, achieving a weighted average MAE of 4.43 years. Notably, it effectively generalizes to EPIC 850k arrays despite partial feature missingness, and maintains consistent performance across homologous age distribution shifts (MAE 2.94 years in a young cohort). Ablation studies confirm that graph topology contributes to improved robustness against noise. Mechanistic analysis suggests that the model captures methylation patterns associated with both developmental and functional processes. AVAILABILITY: Source code and pre-trained models are freely available at https://github.com/NENUBioCompute/GT-Mamba and archived on Zenodo (DOI: 10.5281/zenodo.19703155).

Epigenesis, Genetic↗

PubMed2004

Graph-based clustering for finding distant relationships in a large set of protein sequences.

MOTIVATION: Clustering of protein sequences is widely used for the functional characterization of proteins. However, it is still not easy to cluster distantly-related proteins, which have only regional similarity among their sequences. It is therefore necessary to develop an algorithm for clustering such distantly-related proteins. RESULTS: We have developed a time and space efficient clustering algorithm. It uses a graph representation where its vertices and edges denote proteins and their sequence similarities above a certain cutoff score, respectively. It repeatedly partitions the graph by removing edges that have small weights, which correspond to low sequence similarities. To find the appropriate partitions, we introduce a score combining the normalized cut and a locally minimal cut capacities. Our method is applied to the entire 40,703 human proteins in SWISS-PROT and TrEMBL. The resulting clusters shows a 76% recall (20,529 proteins) of the 26,917 classified by InterPro. It also finds relationships not found by other clustering methods. AVAILABILITY: The complete result of our algorithm for all the human proteins in SWISS-PROT and TrEMBL, and other supplementary information are available at http://motif.ics.es.osaka-u.ac.jp/Ncut-KL/

Algorithms↗

PubMed2004

A graph-theoretic approach to testing associations between disparate sources of functional genomics data.

MOTIVATION: The last few years have seen the advent of high-throughput technologies to analyze various properties of the transcriptome and proteome of several organisms. The congruency of these different data sources, or lack thereof, can shed light on the mechanisms that govern cellular function. A central challenge for bioinformatics research is to develop a unified framework for combining the multiple sources of functional genomics information and testing associations between them, thus obtaining a robust and integrated view of the underlying biology. RESULTS: We present a graph-theoretic approach to test the significance of the association between multiple disparate sources of functional genomics data by proposing two statistical tests, namely edge permutation and node label permutation tests. We demonstrate the use of the proposed tests by finding significant association between a Gene Ontology-derived predictome and data obtained from mRNA expression and phenotypic experiments for Saccharomyces cerevisiae. Moreover, we employ the graph-theoretic framework to recast a surprising discrepancy presented elsewhere between gene expression and knockout phenotype, using expression data from a different set of experiments. AVAILABILITY: An R software package, GraphAT, containing the data and statistical procedures is available from Bioconductor: http://www.bioconductor.org.

Algorithms↗

PubMed2005

Augmented cell-graphs for automated cancer diagnosis.

This work reports a novel computational method based on augmented cell-graphs (ACG), which are constructed from low-magnification tissue images for the mathematical diagnosis of brain cancer (malignant glioma). An ACG is a simple, undirected, weighted and complete graph in which a node represents a cell cluster and an edge between a pair of nodes defines a binary relationship between them. Both the nodes and the edges of an ACG are assigned weights to capture more information about the topology of the tissue. In this work, the experiments are conducted on a dataset that is comprised of 646 human brain biopsy samples from 60 different patients. It is shown that the ACG approach yields sensitivity of 97.53% and specificities of 93.33 and 98.15% (for the inflamed and healthy, respectively) at the tissue level in glioma diagnosis.

Algorithms↗

PubMed2004

A graph based algorithm for generating EST consensus sequences.

MOTIVATION: EST sequences constitute an abundant, yet error prone resource for computational biology. Expressed sequences are important in gene discovery and identification, and they are also crucial for the discovery and classification of alternative splicing. An important challenge when processing EST sequences is the reconstruction of mRNA by assembling EST clusters into consensus sequences. RESULTS: In contrast to the more established assembly tools, we propose an algorithm that constructs a graph over sequence fragments of fixed size, and produces consensus sequences as traversals of this graph. We provide a tool implementing this algorithm, and perform an experiment where the consensus sequences produced by our implementation, as well as by currently available tools, are compared to mRNA. The results show that our proposed algorithm in a majority of the cases produces consensus of higher quality than the established sequence assemblers and at a competitive speed. AVAILABILITY: The source code for the implementation is available under a GPL license from http://www.ii.uib.no/~ketil/bioinformatics/ CONTACT: ketil@ii.uib.no.

Algorithms↗

PubMed2004

An enhanced Java graph applet interface for visualizing interactomes.

UNLABELLED: We have developed several new navigation features for a Java graph applet previously released for visualizing protein-protein interactions. This graph viewer can be used to navigate any molecular interactome dataset. We have successfully implemented this tool for exploring protein networks stored in the Bioverse interaction database. AVAILABILITY: http://bioverse.compbio.washington.edu/viewer CONTACT: ram@compbio.washington.edu.

Animals↗

PubMed2005

Medusa: a simple tool for interaction graph analysis.

SUMMARY: Medusa is a Java application for visualizing and manipulating graphs of interaction, such as data from the STRING database. It features an intuitive user interface developed with the help of biologists. Medusa is optimized for accessing protein interaction data from STRING, but can be used for any type of graph from any scientific field.

Algorithms↗

PubMed2005

Syntons, metabolons and interactons: an exact graph-theoretical approach for exploring neighbourhood between genomic and functional data.

MOTIVATION: Modern comparative genomics does not restrict to sequence but involves the comparison of metabolic pathways or protein-protein interactions as well. Central in this approach is the concept of neighbourhood between entities (genes, proteins, chemical compounds). Therefore there is a growing need for new methods aiming at merging the connectivity information from different biological sources in order to infer functional coupling. RESULTS: We present a generic approach to merge the information from two or more graphs representing biological data. The method is based on two concepts. The first one, the correspondence multigraph, precisely defines how correspondence is performed between the primary data-graphs. The second one, the common connected components, defines which property of the multigraph is searched for. Although this problem has already been informally stated in the past few years, we give here a formal and general statement together with an exact algorithm to solve it. AVAILABILITY: The algorithm presented in this paper has been implemented in C. Source code is freely available for download at: http://www.inrialpes.fr/helix/people/viari/cccpart.

Algorithms↗

PubMed2006

Graph-based analysis and visualization of experimental results with ONDEX.

MOTIVATION: Assembling the relevant information needed to interpret the output from high-throughput, genome scale, experiments such as gene expression microarrays is challenging. Analysis reveals genes that show statistically significant changes in expression levels, but more information is needed to determine their biological relevance. The challenge is to bring these genes together with biological information distributed across hundreds of databases or buried in the scientific literature (millions of articles). Software tools are needed to automate this task which at present is labor-intensive and requires considerable informatics and biological expertise. RESULTS: This article describes ONDEX and how it can be applied to the task of interpreting gene expression results. ONDEX is a database system that combines the features of semantic database integration and text mining with methods for graph-based analysis. An overview of the ONDEX system is presented, concentrating on recently developed features for graph-based analysis and visualization. A case study is used to show how ONDEX can help to identify causal relationships between stress response genes and metabolic pathways from gene expression data. ONDEX also discovered functional annotations for most of the genes that emerged as significant in the microarray experiment, but were previously of unknown function.

Algorithms↗

PubMed2006

Improved scoring of functional groups from gene expression data by decorrelating GO graph structure.

MOTIVATION: The result of a typical microarray experiment is a long list of genes with corresponding expression measurements. This list is only the starting point for a meaningful biological interpretation. Modern methods identify relevant biological processes or functions from gene expression data by scoring the statistical significance of predefined functional gene groups, e.g. based on Gene Ontology (GO). We develop methods that increase the explanatory power of this approach by integrating knowledge about relationships between the GO terms into the calculation of the statistical significance. RESULTS: We present two novel algorithms that improve GO group scoring using the underlying GO graph topology. The algorithms are evaluated on real and simulated gene expression data. We show that both methods eliminate local dependencies between GO terms and point to relevant areas in the GO graph that remain undetected with state-of-the-art algorithms for scoring functional terms. A simulation study demonstrates that the new methods exhibit a higher level of detecting relevant biological terms than competing methods.

Algorithms↗

PubMed2005

Gradient directed regularization for sparse Gaussian concentration graphs, with applications to inference of genetic networks.

Large-scale microarray gene expression data provide the possibility of constructing genetic networks or biological pathways. Gaussian graphical models have been suggested to provide an effective method for constructing such genetic networks. However, most of the available methods for constructing Gaussian graphs do not account for the sparsity of the networks and are computationally more demanding or infeasible, especially in the settings of high dimension and low sample size. We introduce a threshold gradient descent (TGD) regularization procedure for estimating the sparse precision matrix in the setting of Gaussian graphical models and demonstrate its application to identifying genetic networks. Such a procedure is computationally feasible and can easily incorporate prior biological knowledge about the network structure. Simulation results indicate that the proposed method yields a better estimate of the precision matrix than the procedures that fail to account for the sparsity of the graphs. We also present the results on inference of a gene network for isoprenoid biosynthesis in Arabidopsis thaliana. These results demonstrate that the proposed procedure can indeed identify biologically meaningful genetic networks based on microarray gene expression data.

Arabidopsis↗