Conclusion
Recent advances in experimental techniques resulted in the accumulation of a vast amount of protein interaction information, which is routinely represented by protein interaction networks. Therefore it is not surprising that increasingly more complex graph-theoretical tools are deployed to analyze protein interaction graphs and extract biologically meaningful patterns.
In general, graphs are not required to have any type of regularity. This makes them a very flexible tool which is able to represent complex relationships. However, this often also makes them computationally hard to deal with, for many problems in graph theory are NP-complete. Frequently graph theoretical problems can be simplified if some restrictions are imposed on the graph. Various restrictions give rise to various graph families. Given a graph family, it is usually very useful to be able to represent it using some kind of a tree. Such tree representation exposes a hierarchical organization that a graph may have, allowing for a structured analysis of it.
In this work we proposed a tree representation for protein interaction graphs called Tree of Complexes representation. Nodes in the Tree of Complexes are functional groups and the tree satisfies the additional condition that functional groups that contain any fixed protein form a connected subgraph. In this way, our representation captures not only the overlap between functional groups but, potentially, also the manner in which proteins enter and leave their enclosing functional groups. We developed a method (together with the corresponding graph-theoretical theory) for efficient identification of such overlapping functional groups and construction of the corresponding Tree of Complexes. In particular, our method differs from other approaches in that it does not attempt to enumerate disjoint complexes but instead identifies and represents relations between overlapping functional groups. Even though the Tree of Complexes representation is not unique, the protein interaction networks that we analyzed admit very few alternative tree topologies. If we ask for a tree topology with a maximum number of leaves, as not to impose an artificial order between functional groups, the number of tree topologies is reduced even further. Thus, in the TNFα/NF-κB signalling pathway this results in a unique Tree of Complexes representation and in the pheromone signalling pathway in two very closely related possible Tree of Complexes representations. The nature of high-throughput protein interaction data does not directly imply that this data encodes temporal relations. We demonstrated that our method is frequently capable of discovering such temporal relations. Interestingly, temporal associations can also be implicated in the absence of actual interaction in the data. For example, in the case of the pheromone signaling pathway, our method correctly included KSS1 and FUS3 in the same functional group (treated here as temporal associations), despite the fact that there is no link between KSS1 and FUS3 in the input protein interaction network.
Obviously, there are limitations to deciphering such temporal relations. For example, we cannot provide temporal ordering between different tree branches. Furthermore, if a functional group is not a clique but is represented as a Boolean expression indicating various possibilities for such group, then one can not be sure if these variants are mutually exclusive or if they represent partial information capturing incomplete data. Even in the case when the functional unit forms a clique it is still possible that it contains interactions that are not simultaneous. For example, interactions between pairs (A, B), (B, C) and (C, A) are represent as a three-vertex clique with nodes A, B, C and thus cannot be distinguished from a trimer (A, B, C). Such coincidences are less likely for larger cliques.
Although our algorithm is not guaranteed to produce the Tree of Complexes representation for every possible protein interaction network, the algorithm will succeed for a broad family of graphs, which includes chordal graphs (and thus interval graphs) and cographs. Currently, our method can be applied to protein interaction networks that do not contain long (longer than four node) chordless cycles. As a consequence, it is more appropriate for analyzing dedicated subnetworks or modules than large protein interaction networks, which are expected to contain such long cycles. We distinguish between two different types of problematic networks for our method. First type includes networks for which imposing a temporal order that encompasses all functional groups in the network is meaningless. Second type includes networks for which such order is meaningful, but the assumption that the overlap between functional groups has a tree-like structure is not valid. We plan to extend our approach to deal with networks of the second type by utilizing graph-theoretical tools developed for other specialized graph families, such as arc-intersection graphs.
Another issue that requires further investigation is the presence of noise in high-throughput protein interaction networks and its effect on the Tree of Complexes representation. While our method deals to some extent with false negatives, through its edge addition procedure, the issue of false positives is not addressed. We plan to explore alternative graph modification procedures that will incorporate both false negative and false positive interactions.