Topology-Free Querying of Protein Interaction Networks
Topology-Free Querying of Protein Interaction Networks
复制标题
DOI：
10.1089/cmb.2009.0170
复制
发表时间：
2010-03-01
影响因子：
1.7
通讯作者：
Sharan, Roded
中科院分区：
文献类型：
--
作者：
Bruckner, Sharon;Hueffner, Falk;Sharan, Roded
在网络查询问题中，给定物种A的蛋白质复合体或途径和物种B的蛋白质-蛋白质相互作用网络，目标是识别在序列、拓扑或两者方面与查询相似的B的子网络。现有的方法大多依赖于物种A网络中查询的交互拓扑的知识；然而，在实践中，这种拓扑通常是未知的。为了解决这个问题，我们开发了一种无拓扑查询算法，我们称之为TORQUE。给定一个被表示为一组蛋白质的查询，Torke寻找一组与查询蛋白质序列相似的匹配蛋白质集，这些蛋白质跨越网络的一个连接区域，同时允许插入和删除。该算法交替使用动态规划和整数线性规划来完成搜索任务。我们用来自酵母、苍蝇和人类的查询来测试TORQUE，在这些查询中，我们将其与QNET基于拓扑的方法进行比较，并使用研究较少的物种的查询，在这些物种中，只应用无拓扑的算法。TORQUE检测的匹配项比QNET多得多，同时提供的结果在功能上高度一致。
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 in terms of sequence, topology, or both. 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 address 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 giving results that are highly functionally coherent.