Please use this identifier to cite or link to this item: http://hdl.handle.net/10216/101828
Author(s): Ribeiro, P
Silva, F
Title: G-tries: An efficient data structure for discovering network motifs
Issue Date: 2010
Abstract: In this paper we propose a novel specialized data structure that we call g-trie, designed to deal with collections of subgraphs. The main conceptual idea is akin to a prefix tree in the sense that we take advantage of common topology by constructing a multiway tree where the descendants of a node share a common substructure. We give algorithms to construct a g-trie, to list all stored subgraphs, and to find occurrences on another graph of the subgraphs stored in the g-trie. We evaluate the implementation of this structure and its associated algorithms on a set of representative benchmark biological networks in order to find network motifs. To assess the efficiency of our algorithms we compare their performance with other known network motif algorithms also implemented in the same common platform. Our results show that indeed, g-tries are a feasible, adequate and very efficient data structure for network motifs discovery, clearly outperforming previous algorithms and data structures. © 2010 ACM.
Subject: Algoritmos, Ciência de computadores
Algorithms, Computer science
Call Number: 48989
URI: http://hdl.handle.net/10216/101828
Source: Proceedings of the ACM Symposium on Applied Computing
Document Type: Artigo em Livro de Atas de Conferência Internacional
Rights: restrictedAccess
Appears in Collections:FCUP - Artigo em Livro de Atas de Conferência Internacional

Files in This Item:
File Description SizeFormat 
48989.pdfArtigo415.11 kBAdobe PDF    Request a copy


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.