A Caltech Library Service

Site-directed protein recombination as a shortest-path problem

Endelman, Jeffrey B. and Silberg, Jonathan J. and Wang, Zhen-Gang and Arnold, Frances H. (2004) Site-directed protein recombination as a shortest-path problem. Protein Engineering, Design and Selection, 17 (7). pp. 589-594. ISSN 1741-0126. doi:10.1093/protein/gzh067.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


Protein function can be tuned using laboratory evolution, in which one rapidly searches through a library of proteins for the properties of interest. In site-directed recombination, n crossovers are chosen in an alignment of p parents to define a set of p(n + 1) peptide fragments. These fragments are then assembled combinatorially to create a library of p^(n+1) proteins. We have developed a computational algorithm to enrich these libraries in folded proteins while maintaining an appropriate level of diversity for evolution. For a given set of parents, our algorithm selects crossovers that minimize the average energy of the library, subject to constraints on the length of each fragment. This problem is equivalent to finding the shortest path between nodes in a network, for which the global minimum can be found efficiently. Our algorithm has a running time of O(N^3p^2 + N^2n) for a protein of length N. Adjusting the constraints on fragment length generates a set of optimized libraries with varying degrees of diversity. By comparing these optima for different sets of parents, we rapidly determine which parents yield the lowest energy libraries.

Item Type:Article
Related URLs:
URLURL TypeDescription
Wang, Zhen-Gang0000-0002-3361-6114
Arnold, Frances H.0000-0002-4027-364X
Additional Information:© 2004 Oxford University Press. Received August 12, 2004. Accepted August 16, 2004. Published online August 25, 2004. Edited by Stephen Mayo. We thank Costas Maranas, Matt DeLisa, Jeff Saven and Niles Pierce for their comments on the manuscript. This work was supported by National Institutes of Health Grant R01 GM068664-01, Army Research Office Contract DAAD19-03-D-0004, the W. M. Keck Foundation, a National Defense Science and Engineering Graduate Fellowship (J.B.E.) and NIH Fellowship F32 GM64949-01 (J.J.S.).
Funding AgencyGrant Number
NIHR01 GM068664-01
Army Research Office (ARO)DAAD19-03-D-0004
W. M. Keck FoundationUNSPECIFIED
National Defense Science and Engineering Graduate (NDSEG) FellowshipUNSPECIFIED
NIH FellowshipF32 GM64949-01
Subject Keywords:dynamic programming; laboratory evolution; optimization; protein design; recombination
Issue or Number:7
Record Number:CaltechAUTHORS:20111012-101511149
Persistent URL:
Official Citation:Jeffrey B. Endelman, Jonathan J. Silberg, Zhen-Gang Wang, and Frances H. Arnold Site-directed protein recombination as a shortest-path problem Protein Engineering, Design and Selection (2004) 17(7): 589-594 first published online August 25, 2004 doi:10.1093/protein/gzh067
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:27183
Deposited By: Ruth Sustaita
Deposited On:12 Oct 2011 17:58
Last Modified:09 Nov 2021 16:46

Repository Staff Only: item control page