Conflict-Sensitive Scheduling: Identifying Temporal and Spatial Constraints for Dynamic PPI Networks

Abstract

An important issue in protein-protein interaction network studies is the identification of interaction dynamics. Two factors contribute to the dynamics. One, not all proteins may be expressed in a given cell, and two, competition may exist among multiple proteins for a particular protein domain. Taking into account these two factors, we propose a method for building scheduling of interactions based on an extended notion of mutually exclusive interactions (interactions having the same target). By integrating data from different sources on the HeLa cancer cells and Homo sapiens (human) cells, we find a number of conflicting interaction pairs in post- translational modifications and in phosphorylation, which we use as spatial constraints. We further extend the spatial constraints by exploring non-conflicting upstream interactions (which we call conflict-free upstream cascades) to build an extended conflict graph. By integrating coloring-based clus- tering of the extended-conflict graph and activation patterns generated by soft clustering of a proteomic time profile data, we calculate the maximum likelihood conflict-sensitive scheduling using maximum bipartite matching. We use the scheduling results to infer a hypergraph of protein-protein interactions. The hyperedges of the hypergraph correspond to dynamic network modules. Those hyperedges can be used to predict protein complexes.

Team members

Materials

1. Significance of MEIs(Mutual exclusibe interactions): 8 Tables

2. Scheduling table

3. Condition set

4. Training model (the first two columns are PPIs)

5. Test data (the first two columns are PPIs)

6. Representatives

7. Prediction