Energy Minimization of Discrete Protein Titration State Models Using Graph Theory

There
are several applications in computational biophysics that
require the optimization of discrete interacting states, for example,
amino acid titration states, ligand oxidation states, or discrete
rotamer angles. Such optimization can be very time-consuming as it
scales exponentially in the number of sites to be optimized. In this
paper, we describe a new polynomial time algorithm for optimization
of discrete states in macromolecular systems. This algorithm was adapted
from image processing and uses techniques from discrete mathematics
and graph theory to restate the optimization problem in terms of “maximum
flow–minimum cut” graph analysis. The interaction energy
graph, a graph in which vertices (amino acids) and edges (interactions)
are weighted with their respective energies, is transformed into a
flow network in which the value of the minimum cut in the network
equals the minimum free energy of the protein and the cut itself encodes
the state that achieves the minimum free energy. Because of its deterministic
nature and polynomial time performance, this algorithm has the potential
to allow for the ionization state of larger proteins to be discovered.