Computing Shortest Hyperpaths for Pathway Inference in Cellular Reaction Networks

Spencer Krieger, John Kececioglu

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Signaling and metabolic pathways, which consist of a series of reactions producing target molecules from source compounds, are cornerstones of cellular biology. The cellular reaction networks containing such pathways can be precisely modeled by directed hypergraphs, where each reaction corresponds to a hyperedge, directed from its set of reactants to its set of products. Given such a network represented by a directed hypergraph, inferring the most likely set of reactions that produce a given target from a given set of sources corresponds to finding a shortest hyperpath, which is NP-complete. The best methods currently available for shortest hyperpaths either offer no guarantee of optimality, or exclude hyperpaths containing cycles even though cycles are abundant in real biological pathways. We derive a novel graph-theoretic characterization of hyperpaths, leveraged in a new formulation of the general shortest hyperpath problem as an integer linear program that for the first time handles hyperpaths containing cycles, and present a novel cutting-plane algorithm that can solve this integer program to optimality in practice. This represents a major advance over the best prior exact algorithm, which was limited to acyclic hyperpaths (and hence fails to find a solution for the many biological instances where all hyperpaths are in fact cyclic). In comprehensive experiments over thousands of instances from the standard NCI-PID and Reactome databases, we demonstrate that our cutting-plane algorithm quickly finds an optimal hyperpath, with a median running-time of under ten seconds and a maximum time of around thirty minutes, even on large instances with many thousands of reactions. Source code implementing our cutting-plane algorithm for shortest hyperpaths in a new tool called Mmunin is available free for research use at

Original languageEnglish (US)
Title of host publicationResearch in Computational Molecular Biology - 27th Annual International Conference, RECOMB 2023, Proceedings
EditorsHaixu Tang
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages19
ISBN (Print)9783031291180
StatePublished - 2023
Event27th International Conference on Research in Computational Molecular Biology, RECOMB 2023 - Istanbul, Turkey
Duration: Apr 16 2023Apr 19 2023

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13976 LNBI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference27th International Conference on Research in Computational Molecular Biology, RECOMB 2023

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Computing Shortest Hyperpaths for Pathway Inference in Cellular Reaction Networks'. Together they form a unique fingerprint.

Cite this