关键词：酶途径；最优路径；合成生物学
摘 要：We examine two optimal path problems that arise in the context of ranking enzymatic pathways to synthesize a target compound. First, we present a survey of exact and approximation algorithms for the multiobjective shortest path (MOSP) problem. Second, we formalize the problem of fi nding stoichiometrically minimal source pathways (SMSP), which seeks to find paths that use a non-dominated amount of native chemicals to reach a target compound. We show that the SMSP problem is NP-complete and present two approaches to solve it based on model checking. For both problems, we provide an experimental evaluation and discussion of results.