¹National Center for Supercomputing Applications, University of Illinois at Urbana-Champaign, U.S.A.
²Beckman Institute for Advanced Science and Technology, University of Illinois at Urbana-Champaign, U.S.A.
³Center for Biophysics and Computational Biology, University of Illinois at Urbana-Champaign, U.S.A.
⁴Department of Mathematics, University of Illinois at Urbana-Champaign, U.S.A.
⁵Department of Biology, University of Pennsylvania, Philadelphia, U.S.A.
⁶Renaissance Computing Institute, Chapel Hill, North Carolina 27517, U.S.A.

Protein evolution proceeds by two distinct processes: 1) individual mutation and selection for adaptive mutations and 2) rearrangement of entire domains within proteins into novel combinations, producing new protein families that combine functional properties in ways that previously did not exist. Domain rearrangement poses a challenge to sequence alignment-based search methods, such as BLAST, in predicting homology since the methodology implicitly assumes that related proteins primarily differ from each other by individual mutations. Moreover, there is ample evidence that the evolutionary process has used (and continues to use) domains as building blocks, therefore, it seems fit to utilize computational, domain-based methods to reconstruct that process. A challenge and opportunity for computational biology is how to use knowledge of evolutionary domain recombination to characterize families of proteins whose evolutionary history includes such recombination, to discover novel proteins, and to infer protein-protein interactions. In this paper we review techniques and databases that exploit our growing knowledge of ``horizontal'' protein evolution, and suggest possible areas of future development. We illustrate the power of the domain-based methods and the possible directions of future development by a case history in progress aiming at facilitating a particular approach to understanding microbial pathogenicity.

This work is supported by NSF of USA under Grant Nos. 0835718 and 0235792, NIH under Grant Nos. 5PN2EY016570-06 and 5R01NS063405-02, the Beckman Institute for Advanced Science and Technology, the National Center for Supercomputing Applications, and the Renaissance Computing Institute.