Graph-theoretic constraints on vesicle traffic networks

Eukaryotic cells use small membrane-enclosed vesicles to transport molecular cargo between intracellular compartments. Interactions between molecules on vesicles and compartments determine the source and target compartment of each vesicle type. The set of compartment and vesicle types in a cell define the nodes and edges of a transport graph known as the vesicle traffic network. The transmembrane SNARE proteins that regulate vesicle fusion to target compartments travel in cycles through the transport graph, but the paths they follow must be tightly regulated to avoid aberrant vesicle fusion. Here we use graph-theoretic ideas to understand how such molecular constraints place constraints on the structure of the transport graph. We identify edge connectivity (the minimum number of edges that must be removed to disconnect a graph) as a key determinant that separates allowed and disallowed types of transport graphs. As we increase the flexibility of molecular regulation, the required edge connectivity decreases, so more types of vesicle transport graphs are allowed. These results can be used to aid the discovery of new modes of molecular regulation and new vesicle traffic pathways.