# Shortest Paths with Pairwise-Distinct Edge Labels: Finding Biochemical Pathways in Metabolic Networks

Preprint · Sandor Fekete, Tom Kamphans, Michael Stelzer

- Archive id: arxiv:1012.5024
- Published: 2010-12-22
- arXiv: https://arxiv.org/abs/1012.5024
- Citations: 3
- Source URL: https://arxiv.org/abs/1012.5024
- PDF: https://arxiv.org/pdf/1012.5024
- Provenance: arxiv

## Abstract

A problem studied in Systems Biology is how to find shortest paths in metabolic networks. Unfortunately, simple (i.e., graph theoretic) shortest paths do not properly reflect biochemical facts. An approach to overcome this issue is to use edge labels and search for paths with distinct labels. In this paper, we show that such biologically feasible shortest paths are hard to compute. Moreover, we present solutions to find such paths in networks in reasonable time.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Algorithms & Complexity Breakthroughs](https://space-kitty.com/topics/algorithms-complexity)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.