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

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