Mining the Enriched Subgraphs for Specific Vertices in a Biological Graph

In this paper, we present a subgroup discovery method to find subgraphs in a graph that are associated with a given set of vertices. The association between a subgraph pattern and a set of vertices is defined by its significant enrichment based on a Bonferroni-corrected hypergeometric probability va...

Full description

Saved in:
Bibliographic Details
Published in:IEEE/ACM transactions on computational biology and bioinformatics 2019-09, Vol.16 (5), p.1496-1507
Main Authors: Meysman, Pieter, Saeys, Yvan, Sabaghian, Ehsan, Bittremieux, Wout, Van de Peer, Yves, Goethals, Bart, Laukens, Kris
Format: Article
Language:English
Subjects:
Algorithm design and analysis
Algorithms
Apexes
Computational Biology - methods
Data mining
Data Mining - methods
Diseases
Gene Regulatory Networks
Graph theory
Life sciences
Models, Statistical
Protein engineering
protein graph
Protein Interaction Mapping
Proteins
single graph
Subgraph mining
subgroup discovery
Subgroups
transcriptional regulatory network
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we present a subgroup discovery method to find subgraphs in a graph that are associated with a given set of vertices. The association between a subgraph pattern and a set of vertices is defined by its significant enrichment based on a Bonferroni-corrected hypergeometric probability value. This interestingness measure requires a dedicated pruning procedure to limit the number of subgraph matches that must be calculated. The presented mining algorithm to find associated subgraph patterns in large graphs is therefore designed to efficiently traverse the search space. We demonstrate the operation of this method by applying it on three biological graph data sets and show that we can find associated subgraphs for a biologically relevant set of vertices and that the found subgraphs themselves are biologically interesting.
ISSN:1545-5963
1557-9964
DOI:10.1109/TCBB.2016.2576440