Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2017 Sep-Oct;14(5):1042-1055.
doi: 10.1109/TCBB.2015.2459681.

Pathway Analysis with Signaling Hypergraphs

Pathway Analysis with Signaling Hypergraphs

Anna Ritz et al. IEEE/ACM Trans Comput Biol Bioinform. 2017 Sep-Oct.

Abstract

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.

PubMed Disclaimer

Figures

Fig. 1
Fig. 1
Signaling hypergraph concepts and notation. Dark gray circles represent nodes, and light gray circles represent hypernodes (subsets of nodes). Regulators are denoted by a dashed line for visualization purposes. (a) A signaling hypergraph H=(V,V,E). (b) Hyperedge e2 establishes that hypernodes u3 and u4 are B-connected to s while hyperedge e3 performs this role for hypernodes u5, and u6. Hypernodes u1 and u2 are not B-connected to s. (c) Hypernode u6 is also B-connected to s because of hyperedge e4. (d) The set BH(s) of hypernodes that are B-connected to s and the hyperedges that establish these B-connections. (e) An s-t B-hyperpath ∏ (s, t) containing six hyperedges. Note that no hyperedge may be removed from ∏(s, t) and still maintain that t is B-connected to s using only the hyperedges in ∏(s, t). (f) An s-t B-hyperpath ∏(s, t) containing three hyperedges.
Fig. 2
Fig. 2
An s-t B-hyperpath with a simple cycle (u6, e5, u7, e6, u6).
Fig. 3
Fig. 3
k-hypergraph construction from an instance of Minimum k-Set Cover with seven elements A = {a1, a2, …, a7}, four subsets Q = {{a1, a2}, {a3}, {a3, a4, a5}, {a5, a6, a7}}, and k = 3.
Fig. 4
Fig. 4
A sub-hypergraph H(α) that satisfies constraints (2)–(5) where t is not B-connected to s. Hypernode t is in the solution, and each hypernode in the solution (u8, u9, u10, t) has a hyperedge in its backwards star that is also in the solution (e8, e7, e9, e9).
Fig. 5
Fig. 5
Hypergraph Conversions to Graph Representations. A single hyperedge (a) is converted into a graph with complexes (b) and a graph (c) representations. Note that if the same node appears on in the tail and the head, some edges will be collapsed.
Fig. 6
Fig. 6
Small Wnt Pathway Solutions to ubiquitinated β-catenin, denoted by a post-translational modification with a ‘U’.
Fig. 7
Fig. 7
Small Wnt Pathway Solutions to nuclear β-catenin, denoted by a compartment marked ‘n’ for nucleus.
Fig. 8
Fig. 8
Large Wnt Pathway solutions. (a) The shortest acyclic B-hyperpath in the signaling hypergraph, and (b) the same B-hypergraph organized by cellular compartment (hyperedges from s not shown). (c) The Steiner tree in the graph with complexes connecting s to TCF1 and LEF1 terminals. The Steiner tree was comprised of two of the five shortest paths in the graph with complexes representation (Table 2).
Fig. 9
Fig. 9
Precision-recall plots for edge recovery of the shortest acyclic B-hyperpath using the k-shortest paths from GC and G from the large Wnt signaling pathway. Labels on the lines represent k, the number of shortest paths used to achieve that exact precision-recall value.
Fig. 10
Fig. 10
Two B-hyperpaths computed in the full NCI-PID signaling pathway. The B-hyperpath from s1 to t1 is the optimal result for “New Sources to Known Targets”, and the B-hyperpath from s2 to t2 is the optimal result for “Known Sources to New Targets.”

Similar articles

Cited by

References

    1. Heath LS, Sioson AA. Semantics of multimodal network models. IEEE/ACM Transactions on Computational Biology and Bioinformatics. 2009;6(2):271–280. - PubMed
    1. Klamt S, Haus U-U, Theis F. Hypergraphs and cellular networks. PLoS Computational Biology. 2009;5(5):e1000385. - PMC - PubMed
    1. Berge C. Hypergraphs, Volume 45: Combinatorics of Finite Sets. 1st. North Holland; Aug, 1989.
    1. Ritz A, Tegge AN, Kim H, Poirel CL, Murali T. Signaling hypergraphs. Trends in Biotechnology. 2014;32(7):356–362. [Online]. Available: http://dx.doi.org/10.1016/j.tibtech.2014.04.007. - DOI - PMC - PubMed
    1. Ritz A, Murali TM. Proceedings of the 5th ACM Conference on Bioinformatics, Computational Biology, and Health Informatics. New York, NY, USA: ACM; 2014. Pathway analysis with signaling hypergraphs; pp. 249–258. (ser BCB ’14). [Online]. Available: http://doi.acm.org/10.1145/2649387.2649450. - DOI

Publication types