## Abstract

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 http://mmunin.cs.arizona.edu.

Original language | English (US) |
---|---|

Title of host publication | Research in Computational Molecular Biology - 27th Annual International Conference, RECOMB 2023, Proceedings |

Editors | Haixu Tang |

Publisher | Springer Science and Business Media Deutschland GmbH |

Pages | 155-173 |

Number of pages | 19 |

ISBN (Print) | 9783031291180 |

DOIs | |

State | Published - 2023 |

Event | 27th International Conference on Research in Computational Molecular Biology, RECOMB 2023 - Istanbul, Turkey Duration: Apr 16 2023 → Apr 19 2023 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 13976 LNBI |

### Conference

Conference | 27th International Conference on Research in Computational Molecular Biology, RECOMB 2023 |
---|---|

Country/Territory | Turkey |

City | Istanbul |

Period | 4/16/23 → 4/19/23 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- General Computer Science