1 Search Results for "Krieger, Spencer"

Document
DOI: 10.4230/LIPIcs.WABI.2021.20
Fast Approximate Shortest Hyperpaths for Inferring Pathways in Cell Signaling Hypergraphs

Authors: Spencer Krieger and John Kececioglu

Published in: LIPIcs, Volume 201, 21st International Workshop on Algorithms in Bioinformatics (WABI 2021)

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.
Cite as

Spencer Krieger and John Kececioglu. Fast Approximate Shortest Hyperpaths for Inferring Pathways in Cell Signaling Hypergraphs. In 21st International Workshop on Algorithms in Bioinformatics (WABI 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 201, pp. 20:1-20:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2021.20},
  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}
}
  • Refine by Author
  • 1 Kececioglu, John
  • 1 Krieger, Spencer

  • Refine by Classification
  • 1 Applied computing → Bioinformatics
  • 1 Applied computing → Systems biology
  • 1 Mathematics of computing → Hypergraphs
  • 1 Theory of computation → Shortest paths

  • Refine by Keyword
  • 1 Systems biology
  • 1 cell signaling networks
  • 1 directed hypergraphs
  • 1 efficient heuristics
  • 1 hyperpath enumeration
  • Show More...

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact