Accurate and Scalable Techniques for the Complex/Pathway Membership Problem in Protein Networks

[摘要] A protein network shows physical interactions as well as functional associations. An importantusage of such networks is to discover unknown members of partially known complexes andpathways. A number of methods exist for such analyses, and they can be divided into two maincategories based on their treatment of highly connected proteins. In this paper, we show thatmethods that are not affected by the degree (number of linkages) of a protein give more accuratepredictions for certain complexes and pathways. We propose a network flow-based techniqueto compute the association probability of a pair of proteins. We extend the proposed techniqueusing hierarchical clustering in order to scale well with the size of proteome. We also show thattop-k queries are not suitable for a large number of cases, and threshold queries are more meaningfulin these cases. Network flow technique with clustering is able to optimize meaningfulthreshold queries and answer them with high efficiency compared to a similar method that usesMonte Carlo simulation.

[学科分类] 生物技术