Revealing evolutionarily plausible paths between two homologous but orthogonal PPIs

Some interacting protein pairs exhibit extreme specificities that functionally insulate them even from homologs. Evolution of such binding pairs proceeds mostly by accumulating single-point mutations, and mutants are selected only if their affinity exceeds the threshold required for function. Thus, homologous and functionally insulated (high-specificity) binding pairs bring to light an evolutionary conundrum; namely, how does a new specificity evolve while maintaining the required affinity in each intermediate mutant? We develop a Rosetta energy-based and graph-theoretical framework for discovering low molecular strain single-mutation paths that connect two wild type proteins and apply it to two ultraspecific E. coli colicin endonuclease-immunity pairs. We find that the sequence space defined by the interfaces of the two natural pairs does not contain a strain-free and functional path. By contrast, extending the sequence space to include mutations that bridge amino acids that cannot be exchanged through single-nucleotide mutations yields a strain-free 19-mutation trajectory that is completely functional in vivo. The specificity switch is remarkably abrupt, resulting from only one radical mutation on each side of the interface. We further find that the critical specificity-switch mutations each increase fitness, demonstrating that the functional divergence could have been driven by Darwinian selection rather than by mutational drift. These results reveal how even radical functional changes in an extremely epistatic fitness landscape may evolve.