Optimising orbit counting of arbitrary order by equation selection

dc.contributor.authorMelckenbeeck, Ine
dc.contributor.authorAudenaert, Pieter
dc.contributor.authorVan Parys, Thomas
dc.contributor.authorVan de Peer, Yves
dc.contributor.authorColle, Didier
dc.contributor.authorPickavet, Mario
dc.date.accessioned2020-07-10T14:40:07Z
dc.date.available2020-07-10T14:40:07Z
dc.date.issued2019-01-15
dc.description.abstractBACKGROUND : 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.en_ZA
dc.description.departmentBiochemistryen_ZA
dc.description.departmentGeneticsen_ZA
dc.description.departmentMicrobiology and Plant Pathologyen_ZA
dc.description.librarianam2020en_ZA
dc.description.sponsorshipGhent University – imec and the European Union Seventh Framework Programme (FP7/2007-2013) – European Research Council Advanced Grant Agreement 322739-DOUBLEUP.en_ZA
dc.description.urihttps://bmcbioinformatics.biomedcentral.comen_ZA
dc.identifier.citationMelckenbeeck, 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.en_ZA
dc.identifier.issn1471-2105 (online)
dc.identifier.other10.1186/s12859-018-2483-9
dc.identifier.urihttp://hdl.handle.net/2263/75137
dc.language.isoenen_ZA
dc.publisherBioMed Centralen_ZA
dc.rights© The Author(s). 2019 Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License.en_ZA
dc.subjectGraph theoryen_ZA
dc.subjectGraphletsen_ZA
dc.subjectOrbitsen_ZA
dc.subjectEquationsen_ZA
dc.subjectOptimisationen_ZA
dc.subjectCytoscape appen_ZA
dc.titleOptimising orbit counting of arbitrary order by equation selectionen_ZA
dc.typeArticleen_ZA

Files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
Melckenbeeck_Optimising_2019.pdf
Size:
1.73 MB
Format:
Adobe Portable Document Format
Description:
Article

License bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
license.txt
Size:
1.75 KB
Format:
Item-specific license agreed upon to submission
Description: