Torque: Topology-Free Querying of Protein Interaction Networks
Title | Torque: Topology-Free Querying of Protein Interaction Networks |
Publication Type | Journal Article |
Year of Publication | 2010 |
Authors | Bruckner, S., Hüffner F., Karp R. M., Shamir R., & Sharan R. |
Published in | Journal of Computational Biology |
Volume | 17 |
Issue | 3 |
Page(s) | 237-252 |
Other Numbers | 3250 |
Abstract | In the network querying problem, one is given a protein complexor pathway of species A and a protein{protein interaction networkof species B; the goal is to identify subnetworks of B that are similarto the query. Existing approaches mostly depend on knowledge of theinteraction 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 matchingset of proteins that are sequence-similar to the query proteins and spana connected region of the network, while allowing both insertions anddeletions. The algorithm uses alternatively dynamic programming andinteger linear programming for the search task. We test Torque withqueries from yeast,y, and human, where we compare it to the QNettopology-based approach, and with queries from less studied species,where only topology-free algorithms apply. Torque detects many morematches than QNet, while in both cases giving results that are highlyfunctionally coherent. |
Bibliographic Notes | Journal of Computational Biology, Vol. 17, Issue 3, pp. 237-252 |
Abbreviated Authors | S. Bruckner, F. Hüffner, R. M. Karp, R. Shamir, and R. Sharan |
ICSI Research Group | Algorithms |
ICSI Publication Type | Article in journal or magazine |