Prize-collecting Steiner forest network analysis

We performed network enrichment using the Prize-collecting Steiner forest (PCSF) algorithm. PCSF creates subnetworks from sets of proteins and a background protein-protein interaction network by finding connections between proteins of interest. In PCSF, proteins of interest are given prizes, and all edges in the reference set of protein-protein interactions are given costs. The objective is to select a subnetwork from the larger background network that maximizes the prizes of the selected proteins and minimizes the costs of the selected edges. The subnetwork is a forest-structured graph F = (V_F, E_F) that optimizes the following function:

where p(v) is the positive prize on each protein vertex, c(e) is the positive cost on each edge, d(v) is the degree of each vertex, and κ is the number of trees (connected components) in the subnetwork. The parameters β, μ, and ω are used to control the desired properties of the subnetwork such as the size. Choices of prizes, costs, and parameters are explained below. We used the Omics Integrator [53] implementation of PCSF, which solves PCSF via a message passing algorithm [54].