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.


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.



Slides of the presentation at AB'07 may be put up here later ...

BibTeX Entry

	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