Combinatorial algorithm for counting small induced graphs and orbits

Graphlet analysis is an approach to network analysis that is particularly popular in bioinformatics. We show how to set up a system of linear equations that relate the orbit counts and can be used in an algorithm that is significantly faster than the existing approaches based on direct enumeration o...

Full description

Saved in:
Bibliographic Details
Published in:PloS one 2017-02, Vol.12 (2), p.e0171428-e0171428
Main Authors: Demsar, Janez, Hocevar, Tomaz
Format: Article
Language:English
Subjects:
Algorithms
Analysis
Bioinformatics
Biology and Life Sciences
Citations
Combinatorial analysis
Computational biology
Computational Biology - methods
Computer and Information Sciences
Computer Graphics - statistics & numerical data
Computer Simulation
Counting
Data mining
Electronic Data Processing - methods
Empirical analysis
Enumeration
Gene Regulatory Networks
Graphs
Informatics
Information science
International conferences
Linear equations
Mathematical models
Models, Biological
Models, Theoretical
Network analysis
Neural networks
Orbits
Physical Sciences
Protein Interaction Mapping
Proteins
Research and Analysis Methods
Run time (computers)
Social networks
Social Sciences
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:Graphlet analysis is an approach to network analysis that is particularly popular in bioinformatics. We show how to set up a system of linear equations that relate the orbit counts and can be used in an algorithm that is significantly faster than the existing approaches based on direct enumeration of graphlets. The approach presented in this paper presents a generalization of the currently fastest method for counting 5-node graphlets in bioinformatics. The algorithm requires existence of a vertex with certain properties; we show that such vertex exists for graphlets of arbitrary size, except for complete graphs and a cycle with four nodes, which are treated separately. Empirical analysis of running time agrees with the theoretical results.
ISSN:1932-6203
1932-6203
DOI:10.1371/journal.pone.0171428