Permutation-Invariant Subgraph Discovery
This provides a tool for computational biologists to identify novel prognostic signatures in systems biology, though it is incremental as it builds on existing graph matching tasks.
The authors tackled the problem of detecting structural changes between two graphs, such as gene regulatory networks from diseased and normal tissues, by introducing the Permutation and Structured Perturbation Inference (PSPI) formulation and proposing the STEPD algorithm, which accurately infers structured perturbations in a case study on comparative gene regulatory networks.
We introduce Permutation and Structured Perturbation Inference (PSPI), a new problem formulation that abstracts many graph matching tasks that arise in systems biology. PSPI can be viewed as a robust formulation of the permutation inference or graph matching, where the objective is to find a permutation between two graphs under the assumption that a set of edges may have undergone a perturbation due to an underlying cause. For example, suppose there are two gene regulatory networks X and Y from a diseased and normal tissue respectively. Then, the PSPI problem can be used to detect if there has been a structural change between the two networks which can serve as a signature of the disease. Besides the new problem formulation, we propose an ADMM algorithm (STEPD) to solve a relaxed version of the PSPI problem. An extensive case study on comparative gene regulatory networks (GRNs) is used to demonstrate that STEPD is able to accurately infer structured perturbations and thus provides a tool for computational biologists to identify novel prognostic signatures. A spectral analysis confirms that STEPD can recover small clique-like perturbations making it a useful tool for detecting permutation-invariant changes in graphs.