Repurposing a chemosensory macromolecular machine.

How complex, multi-component macromolecular machines evolved remains poorly understood. Here we reveal the evolutionary origins of the chemosensory machinery that controls flagellar motility in Escherichia coli. We first identify ancestral forms still present in Vibrio cholerae, Pseudomonas aeruginosa, Shewanella oneidensis and Methylomicrobium alcaliphilum, characterizing their structures by electron cryotomography and finding evidence that they function in a stress response pathway. Using bioinformatics, we trace the evolution of the system through γ-Proteobacteria, pinpointing key evolutionary events that led to the machine now seen in E. coli. Our results suggest that two ancient chemosensory systems with different inputs and outputs (F6 and F7) existed contemporaneously, with one (F7) ultimately taking over the inputs and outputs of the other (F6), which was subsequently lost.


Supplementary Discussion
Our results also shed light on the biological function of CheD. CheD is thought to interact with chemoreceptors in an adaptation mechanism together with CheC and CheY 1 , but more recent results showed that CheD from Bacillus subtilis is able to deamidate chemoreceptors in vitro without CheC 2 . Our results provide two further pieces of evidence supporting the idea that CheD is able to perform a biological role independently of CheC. First, the ancestral F7 system included cheD but not cheC. Second, cheD co-evolved with the ancestral F7 cheY (it was lost in the same evolutionary step), pointing to a functional link.
A recent study in Comamonas testosteroni, an organism with a stage 4 F7 system, shows that the kinase CheA is able to phosphorylate both the ancient CheY as well as the recently acquired CheY-F6-like 3 . Deletion of the CheY-F6-like protein completely abolished chemotaxis response, while the deletion of CheY-F7 only partially affected it. The study further shows that CheY-F7 has a much faster auto-dephosphorylation rate than CheY-F6-like. The authors interpreted these results such that the CheY-F6-like is the primary response regulator, and CheY-F7 may act as a phosphate sink. These conclusions are based on previous work in organisms with multiple CheY genes per chemosensory cluster.
However, because CheY-F7 in stages 1 and 2 is the sole response regulator of the system, we hypothesize that it plays a major role in the control of a yet-unknown cellular process, at least in stages 1 and 2. The rapid auto-dephosphorylation does not necessarily imply a phosphate sink as the main biological function of this CheY. Thus, in the intermediate stages of the extant β-Proteobacteria, including the system in C. testosteroni, the CheY-F7 may retain both the older unknown function as well as its new role in the control of the flagellar motor.
On the other hand, the immediate loss of McpA and adjacent genes from stage 1 to 3, might indicate the loss of the original F7 function. If this were true, why would the system keep a conserved response regulator (cheY) for a lost function? One hypothesis is that the original CheY and CheD might be serving in an auxiliary feedback loop in addition to the canonical CheB/CheR adaptation mechanism in stages 3 and 4. This could compensate response time of the flagellar control as the system acquired mutations to accommodate the new components and function, providing flexibility. In the stage 5, the system evolved to perform optimum response without the need of CheY/CheD adaptation mechanism, resulting in loss of these components in that stage.
Imaging four γ-Proteobacteria with both F6 and F7 systems by cryo-ET, we observed that the arrays formed by different chemosensory systems were both separate and structurally distinct. This is consistent with previous studies showing physical separation of the arrays from different chemosensory gene clusters in V. cholerae (F6 and F9 systems 4 ) and P. aeruginosa (F6 and F7 systems 5 ). It is also consistent with experiments in E. coli showing that engineered chemoreceptors with additional heptads cannot form arrays with shorter, native chemoreceptors, likely because of a large physical mismatch in the CheA/CheW layers 6 .
In all cases, we observed that the F7 arrays in non-enteric γ-Proteobacteria were membraneassociated, but it remains unclear how this is achieved. In other arrays, N-terminal hydrophobic alpha-helices of chemoreceptors mediate membrane insertion. Aer2-like receptors in V. cholerae, P. aeruginosa and S. oneidensis, however, lack any predicted transmembrane regions. The M.
alcaliphilum Aer2-like receptor has two small fragments of transmembrane regions (10 and 14 residues), but these are likely too short to attach the receptor to the membrane. One possibility is that the receptors are post-translationally modified for membrane attachment. Another possibility is that another protein serves as a membrane anchor. Our work ruled out one such candidate -the McpA receptor in the same gene cluster; ΔmcpA F7 arrays were still attached to the membrane.
One of the most striking features of the F7 arrays in non-enteric γ-Proteobacteria was the presence of additional density layers between the CheA/CheW baseplate and the IM. Based on our homology models of the receptors, we propose that these layers correspond to domain features (Fig. 2B). The L2 layer matched the PAS domain present in Aer2-like receptors in all four species.
The fainter (possibly less-ordered) L3 layer in V. cholerae and S. oneidensis matched the additional PAS domain in the Aer2-like receptors from these species. This suggests that PAS domains might mediate intra-and inter-trimer interactions, potentially contributing to cooperativity in the signaling array. The L1 layer matched the junction between the HAMP and signaling domains, which is puzzling because this chemoreceptor region is predicted to have low molecular density 7 .
It is unlikely that this density is produced by another known chemotaxis protein. For example generate a visible density layer 8,9 . Furthermore, previous cryo-ET of in vitro preparations containing only E. coli CheA, CheW and Tsr showed a similar layer in that region, suggesting one or more of these proteins alone is responsible for the L1 layer 10 . Similarly, the L3 layer in P.
aeruginosa F7 array appears to be located between 2 HAMP domains. Interestingly, both P. aeruginosa L3 and the L1 layer in all organisms coincide with a coupling double alpha-helix linker between two four-helical bundles. However, the composition of these layers remains unclear.
Another mystery is the function of the F7 chemosensory array in non-enteric γ-Proteobacteria.
Flagellar motility in these organisms is controlled by the F6 chemosensory system [11][12][13] , which is expressed under a variety of conditions. In contrast, the P. aeruginosa and V. cholerae F7 system is only expressed when cells are grown in stressful conditions such as into late stationary phase, induced by the stress-related sigma factor RpoS 5,14,15 . Expression of the F7 system in different conditions has not been studied in S. oneidensis or M. alcaliphilum, but both organisms live in unique and challenging environments which may be poorly mimicked by laboratory growth; S. oneidensis is a facultative anaerobe adapted to changing environments 16 and M. alcaliphilum is a haloalkaliphilic methanotroph 17 . While we did not test different growth conditions for M. alcaliphilum, we did observe that formation of F7 arrays in S. oneidensis was dependent on culture conditions. Another clue is that both P. aeruginosa and V. cholerae are capable of sensing oxygen, which binds to the PAS-heme domains of Aer2 receptors to activate signaling 18,19 . We therefore favor the working model that the older F7 systems are part of an emergency response system activated by stress conditions, perhaps related to the availability of oxygen. The McpA receptor may also be an important mediator of this response. McpA has no sensory domain, but has been implicated in taxis toward trichloroethylene 20 . A previous study in P. aeruginosa showed that McpA physically co-localizes with F6 system proteins 5 . Here we find that despite being part of the F6 system, McpA co-evolved with the F7 system, suggesting that McpA may bridge the two systems to provide additional inputs to the flagellar control system in response to stress.

