Optimising orbit counting of arbitrary order by equation selection
BACKGROUND : Graphlets are useful for bioinformatics network analysis. Based on the structure of Hoˇcevar 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 an...
Published in: | BMC Bioinformatics |
---|---|
Main Authors: | , , , , , |
Format: | Article in Journal/Newspaper |
Language: | English |
Published: |
BioMed Central
2019
|
Subjects: | |
Online Access: | http://hdl.handle.net/2263/75137 https://doi.org/10.1186/s12859-018-2483-9 |
id |
ftunivpretoria:oai:repository.up.ac.za:2263/75137 |
---|---|
record_format |
openpolar |
spelling |
ftunivpretoria:oai:repository.up.ac.za:2263/75137 2023-05-15T17:53:31+02:00 Optimising orbit counting of arbitrary order by equation selection Melckenbeeck, Ine Audenaert, Pieter Van Parys, Thomas Van de Peer, Yves Colle, Didier Pickavet, Mario 2019-01-15 http://hdl.handle.net/2263/75137 https://doi.org/10.1186/s12859-018-2483-9 en eng BioMed Central http://hdl.handle.net/2263/75137 Melckenbeeck, I., Audenaert, P., Van Parys, T. et al. 2019, 'Optimising orbit counting of arbitrary order by equation selection', BMC Bioinformatics, vol. 20, art. 27, pp. 1-13. 1471-2105 (online) doi:10.1186/s12859-018-2483-9 © The Author(s). 2019 Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License. CC-BY Graph theory Graphlets Orbits Equations Optimisation Cytoscape app Article 2019 ftunivpretoria https://doi.org/10.1186/s12859-018-2483-9 2022-05-31T13:23:40Z BACKGROUND : Graphlets are useful for bioinformatics network analysis. Based on the structure of Hoˇcevar 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. CONCLUSION : 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. Ghent University – imec and the European Union Seventh Framework Programme (FP7/2007-2013) – European Research Council Advanced Grant Agreement 322739-DOUBLEUP. https://bmcbioinformatics.biomedcentral.com am2020 Biochemistry Genetics Microbiology and Plant Pathology Article in Journal/Newspaper Orca University of Pretoria: UPSpace BMC Bioinformatics 20 1 |
institution |
Open Polar |
collection |
University of Pretoria: UPSpace |
op_collection_id |
ftunivpretoria |
language |
English |
topic |
Graph theory Graphlets Orbits Equations Optimisation Cytoscape app |
spellingShingle |
Graph theory Graphlets Orbits Equations Optimisation Cytoscape app Melckenbeeck, Ine Audenaert, Pieter Van Parys, Thomas Van de Peer, Yves Colle, Didier Pickavet, Mario Optimising orbit counting of arbitrary order by equation selection |
topic_facet |
Graph theory Graphlets Orbits Equations Optimisation Cytoscape app |
description |
BACKGROUND : Graphlets are useful for bioinformatics network analysis. Based on the structure of Hoˇcevar 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. CONCLUSION : 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. Ghent University – imec and the European Union Seventh Framework Programme (FP7/2007-2013) – European Research Council Advanced Grant Agreement 322739-DOUBLEUP. https://bmcbioinformatics.biomedcentral.com am2020 Biochemistry Genetics Microbiology and Plant Pathology |
format |
Article in Journal/Newspaper |
author |
Melckenbeeck, Ine Audenaert, Pieter Van Parys, Thomas Van de Peer, Yves Colle, Didier Pickavet, Mario |
author_facet |
Melckenbeeck, Ine Audenaert, Pieter Van Parys, Thomas Van de Peer, Yves Colle, Didier Pickavet, Mario |
author_sort |
Melckenbeeck, Ine |
title |
Optimising orbit counting of arbitrary order by equation selection |
title_short |
Optimising orbit counting of arbitrary order by equation selection |
title_full |
Optimising orbit counting of arbitrary order by equation selection |
title_fullStr |
Optimising orbit counting of arbitrary order by equation selection |
title_full_unstemmed |
Optimising orbit counting of arbitrary order by equation selection |
title_sort |
optimising orbit counting of arbitrary order by equation selection |
publisher |
BioMed Central |
publishDate |
2019 |
url |
http://hdl.handle.net/2263/75137 https://doi.org/10.1186/s12859-018-2483-9 |
genre |
Orca |
genre_facet |
Orca |
op_relation |
http://hdl.handle.net/2263/75137 Melckenbeeck, I., Audenaert, P., Van Parys, T. et al. 2019, 'Optimising orbit counting of arbitrary order by equation selection', BMC Bioinformatics, vol. 20, art. 27, pp. 1-13. 1471-2105 (online) doi:10.1186/s12859-018-2483-9 |
op_rights |
© The Author(s). 2019 Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License. |
op_rightsnorm |
CC-BY |
op_doi |
https://doi.org/10.1186/s12859-018-2483-9 |
container_title |
BMC Bioinformatics |
container_volume |
20 |
container_issue |
1 |
_version_ |
1766161221614043136 |