Why do bacteria use formylated methionine in the initiator tRNA, while eukaryotes do not?
Summary

The question is posed in terms which imply that the formylation of the initiating methionine (Met) of protein synthesis was a relatively late evolutionary development for some purpose not concerned with translation, such as allowing regulation of protein degradation. 

My answer takes the quite different view that this was an early evolutionary development in translation, arising as part of the system for initiating at a specific codon — AUG. With time, the initiating system became more sophisticated, with the specificity of initiation residing more in a separate initiating Met-accepting tRNAf which evolved to have a distinct structure from the elongating Met-accepting tRNAm allowing it to be distinguished from the latter and other elongator tRNAs. 

I postulate that in the line leading to eukaryotes and archaea a mutation subsequently occurred that resulted in a loss of ability to formylate Met-tRNAf, but that individuals with this mutation were viable as initiation had ceased to be dependent on the formylation for discrimination.

Contemporary systems for initiating translation

I constructed the diagram below for an answer to another question, but it shows some of the common features of initiation of protein synthesis in contemporary eukaryotes and prokaryotes. (The reader who wishes more detail on translation is directed to standard text books, e.g. chapter 29 of Berg et al.)



The common features of initiation in eukaryotes and prokaryotes are:
1. The use of  a Met-accepting tRNA with an anticodon that recognises AUG to insert the first amino acid in a protein.
2. That this tRNA, here designated tRNAf (but also designated tRNAi) is distinct from the Met-accepting tRNA used for inserting Met at other points in the protein during elongation.
3. That the (f)Met- tRNAf is recognized by an initiation tRNA-binding factor (I-TBF in the diagram — a non-standard abbreviation) and not by the elongation tRNA-binding factor (E-TBF in the diagram).
4. That the (f)Met- tRNAf is delivered to the P site of the ribosome (otherwise occupied by the growing peptidyl-tRNA), rather than the A site, to which elongator-tRNAs are bound.
5. In many cases the N-terminal Met is removed by proteolysis after translation.

The features of initiation that differ between eukaryotes and prokaryotes are:
1. That the initiating amino acid in eubacteria and mitochondria and chloroplasts  is N-formyl-methionine (fMet), rather than methionine, as is the case in eukaryotes and archaea.
2. The selection of the particular AUG codon for initiation is different in the two cases. In eubacteria and archaea the 16S rRNA binds to a polypurine, Shine and Dalgarno, sequence; in eukaryotes the normal method involves a complex of the small ribosomal subunit and the Met-tRNA ‘scanning’ from the 5ʹ-end of the mRNA (the secondary structure of which is first unwound.

Argument 

As the question about the function of the formylation is posed in evolutionary terms, and fMet-tRNA is involved in the initiation of protein synthesis, it seems valid to consider the evolution of this latter process, however speculative that may inevitably be. The following formulation is my own, although I suspect it represents the orthodoxy in this field. This, of course, does not mean that it is necessarily correct.


It seems likely that initially translation lacked signals for start and stop (and probably also protein initiation factors). I will not deal with termination, other than to say it is probably an easier problem, but initiation would seem to require the introduction of two new features:
(i) The designation of a specific initiation codon AUG†, which, for whatever reason, corresponded to one of the existing amino acids, methionine.
(ii) Given that this initiation codon also served for incorporation of Met internally, the development of a system to select one particular AUG for initiation.
It seems simpler to suppose that (i) preceded (ii), and that is what I shall assume, although the following arguments do not depend on this.
In contemporary initiation the problem of competition between initiation and elongation factors for (f)Met-tRNAs has been solved by the evolution of two separate tRNAs that accept Met — one for initiation and one for elongation. These share certain structural features — their amino acylation is catalysed by the same amino acyl-tRNA synthetase — but they differ in recognition by the protein synthesis factors that bring them to the appropriate P or A site on the ribosome. Despite the lack of formylation of Met-tRNAf in eukaryotes, the structural similarity to the eubacterial tRNAf is such that it can be methylated by E. coli transformylase (reviewed here). However, I imagine that this structurally different tRNA took time to evolve, as, indeed did the protein synthesis factors. 


My argument is that the formylation of Met-tRNA was the basis of the initial discrimination between initiator and elongator Met-tRNAs, and this could have arisen even before the gene duplication that led to separate tRNAs.


Why would fMet-tRNA bind preferentially to the P site and Met-tRNA to the A site? The amino acyl tRNAs that bind at the A site all have a free α-amino group that attacks the linkage of the peptide to the tRNA in the peptidyl-tRNA in the A-site at the peptidyl transferase centre. The peptidyl-tRNA, of course, lacks such a free α-amino group. In this respect fMet-tRNA, with a blocked α-amino group, resembles peptidyl-tRNA (see diagram below). One can imagine how structural differences in the P site could hinder binding of Met-tRNA, but allow binding of fMet-tRNA. And, of course, fMet-tRNA would not be able to react if bound at the A site, which might also have structural features to hinder its binding. 





If subsequently the discrimination became magnified by gene duplication and evolution of a structurally distinct tRNAf, the need for formylation would be diminished, and one could envisage that its subsequent loss in eukaryotes may have had no adverse effects, or was easy to accommodate.  
The question does arise why formylation has persisted in eubacteria, even though it is possible to obtain viable mutants lacking the transformylase. This is what the work alluded to in the question addresses. There is a 2015 paper by Piatkov et al. which suggests that N-terminal fMet can be a degradation system in E. coli. Presumably this arose after the divergence of the line leading to eukaryotes and archaea, which developed other systems for regulating protein turnover.
However I would suggest that, assuming that the foregoing is correct, it is an explanation for the persistence of the formylation of Met in eubacteria, and not the reason for its initial appearance. 


Concluding Remarks

At present I know of no convincing evidence that proves my arguments and rejects the proteolysis idea regarding the reason for the evolution of fMet-tRNA. This is the problem with ideas about early evolution. It is compounded here by the facts that suggestion of a role in proteolysis only came up recently and that this is no longer the ‘hot’ field it was 50 years ago.

Nevertheless, I find it hard to imagine a system as crucial and sensitive as protein synthesis incorporating a feature like formylation of methionine if it only had a secondary function. In this case it would seem easier to formylate the N-termini of proteins post-translationally, as for other N-terminal modifications like acetylation. Furthermore, the finding that the eubacteria-derived mitochondria still use fMet can hardly be to control protein turnover, as the vast majority of mitochondrial proteins are translated in the cytoplasm and lack fMet.

†Footnote

I am aware that, in bacteria especially, there are other possible initiation codons, notably GUG, although the initiating amino acid is always (f)Met. (This attests to the importance of the tRNA structure in contemporary initiation.) It is simpler just to refer to AUG in the argument.