  With recent advances in high-throughput cell biology the amount of cellular
biological data has grown drastically. Such data is often modeled as graphs
(also called networks) and studying them can lead to new insights into
molecule-level organization. A possible way to understand their structure is by
analysing the smaller components that constitute them, namely network motifs
and graphlets. Graphlets are particularly well suited to compare networks and
to assess their level of similarity but are almost always used as small
undirected graphs of up to five nodes, thus limiting their applicability in
directed networks. However, a large set of interesting biological networks such
as metabolic, cell signaling or transcriptional regulatory networks are
intrinsically directional, and using metrics that ignore edge direction may
gravely hinder information extraction. The applicability of graphlets is
extended to directed networks by considering the edge direction of the
graphlets. We tested our approach on a set of directed biological networks and
verified that they were correctly grouped by type using directed graphlets.
However, enumerating all graphlets in a large network is a computationally
demanding task. Our implementation addresses this concern by using a
state-of-the-art data structure, the g-trie, which is able to greatly reduce
the necessary computation. We compared our tool, gtrieScanner, to other
state-of-the art methods and verified that it is the fastest general tool for
graphlet counting.
