2015/11/06 by David Aparício, Pedro Ribeiro, Aparício, David +3 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #Bioinformatics and Genomic Networks #Computational Drug Discovery Methods #FOS: Biological sciences #FOS: Computer and information sciences #FOS: Physical sciences #Gene Regulatory Network Analysis #Molecular Networks (q-bio.MN) #Physics and Society (physics.soc-ph) #Social and Information Networks (cs.SI)
paper · pdf · doi:10.48550/arxiv.1511.01964
openalex publication_date 2015/11/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.