Querying Graphs in Protein-Protein Interactions Networks using Feedback Vertex Set - Archive ouverte HAL Accéder directement au contenu
Article Dans Une Revue IEEE/ACM Transactions on Computational Biology and Bioinformatics Année : 2010

Querying Graphs in Protein-Protein Interactions Networks using Feedback Vertex Set

Résumé

Recent techniques increase rapidly the amount of our knowledge on interactions between proteins. The interpretation of these new information depends on our ability to retrieve known sub-structures in the data, the Protein-Protein Interactions (PPI) networks. In an algorithmic point of view, it is an hard task since it often leads to NP-hard problems. To overcome this difficulty, many authors have provided tools for querying patterns with a restricted topology, i.e. paths or trees in PPI networks. Such restriction leads to the development of fixed parameter tractable (FPT) algorithms, which can be practicable for restricted sizes of queries. Unfortunately, GRAPH HOMOMORPHISM is a W[1]-hard problem, and hence, no FPT algorithm can be found when patterns are in the shape of general graphs. However, Dost et al. [2] gave an algorithm (which is not implemented) to query graphs with a bounded treewidth in PPI networks (the treewidth of the query being involved in the time complexity). In this paper, we propose another algorithm for querying pattern in the shape of graphs, also based on dynamic programming and the color-coding technique. To transform graphs queries into trees without loss of informations, we use feedback vertex set coupled to a node duplication mecanism. Hence, our algorithm is FPT for querying graphs with a bounded size of their feedback vertex set. It gives an alternative to the treewidth parameter, which can be better or worst for a given query. We provide a python implementation which allows us to validate our implementation on real data. Especially, we retrieve some human queries in the shape of graphs into the fly PPI network.
Fichier principal
Vignette du fichier
hal.pdf (1.5 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00619763 , version 1 (06-10-2011)

Identifiants

  • HAL Id : hal-00619763 , version 1

Citer

Guillaume Blin, Florian Sikora, Stéphane Vialette. Querying Graphs in Protein-Protein Interactions Networks using Feedback Vertex Set. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2010, 7 (4), pp.628-635. ⟨hal-00619763⟩
158 Consultations
423 Téléchargements

Partager

Gmail Facebook X LinkedIn More