Pathway Analysis with Signaling Hypergraphs

doi:10.1109/TCBB.2015.2459681

Pathway Analysis with Signaling Hypergraphs

2017-09-01

17

OA

AI

DOI：10.1109/TCBB.2015.2459681

Original

Save

View PDF

Abstract

En 中文

Signaling pathways play an important role in the cell's response to its environment. Signaling pathways are often represented as directed graphs, which are not adequate for modeling reactions such as complex assembly and dissociation, combinatorial regulation, and protein activation/inactivation. More accurate representations such as directed hypergraphs remain underutilized. In this paper, we present an extension of a directed hypergraph that we call a signaling hypergraph. We formulate a problem that asks what proteins and interactions must be involved in order to stimulate a specific response downstream of a signaling pathway. We relate this problem to computing the shortest acyclic B-hyperpath in a signaling hypergraph-an NP-hard problem-and present a mixed integer linear program to solve it. We demonstrate that the shortest hyperpaths computed in signaling hypergraphs are far more informative than shortest paths, Steiner trees, and subnetworks containing many short paths found in corresponding graph representations. Our results illustrate the potential of signaling hypergraphs as an improved representation of signaling pathways and motivate the development of novel hypergraph algorithms.

Keywords:

Hypergraphs

integer linear programming

systems biology

signaling pathways

Wnt signaling

Pathway Analysis with Signaling Hypergraphs

Abstract

AI Summary

Journal

Organization