License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.WABI.2021.20
URN: urn:nbn:de:0030-drops-143733
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14373/
Go to the corresponding LIPIcs Volume Portal

Krieger, Spencer ; Kececioglu, John

Fast Approximate Shortest Hyperpaths for Inferring Pathways in Cell Signaling Hypergraphs

pdf-format:
LIPIcs-WABI-2021-20.pdf (1 MB)

Abstract

Cell signaling pathways, which are a series of reactions that start at receptors and end at transcription factors, are basic to systems biology. Properly modeling the reactions in such pathways requires directed hypergraphs, where an edge is now directed between two sets of vertices. Inferring a pathway by the most parsimonious series of reactions then corresponds to finding a shortest hyperpath in a directed hypergraph, which is NP-complete. The state of the art for shortest hyperpaths in cell-signaling hypergraphs solves a mixed-integer linear program to find an optimal hyperpath that is restricted to be acyclic, and offers no efficiency guarantees.
We present for the first time a heuristic for general shortest hyperpaths that properly handles cycles, and is guaranteed to be efficient. Its accuracy is demonstrated through exhaustive experiments on all instances from the standard NCI-PID and Reactome pathway databases, which show the heuristic finds a hyperpath that matches the state-of-the-art mixed-integer linear program on over 99% of all instances that are acyclic. On instances where only cyclic hyperpaths exist, the heuristic surpasses the state-of-the-art, which finds no solution; on every such cyclic instance, enumerating all possible hyperpaths shows that the solution found by the heuristic is in fact optimal.

BibTeX - Entry

@InProceedings{krieger_et_al:LIPIcs.WABI.2021.20,
  author =	{Krieger, Spencer and Kececioglu, John},
  title =	{{Fast Approximate Shortest Hyperpaths for Inferring Pathways in Cell Signaling Hypergraphs}},
  booktitle =	{21st International Workshop on Algorithms in Bioinformatics (WABI 2021)},
  pages =	{20:1--20:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-200-6},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{201},
  editor =	{Carbone, Alessandra and El-Kebir, Mohammed},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14373},
  URN =		{urn:nbn:de:0030-drops-143733},
  doi =		{10.4230/LIPIcs.WABI.2021.20},
  annote =	{Keywords: Systems biology, cell signaling networks, reaction pathways, directed hypergraphs, shortest hyperpaths, efficient heuristics, hyperpath enumeration}
}

Keywords: Systems biology, cell signaling networks, reaction pathways, directed hypergraphs, shortest hyperpaths, efficient heuristics, hyperpath enumeration
Collection: 21st International Workshop on Algorithms in Bioinformatics (WABI 2021)
Issue Date: 2021
Date of publication: 22.07.2021
Supplementary Material: Source code for the shortest hyperpath heuristic and hyperpath enumeration is available at http://hyperpaths.cs.arizona.edu.

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI