Send to

Choose Destination
PLoS One. 2017 Jul 6;12(7):e0180692. doi: 10.1371/journal.pone.0180692. eCollection 2017.

Discovering vesicle traffic network constraints by model checking.

Author information

School of Computer Science and Engineering, Vellore Institute of Technology, Vellore, India.
Department of Computer Science and Automation, Indian Institute of Science, Bengaluru, India.
Chennai Mathematical Institute, Chennai, India.
Simons Centre for the Study of Living Machines, National Centre for Biological Sciences, Tata Institute of Fundamental Research, Bengaluru, India.


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.

[Indexed for MEDLINE]
Free PMC Article

Supplemental Content

Full text links

Icon for Public Library of Science Icon for PubMed Central
Loading ...
Support Center