Academic Bibliography

 Search 200 years of publications by Ghent University researchers.
Advanced search
1 file | 1.81 MB
Add to list
  1. Search results
  2. Optimising orbit counting of arbitrar...

Optimising orbit counting of arbitrary order by equation selection

Ine Melckenbeeck, P. Audenaert (UGent) , Thomas Van Parys (UGent) , Yves Van de Peer (UGent) , Didier Colle (UGent) and Mario Pickavet (UGent)
(2019) BMC BIOINFORMATICS. 20.
Author
Organization
Abstract
Background: Graphlets are useful for bioinformatics network analysis. Based on the structure of Hočevar and Demšar’s ORCA algorithm, we have created an orbit counting algorithm, named Jesse. This algorithm, like ORCA, uses equations to count the orbits, but unlike ORCA it can count graphlets of any order. To do so, it generates the required internal structures and equations automatically. Many more redundant equations are generated, however, and Jesse’s running time is highly dependent on which of these equations are used. Therefore, this paper aims to investigate which equations are most efficient, and which factors have an effect on this efficiency. Results: With appropriate equation selection, Jesse’s running time may be reduced by a factor of up to 2 in the best case, compared to using randomly selected equations. Which equations are most efficient depends on the density of the graph, but barely on the graph type. At low graph density, equations with terms in their right-hand side with few arguments are more efficient, whereas at high density, equations with terms with many arguments in the right-hand side are most efficient. At a density between 0.6 and 0.7, both types of equations are about equally efficient. Conclusions: Our Jesse algorithm became up to a factor 2 more efficient, by automatically selecting the best equations based on graph density. It was adapted into a Cytoscape App that is freely available from the Cytoscape App Store to ease application by bioinformaticians.
Keywords
graph theory, graphlets, orbits, equations, optimisation, Cytoscape App, SCALE-FREE

Downloads

  • Download
    Melckenbeeck et al. (2019) BMC Bioinformatics 20,27.pdf
    • full text
    • |
    • open access
    • |
    • PDF
    • |
    • 1.81 MB

Citation

Please use this url to cite or link to this publication:

MLA
Melckenbeeck, Ine, et al. “Optimising Orbit Counting of Arbitrary Order by Equation Selection.” BMC BIOINFORMATICS, vol. 20, 2019, doi:10.1186/s12859-018-2483-9.
APA
Melckenbeeck, I., Audenaert, P., Van Parys, T., Van de Peer, Y., Colle, D., & Pickavet, M. (2019). Optimising orbit counting of arbitrary order by equation selection. BMC BIOINFORMATICS, 20. https://doi.org/10.1186/s12859-018-2483-9
Chicago author-date
Melckenbeeck, Ine, P. Audenaert, Thomas Van Parys, Yves Van de Peer, Didier Colle, and Mario Pickavet. 2019. “Optimising Orbit Counting of Arbitrary Order by Equation Selection.” BMC BIOINFORMATICS 20. https://doi.org/10.1186/s12859-018-2483-9.
Chicago author-date (all authors)
Melckenbeeck, Ine, P. Audenaert, Thomas Van Parys, Yves Van de Peer, Didier Colle, and Mario Pickavet. 2019. “Optimising Orbit Counting of Arbitrary Order by Equation Selection.” BMC BIOINFORMATICS 20. doi:10.1186/s12859-018-2483-9.
Vancouver
1.
Melckenbeeck I, Audenaert P, Van Parys T, Van de Peer Y, Colle D, Pickavet M. Optimising orbit counting of arbitrary order by equation selection. BMC BIOINFORMATICS. 2019;20.
IEEE
[1]
I. Melckenbeeck, P. Audenaert, T. Van Parys, Y. Van de Peer, D. Colle, and M. Pickavet, “Optimising orbit counting of arbitrary order by equation selection,” BMC BIOINFORMATICS, vol. 20, 2019.
@article{8584069,
  abstract     = {{Background: Graphlets are useful for bioinformatics network analysis. Based on the structure of Hočevar and Demšar’s ORCA algorithm, we have created an orbit counting algorithm, named Jesse. This algorithm, like ORCA, uses equations to count the orbits, but unlike ORCA it can count graphlets of any order. To do so, it generates the required internal structures and equations automatically. Many more redundant equations are generated, however, and Jesse’s running time is highly dependent on which of these equations are used. Therefore, this paper aims to investigate which equations are most efficient, and which factors have an effect on this efficiency.
Results: With appropriate equation selection, Jesse’s running time may be reduced by a factor of up to 2 in the best case, compared to using randomly selected equations. Which equations are most efficient depends on the density of the graph, but barely on the graph type. At low graph density, equations with terms in their right-hand side with few arguments are more efficient, whereas at high density, equations with terms with many arguments in the right-hand side are most efficient. At a density between 0.6 and 0.7, both types of equations are about equally efficient.
Conclusions: Our Jesse algorithm became up to a factor 2 more efficient, by automatically selecting the best equations based on graph density. It was adapted into a Cytoscape App that is freely available from the Cytoscape App Store to ease application by bioinformaticians.}},
  articleno    = {{27}},
  author       = {{Melckenbeeck, Ine and Audenaert, P. and Van Parys, Thomas and Van de Peer, Yves and Colle, Didier and Pickavet, Mario}},
  issn         = {{1471-2105}},
  journal      = {{BMC BIOINFORMATICS}},
  keywords     = {{graph theory,graphlets,orbits,equations,optimisation,Cytoscape App,SCALE-FREE}},
  language     = {{eng}},
  pages        = {{13}},
  title        = {{Optimising orbit counting of arbitrary order by equation selection}},
  url          = {{http://doi.org/10.1186/s12859-018-2483-9}},
  volume       = {{20}},
  year         = {{2019}},
}
Altmetric
View in Altmetric
Web of Science
Times cited: