  Motivation: Protein interactions are fundamental building blocks of
biochemical reaction systems underlying cellular functions. The complexity and
functionality of such systems emerge not from the protein interactions
themselves but from the dependencies between these interactions. Therefore, a
comprehensive approach for integrating and using information about such
dependencies is required. Results: We present an approach for endowing protein
networks with interaction dependencies using propositional logic, thereby
obtaining protein hypernetworks. First we demonstrate how this framework
straightforwardly improves the prediction of protein complexes. Next we show
that modeling protein perturbations in hypernetworks, rather than in networks,
allows to better infer the functional necessity of proteins for yeast.
Furthermore, hypernetworks improve the prediction of synthetic lethal
interactions in yeast, indicating their capability to capture high-order
functional relations between proteins. Conclusion: Protein hypernetworks are a
consistent formal framework for modeling dependencies between protein
interactions within protein networks. First applications of protein
hypernetworks on the yeast interactome indicate their value for inferring
functional features of complex biochemical systems.
