Analyzing Pathways using SAT-based Approaches
Ashish Tiwari, Carolyn Talcott, Merrill Knapp, Patrick Lincoln, and Keith Laderoute
Presented at
AB 2007, Austria, July 2-4, 2007.
Abstract
A network of reactions is a commonly used paradigm
for representing knowledge about a biological process.
How does one understand such generic networks and answer queries using them?
In this paper, we present a novel approach based on translation
of generic reaction networks to Boolean {\em weighted MaxSAT}.
The Boolean weighted MaxSAT instance is generated by encoding
the equilibrium configurations of a reaction network by
weighted boolean clauses.
The important feature
of this translation is that it uses reactions, rather than
the species, as the boolean variables. Existing
weighted MaxSAT solvers are used to solve the generated
instances and find equilibrium configurations.
This method of analyzing reaction networks is generic, flexible
and scales to large models
of reaction networks. We present a few case studies to validate
our claims.
This work was supported in part by Public Health Service
grant GM068146-03 from the National Institute of General Medical Sciences
and by the National Science Foundation under grants IIS-0513857 and
CCR-0326540.
pdf.
Slides
Slides of the presentation at AB'07 may be put up here later ...
BibTeX Entry
@inproceedings{TTKLL07:AB,
author = "A.~Tiwari and C. Talcott and M. Knapp and P. Lincoln and K. Laderoute",
title = "Analyzing Pathways using SAT-based Approaches",
booktitle = "Proc. 2nd Intl. Conf. on Algebraic Biology, AB 2007",
pages = "155--169",
YEAR = 2007,
publisher = "Springer",
series = "LNCS",
volume = "4545",
}
Return to the Ashish's home page
Return to the Computer Science Laboratory home page