Hypergraph model of multi-residue interactions in proteins: sequentially-constrained partitioning algorithms for optimization of site-directed protein recombination.
Relationships among amino acids determine stability and function and are also constrained by evolutionary history. We develop a probabilistic hypergraph model of residue relationships that generalizes traditional pairwise contact potentials to account for the statistics of multi-residue interactions. Using this model, we detected non-random associations in protein families and in the protein database. We also use this model in optimizing site-directed recombination experiments to preserve significant interactions and thereby increase the frequency of generating useful recombinants. We formulate the optimization as a sequentially-constrained hypergraph partitioning problem; the quality of recombinant libraries with respect to a set of breakpoints is characterized by the total perturbation to edge weights. We prove this problem to be NP-hard in general, but develop exact and heuristic polynomial-time algorithms for a number of important cases. Application to the beta-lactamase family demonstrates the utility of our algorithms in planning site-directed recombination.
Ye
Xiaoduan
X
Department of Computer Science, Dartmouth College, Hanover, NH 03755, USA.
Friedman
Alan M
AM
Bailey-Kellogg
Chris
C
D000465:Algorithms; D001665:Binding Sites; D019295:Computational Biology / Q000379:methods; D030562:Databases, Protein; D008958:Models, Molecular; D015394:Molecular Structure; D011487:Protein Conformation; D015202:Protein Engineering; D011995:Recombination, Genetic; D016415:Sequence Alignment; D012984:Software; D001618:beta-Lactamases / Q000737:chemistry* / Q000378:metabolism*
D001618:beta-Lactamases