Connecting the Dots in Protein Interaction Networks

Proteins can be thought of as the machines inside cells, participating in nearly all biological processes. By physically binding to and interacting with one another, proteins form pathways dedicated to specific functions and vast networks. Mapping these pathways is critical for understanding how their disruption causes disease, but biological experiments provide only limited, noisy views of pathway members. We represent protein interaction networks as a graph and present combinatorial optimization techniques – one based on Steiner trees and the other on orienting undirected edges – that connect relevant proteins and complete partially observed pathways. The predictions can provide insights into human diseases including influenza infection and cancer.