Abstract:
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.
