2009 | OriginalPaper | Chapter
Topology-Free Querying of Protein Interaction Networks
Authors : Sharon Bruckner, Falk Hüffner, Richard M. Karp, Ron Shamir, Roded Sharan
Published in: Research in Computational Molecular Biology
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In the network querying problem, one is given a protein complex or pathway of species
A
and a protein–protein interaction network of species
B
; the goal is to identify subnetworks of
B
that are similar to the query. Existing approaches mostly depend on knowledge of the interaction topology of the query in the network of species
A
; however, in practice, this topology is often not known. To combat this problem, we develop a topology-free querying algorithm, which we call
Torque
. Given a query, represented as a set of proteins,
Torque
seeks a matching set of proteins that are sequence-similar to the query proteins and span a connected region of the network, while allowing both insertions and deletions. The algorithm uses alternatively dynamic programming and integer linear programming for the search task. We test
Torque
with queries from yeast, fly, and human, where we compare it to the QNet topology-based approach, and with queries from less studied species, where only topology-free algorithms apply.
Torque
detects many more matches than QNet, while in both cases giving results that are highly functionally coherent.