TitleDiscovering vesicle traffic network constraints by model checking.
Publication TypeJournal Article
Year of Publication2017
AuthorsShukla A, Bhattacharyya A, Kuppusamy L, Srivas M, Thattai M
JournalPLoS One
Volume12
Issue7
Paginatione0180692
Date Published2017
ISSN1932-6203
Abstract

A eukaryotic cell contains multiple membrane-bound compartments. Transport vesicles move cargo between these compartments, just as trucks move cargo between warehouses. These processes are regulated by specific molecular interactions, as summarized in the Rothman-Schekman-Sudhof model of vesicle traffic. The whole structure can be represented as a transport graph: each organelle is a node, and each vesicle route is a directed edge. What constraints must such a graph satisfy, if it is to represent a biologically realizable vesicle traffic network? Graph connectedness is an informative feature: 2-connectedness is necessary and sufficient for mass balance, but stronger conditions are required to ensure correct molecular specificity. Here we use Boolean satisfiability (SAT) and model checking as a framework to discover and verify graph constraints. The poor scalability of SAT model checkers often prevents their broad application. By exploiting the special structure of the problem, we scale our model checker to vesicle traffic systems with reasonably large numbers of molecules and compartments. This allows us to test a range of hypotheses about graph connectivity, which can later be proved in full generality by other methods.

DOI10.1371/journal.pone.0180692
Alternate JournalPLoS ONE
PubMed ID28683137
PubMed Central IDPMC5500374
Grant List / / Wellcome Trust / United Kingdom