Supplementary Figures
Supplementary Figure 1: Phylogeny of CheA, CheB and CheR concatenated alignments of F7 and F8 systems and gene neighborhood of 15 genes up and downstream from CheA. The inlet shows a CheABR tree with additional sequences from F1 systems. The tree is rooted by the common ancestor between F1 systems and the F7/F8 systems.

Supplementary Figure 2:
Phylogenetic profile of the F7 and F6 systems in g-Proteobacteria shows that only organisms with F7 stage 1 (red) or stage 2 (green) systems also has F6 systems. Organisms with F7 stage 5 (blue) does not have F6 systems. Note that the distribution of stage 1and stage 2 are mixed in the non-enteric group. Genomes with empty circles were genomes included in this part of the research but not in the analysis of classifying the F7 systems. The tags in the tips are built using the name of the organism and the locus of the receptor. Tips with red dots belong to chemoreceptors from stage 1 and green to stage 2. The only exception to the monophyletic distribution of Aer2-like receptors were in V. cholerae, where an addition to the Aer2 homolog, a second, orphan 36H receptor (VC0098) was likely introduced by a recent lateral gene transfer from Marinomonas. Genomes with empty circles were genomes included in this part of the research but not in the analysis of classifying the F7 systems. Figure 6: The 1D electron density profile is a collapse of a 3D sub-volume. For each model point (red), the algorithm extends a profile perpendicular to the model points (blue). Then, it averages the intensity of the pixels perpendicular to the profile in the slices above and below (green). The final 1D profile is an average of the profiles calculated for each pixel of the model point.   Figure 2.   Pseudomonas aeruginosa ab2015-05-29-57 dfd11ff2b7b5261968452f994235bece1d208b 793f0c7768b883163fa0cad72c