title: A virtual pebble game to ensemble average graph rigidity.
abstract: BACKGROUND
  The body-bar Pebble Game (PG) algorithm is commonly used to calculate network rigidity properties in proteins and polymeric materials. To account for fluctuating interactions such as hydrogen bonds, an ensemble of constraint topologies are sampled, and average network properties are obtained by averaging PG characterizations. At a simpler level of sophistication, Maxwell constraint counting (MCC) provides a rigorous lower bound for the number of internal degrees of freedom (DOF) within a body-bar network, and it is commonly employed to test if a molecular structure is globally under-constrained or over-constrained. MCC is a mean field approximation (MFA) that ignores spatial fluctuations of distance constraints by replacing the actual molecular structure by an effective medium that has distance constraints globally distributed with perfect uniform density.
  
  
  RESULTS
  The Virtual Pebble Game (VPG) algorithm is a MFA that retains spatial inhomogeneity in the density of constraints on all length scales. Network fluctuations due to distance constraints that may be present or absent based on binary random dynamic variables are suppressed by replacing all possible constraint topology realizations with the probabilities that distance constraints are present. The VPG algorithm is isomorphic to the PG algorithm, where integers for counting "pebbles" placed on vertices or edges in the PG map to real numbers representing the probability to find a pebble. In the VPG, edges are assigned pebble capacities, and pebble movements become a continuous flow of probability within the network. Comparisons between the VPG and average PG results over a test set of proteins and disordered lattices demonstrate the VPG quantitatively estimates the ensemble average PG results well.
  
  
  CONCLUSIONS
  The VPG performs about 20% faster than one PG, and it provides a pragmatic alternative to averaging PG rigidity characteristics over an ensemble of constraint topologies. The utility of the VPG falls in between the most accurate but slowest method of ensemble averaging over hundreds to thousands of independent PG runs, and the fastest but least accurate MCC.
authors.affiliation: Department of Bioinformatics and Genomics, University of North Carolina at Charlotte, Charlotte, NC 28223 USA ; Current address: Facultad de Ingeniería, Universidad Autónoma de Chihuahua, Circuito No. 1, Campus Universitario 2, Chihuahua, Chih, CP 31125 Mexico.
authors.forename: Luis C
authors.initials: LC
authors.lastname: González
authors.affiliation: Department of Physics and Optical Science, University of North Carolina at Charlotte, Charlotte, NC 28223 USA ; Current address: Goldman Sachs, 200 West Street, New York, NY 10282 USA.
authors.forename: Hui
authors.initials: H
authors.lastname: Wang
authors.affiliation: Department of Bioinformatics and Genomics, University of North Carolina at Charlotte, Charlotte, NC 28223 USA ; Center for Biomedical Engineering and Sciences, University of North Carolina at Charlotte, 28223 Charlotte, NC USA.
authors.forename: Dennis R
authors.initials: DR
authors.lastname: Livesay
authors.affiliation: Department of Physics and Optical Science, University of North Carolina at Charlotte, Charlotte, NC 28223 USA ; Center for Biomedical Engineering and Sciences, University of North Carolina at Charlotte, 28223 Charlotte, NC USA.
authors.forename: Donald J
authors.initials: DJ
authors.lastname: Jacobs
keywords: Constraint counting; Constraint topologies; Effective medium; Graph rigidity; Mean field approximation; Pebble game; Probability flow; Protein flexibility; Protein stability