Algorithms for Selecting Breakpoint Locations to Optimize Diversity in Protein Engineering by Site-Directed Protein Recombination

Wei Zheng, Xiaoduan Ye, Alan M. Friedman, Chris Bailey-Kellogg*

6211 Sudikoff Laboratory, Hanover, NH 03755, USA. cbk@cs.dartmouth.edu

Proc LSS Comput Syst Bioinform Conf. August, 2007. Vol. 6, p. 31-40. Full-Text PDF

*To whom correspondence should be addressed.

Protein engineering by site-directed recombination seeks to develop proteins with new or improved function, by accumulating multiple mutations from a set of homologous parent proteins. A library of hybrid proteins is created by recombining the parent proteins at specified breakpoint locations; subsequent screening/selection identifies hybrids with desirable functional characteristics. In order to improve the frequency of generating novel hybrids, this paper develops the first approach to explicitly plan for diversity in site-directed recombination, including metrics for characterizing the diversity of a planned hybrid library and efficient algorithms for optimizing experiments accordingly. The goal is to choose breakpoint locations to sample sequence space as uniformly as possible (which we argue maximizes diversity), under the constraints imposed by the recombination process and the given set of parents. A dynamic programming approach selects optimal breakpoint locations in polynomial time. Application of our method to optimizing breakpoints for an example biosynthetic enzyme, purE, demonstrates the significance of diversity optimization and the effectiveness of our algorithms.