PDF

Description

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 finding 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.

Details

Files

Statistics

from
to
Export
Download Full History