Premium
A divide‐and‐conquer approach to determine the Pareto frontier for optimization of protein engineering experiments
Author(s) -
He Lu,
Friedman Alan M.,
BaileyKellogg Chris
Publication year - 2012
Publication title -
proteins: structure, function, and bioinformatics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.699
H-Index - 191
eISSN - 1097-0134
pISSN - 0887-3585
DOI - 10.1002/prot.23237
Subject(s) - pareto principle , integer programming , divide and conquer algorithms , mathematical optimization , stability (learning theory) , computer science , integer (computer science) , multi objective optimization , linear programming , benchmark (surveying) , mathematics , algorithm , machine learning , geodesy , programming language , geography
In developing improved protein variants by site‐directed mutagenesis or recombination, there are often competing objectives that must be considered in designing an experiment (selecting mutations or breakpoints): stability versus novelty, affinity versus specificity, activity versus immunogenicity, and so forth. Pareto optimal experimental designs make the best trade‐offs between competing objectives. Such designs are not “dominated”; that is, no other design is better than a Pareto optimal design for one objective without being worse for another objective. Our goal is to produce all the Pareto optimal designs (the Pareto frontier), to characterize the trade‐offs and suggest designs most worth considering, but to avoid explicitly considering the large number of dominated designs. To do so, we develop a divide‐and‐conquer algorithm, Protein Engineering Pareto FRontier ( PEPFR ), that hierarchically subdivides the objective space, using appropriate dynamic programming or integer programming methods to optimize designs in different regions. This divide‐and‐conquer approach is efficient in that the number of divisions (and thus calls to the optimizer) is directly proportional to the number of Pareto optimal designs. We demonstrate PEPFR with three protein engineering case studies: site‐directed recombination for stability and diversity via dynamic programming, site‐directed mutagenesis of interacting proteins for affinity and specificity via integer programming, and site‐directed mutagenesis of a therapeutic protein for activity and immunogenicity via integer programming. We show that PEPFR is able to effectively produce all the Pareto optimal designs, discovering many more designs than previous methods. The characterization of the Pareto frontier provides additional insights into the local stability of design choices as well as global trends leading to trade‐offs between competing criteria. Proteins 2011. © 2012 Wiley Periodicals, Inc.