Matthew Fong

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2015-126

May 15, 2015

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2015/EECS-2015-126.pdf

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.

Advisors: Sanjit A. Seshia

---

BibTeX citation:

@mastersthesis{Fong:EECS-2015-126,
    Author= {Fong, Matthew},
    Title= {Two Optimal Path Problems in Synthetic Biology},
    School= {EECS Department, University of California, Berkeley},
    Year= {2015},
    Month= {May},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2015/EECS-2015-126.html},
    Number= {UCB/EECS-2015-126},
    Abstract= {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.},
}

EndNote citation:

%0 Thesis
%A Fong, Matthew 
%T Two Optimal Path Problems in Synthetic Biology
%I EECS Department, University of California, Berkeley
%D 2015
%8 May 15
%@ UCB/EECS-2015-126
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2015/EECS-2015-126.html
%F Fong:EECS-2015-126