Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published July 2004 | public
Journal Article

Site-directed protein recombination as a shortest-path problem


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.

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.).

Additional details

August 22, 2023
October 24, 2023