# Evolution of Mitochondria Reconstructed from the Energy Metabolism of Living Bacteria

Mauro Degli Esposti¹*, Bessem Chouaia², Francesco Comandatore³, Elena Crotti², Davide Sassera³ na,
Patricia Marie-Jeanne Lievens¹nb, Daniele Daffonchio², Claudio Bandi³

¹ Italian Institute of Technology, Genoa, Italy, ² Department of Food, Environmental and Evolutionary Sciences, University of Milan, Milan, Italy, ³ Dipartimento di Scienze Veterinarie e Sanità Pubblica, University of Milan, Milan, Italy

<figure><img src="image_1.png" /></figure>

## Abstract

The ancestors of mitochondria, or proto-mitochondria, played a crucial role in the evolution of eukaryotic cells and derived from symbiotic α-proteobacteria which merged with other microorganisms - the basis of the widely accepted endosymbiotic theory. However, the identity and relatives of proto-mitochondria remain elusive. Here we show that methylotrophic α-proteobacteria could be the closest living models for mitochondrial ancestors. We reached this conclusion after reconstructing the possible evolutionary pathways of the bioenergy systems of proto-mitochondria with a genomic survey of extant α-proteobacteria. Results obtained with complementary molecular and genetic analyses of diverse bioenergetic proteins converge in indicating the pathway stemming from methylotrophic bacteria as the most probable route of mitochondrial evolution. Contrary to other α-proteobacteria, methylotrophs show transition forms for the bioenergetic systems analysed. Our approach of focusing on these bioenergetic systems overcomes the phylogenetic impasse that has previously complicated the search for mitochondrial ancestors. Moreover, our results provide a new perspective for experimentally re-evolving mitochondria from extant bacteria and in the future produce synthetic mitochondria.

**Citation:** Degli Esposti M, Chouaia B, Comandatore F, Crotti E, Sassera D, et al. (2014) Evolution of Mitochondria Reconstructed from the Energy Metabolism of Living Bacteria. PLoS ONE 9(5): e96566. doi:10.1371/journal.pone.0096566

**Editor:** Hemachandra Reddy, Oregon Health & Science University, United States of America

**Received** January 10, 2014; **Accepted** April 7, 2014; **Published** May 7, 2014

**Copyright:** © 2014 Degli Esposti et al. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.

**Funding:** This work has been partially supported by the project BIODESERT GA-245746 "Biotechnology from Desert Microbial Extremophiles for Supporting Agriculture Research Potential in Tunisia and Southern Europe" (European Union) and the Prin 2009 (grant 009L27YC8_003), from the Italian Ministry of Education, University and Research (MIUR). Work at IIT has been sustained by intramural funds. The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.

**Competing Interests:** The authors have declared that no competing interests exist.

* E-mail: mauro.degliesposti@iit.it

## Introduction

A major concept in biology is that the evolution of eukaryotic cell followed a symbiotic event between diverse microorganisms [1-4]. Mitochondria are the remnants of one of the original partners of this symbiotic event and in all likelihood are related to extant α-proteobacteria [1-4]. However, the identity of the proto-mitochondrion remains elusive [1]. Phylogenetic studies suggested a relationship with endocellular parasites of the Rickettsiales order [4,5], which has not been confirmed in subsequent reports [6-8]. Indeed, there appears to be a "phylogenetic impasse" in the identification of the partners that merged into the ancestral symbiotic progenitor of current eukaryotic cells [9], partly due to the problem of long branch attraction blurring the true geneology of living organisms and the fast evolution of mitochondrial DNA [1,10].

The diverse metabolic processes carried out by living bacteria provide complementary approaches to reconstruct key characteristics of the mitochondrial ancestors [11]. Although widely accepted, the reconstruction of proto-mitochondrial metabolism [12] has been partially contradicted by recent evidence suggesting that proto-mitochondria could be related to facultatively anaerobic generalists such as *Rhodobacter* [6-8,10] - which are also capable of

anoxygenic photosynthesis, an autotrophic function that must have been lost early along the evolution of mitochondria. Conversely, this evidence has recently been challenged by controversial reports that aerobic marine organisms such as *Pelagibacter ubique* may be the closest living relatives of mitochondria [13-15]. Other bacterial genera have also been considered to be phylogenetically related, or to display some analogies to the proto-mitochondrion: *Rhodospirillum* on the basis of extensive protein analysis [16]; *Paracoccus* for bioenergy considerations [1], and more recently following the evolution of complex I [17]; *Caulobacter*, on the basis of the sequence similarity of its homologues to the mitochondrial transport protein Tim44 [18]; *Micavibrio*, for its predatory ectoparasite character [19]; the Rhizobiales, *Ochrobactrum* and *Rhodopseudomonas*, for having many proteins in sister position to their mitochondrial homologues [6-8,20]; and finally *Midichloria*, which appears to be the sole representative of the Rickettsiales retaining ancestral features typical of free-living bacteria [21]. The wide diversity of the proposed bacterial ancestors of mitochondria arises from the different approaches of molecular evolution that have been used and the inherent limits of such approaches [1-4].

This work follows a novel approach to identify proto-mitochondrial relatives among extant organisms by focusing on

<footnote>na Current address: Dipartimento di Biologia e Biotecnologie, University of Pavia, Pavia, Italy</footnote>

<footnote>nb Current address: Department of Life and Reproduction Sciences, University of Verona, Verona, Italy</footnote>
A

<figure><img src="image_2.png" /></figure>

B

<figure><img src="image_3.png" /></figure>

**Figure 1. Bioenergetic systems of bacteria and mitochondria.** A -Terminal respiratory chain of bacteria. **11.** Various bioenergetic systems - membrane redox complexes identified by their common name and different colours - carry out the oxidation of quinols (QH₂) reduced by dehydrogenases. Besides oxygen (O₂), nitrogen compounds can function as electron acceptors for the oxidation of dehydrogenases (dotted arrow), quinols and cytochrome c (dashed dark blue arrows), in reactions catalysed by enzyme complexes such as Nrf nitrite reductase [32], which are included within the N-metabolism system. Thick black arrows indicate electron transport in aerobic bacteria and mitochondria. Blue arrows indicate other electron transport pathways of facultatively anaerobic bacteria. **B - Pathways of mitochondrial bioenergetic evolution.** The bioenergetic systems illustrated in A are indicated by the coloured modules (with size proportional to their bioenergetic output) within the boxes representing the bioenergetic subset of each organism or organelle. Mitochondria of fungi and heterokont microorganisms differ from those of other eukaryotes for the presence of elements of N-metabolism. Representative taxa with fully sequenced genome are listed beneath each subset. The pathways of mitochondrial evolution are deduced by connecting these subsets with stepwise loss of a single bioenergetic system. Microorganisms underlined are symbionts or pathogens. Bacteria in embossed typeface have been proposed as ancestors or relatives of mitochondria (see Table S1 in File S1 for specific references). Dark brown arrows A and B indicate the pathways leading to fungal mitochondria. The pathway between the Rickettsia subset and that of mitochondria (dashed arrow) can be discounted, since the symbiotic event occurred only once [1,5,6,10,48]. * indicates the subset from which other pathways depart (Figure S1 in File S1).

doi:10.1371/journal.pone.0096566.g001
<table><caption>**Table 1.** Elements of N-metabolism that are shared by bacteria and eukaryotes.</caption><thead><tr><th rowspan="2">Taxonomic group and organism</th><th colspan="3">NAD(P)H dependent, assimilatory</th><th>PQQ-dehydrogenase</th></tr><tr><th>NirB</th><th>NirBD</th><th>NiaD-related proteins</th><th>MxaF</th></tr></thead><tbody><tr><td colspan="5"><strong>methanotrophs & methylotrophs</strong></td></tr><tr><td>Methylocystis sp. SC2</td><td>yes</td><td></td><td>1 domain</td><td>yes</td></tr><tr><td>Methylocystis parvus</td><td></td><td></td><td>precursor & 1 domain</td><td>yes</td></tr><tr><td>Methylosinus trichosporium OB3b</td><td>yes</td><td></td><td>1 domain</td><td>yes</td></tr><tr><td>Methylosinus sp. LW4</td><td></td><td></td><td>1 domain</td><td>yes</td></tr><tr><td>Methylocella silvestris BL2</td><td>yes</td><td></td><td>1 domain</td><td>yes</td></tr><tr><td>Beijerinckia indica*</td><td></td><td>yes</td><td>precursor & 2 domains</td><td>yes</td></tr><tr><td>Microvirga sp. WSM3557</td><td>yes</td><td></td><td></td><td>yes</td></tr><tr><td>Methylobacterium extorquens DM4</td><td></td><td></td><td>3 domains</td><td>yes</td></tr><tr><td>Methylobacterium extorquens PA1</td><td></td><td></td><td>3 domains</td><td>yes</td></tr><tr><td>Methylobacterium extorquens AM1</td><td></td><td></td><td>2 domains</td><td>yes</td></tr><tr><td>Methylobacterium extorquens CM4</td><td></td><td></td><td></td><td>yes</td></tr><tr><td>Methylobacterium extorquens DSM 13060</td><td></td><td></td><td></td><td>yes</td></tr><tr><td>Methylobacterium nodulans ORS 2060</td><td></td><td></td><td>2 domains</td><td>yes</td></tr><tr><td>Methylobacterium populi BJ001</td><td></td><td></td><td>2 domains</td><td>yes</td></tr><tr><td>Methylobacterium radiotolerans JCM 2831</td><td></td><td></td><td>2 domains</td><td>yes</td></tr><tr><td>Methylobacterium mesophilicum SR1.6/6</td><td></td><td></td><td>2 domains</td><td>yes</td></tr><tr><td>Methylobacterium sp. GXF4</td><td></td><td></td><td>2 domains</td><td>yes</td></tr><tr><td>Methylobacterium sp. 88A</td><td></td><td></td><td>2 domains</td><td>yes</td></tr><tr><td>Methylobacterium sp. 4-46</td><td></td><td></td><td></td><td>yes</td></tr><tr><td>Xanthobacter autotrophicus Py3</td><td>yes</td><td></td><td></td><td>yes</td></tr><tr><td>Hyphomicrobium denitrificans 1NES1</td><td>yes</td><td></td><td></td><td>yes</td></tr><tr><td colspan="5"><strong>Bradyrhizobiaceae</strong></td></tr><tr><td>Nitrobacter winogradskyi Nb-255</td><td>yes</td><td></td><td></td><td></td></tr><tr><td>Nitrobacter hamburgensis X14</td><td>yes</td><td></td><td></td><td></td></tr><tr><td>Nitrobacter hamburgensis sp. Nb-255</td><td>yes</td><td></td><td></td><td></td></tr><tr><td>Oligotropha carboxidovorans OM4 & OM5</td><td>yes</td><td></td><td></td><td></td></tr><tr><td>Rhodopseudomonas palustris BisA53</td><td></td><td></td><td>2 domains</td><td>yes</td></tr><tr><td>Rhodopseudomonas palustris BisB18</td><td></td><td></td><td>1 domain</td><td>yes</td></tr><tr><td>Rhodopseudomonas palustris TIE-1</td><td></td><td></td><td>2 domains</td><td></td></tr><tr><td>other 4 Rhodopseudomonas palustris</td><td></td><td></td><td>1 domain</td><td></td></tr><tr><td colspan="5"><strong>Rhodospirillales</strong></td></tr><tr><td>Granulibacter bethesdensis CGDNIH1</td><td>yes</td><td></td><td>2 domains</td><td>yes</td></tr><tr><td>Commensalibacter intestini A911</td><td>yes</td><td></td><td></td><td></td></tr><tr><td>Acidocella sp. MX-AZ02</td><td>yes</td><td></td><td>1 domain</td><td></td></tr><tr><td>Acidiphilium multivorum AIU301</td><td>yes</td><td></td><td></td><td></td></tr><tr><td>Acidiphilium cryptum & sp. PM</td><td>yes</td><td></td><td>1 domain</td><td></td></tr><tr><td>Gluconobacter oxydans H24</td><td></td><td>yes</td><td>precursor & 2 domains</td><td></td></tr><tr><td>Gluconobacter frateurii NBRC 103465</td><td></td><td>yes</td><td>precursor</td><td></td></tr><tr><td>Gluconacetobacter oboediens 174Bp2</td><td></td><td>yes</td><td>precursor & 2 domains</td><td></td></tr><tr><td>Acetobacter pasteurianus IFO 3283-01/32</td><td></td><td>yes</td><td>precursor</td><td></td></tr><tr><td>Acetobacter aceti</td><td></td><td>yes</td><td>precursor & 1 domains</td><td></td></tr><tr><td>Gluconacetobacter europaeus LMG 18494</td><td></td><td>yes</td><td>precursor</td><td></td></tr><tr><td>Gluconacetobacter diazotrophicus PAI5</td><td></td><td></td><td>2 domains</td><td></td></tr><tr><td>Acetobacter pomorum DM001</td><td></td><td>yes</td><td></td><td></td></tr><tr><td>Acetobacter tropicalis NBRC 101654</td><td></td><td>yes</td><td></td><td></td></tr><tr><td>Asaia platicody</td><td></td><td>yes</td><td>precursor</td><td></td></tr><tr><td>Saccharibacter sp.</td><td>yes</td><td></td><td>2 domains</td><td></td></tr></tbody></table>
<table><caption>**Table 1.** Cont.</caption><thead><tr><th rowspan="2">Taxonomic group and organism</th><th colspan="3">NAD(P)H dependent, assimilatory</th><th>PQQ-dehydrogenase</th></tr><tr><th>NirB</th><th>NirBD</th><th>NiaD-related proteins</th><th>MxaF</th></tr></thead><tbody><tr><td>Tistrella mobilis KA081020-065</td><td>yes</td><td></td><td>2 domains</td><td></td></tr><tr><td>Azospirillum lipoferum 4B</td><td>yes</td><td></td><td>1 domain</td><td>yes</td></tr><tr><td>Azospirillum amazonense Y2</td><td>yes</td><td></td><td></td><td></td></tr><tr><td>Azospirillum brasilense Sp245</td><td>yes</td><td></td><td></td><td></td></tr><tr><td>Azospirillum sp. B510</td><td>yes</td><td></td><td></td><td></td></tr><tr><td>Caenispirillum salinarum AK4</td><td>yes</td><td></td><td></td><td></td></tr><tr><td>Thalassospira profundimaris WP0211</td><td>yes</td><td></td><td></td><td></td></tr><tr><td>Thalassospira xiamenensis M-5</td><td>yes</td><td></td><td></td><td></td></tr><tr><td>Magnetospirillum magneticum AMB-1</td><td>yes</td><td></td><td></td><td></td></tr><tr><td>Magnetospirillum sp. SO-1</td><td>yes</td><td></td><td></td><td></td></tr><tr><td>Magnetospirillum gryphiswaldense MSR-1</td><td>yes</td><td></td><td></td><td></td></tr><tr><td><strong>Rhodobacterales</strong></td><td></td><td></td><td></td><td></td></tr><tr><td>Oceanicola granulosus</td><td></td><td></td><td>1 domain</td><td></td></tr><tr><td>Oceanicola sp. S124</td><td>yes</td><td></td><td></td><td></td></tr><tr><td>Octadecabacter antarcticus 307</td><td>yes</td><td></td><td></td><td></td></tr><tr><td>Paracoccus denitrificans PD1222</td><td>yes</td><td></td><td></td><td></td></tr><tr><td>Roseobacter denitrificans OCh114</td><td>yes</td><td></td><td></td><td></td></tr><tr><td>Roseobacter litoralis Och 149</td><td>yes</td><td></td><td></td><td></td></tr><tr><td>Jannaschia sp. CCS1</td><td>yes</td><td></td><td></td><td></td></tr><tr><td><strong>Rhizobiales (other)</strong></td><td></td><td></td><td></td><td></td></tr><tr><td>Martelella mediterranea</td><td></td><td></td><td>precursor</td><td></td></tr><tr><td>Aureimonas ureilytica</td><td></td><td></td><td>2 domains</td><td></td></tr><tr><td>Sinorhizobium meliloti 1021</td><td>yes</td><td></td><td>2 domains</td><td></td></tr><tr><td>Rhizobium leguminosarum bv. trifolii WSM1325</td><td>yes</td><td></td><td></td><td></td></tr><tr><td>other 32 Rhizobiales</td><td>yes</td><td></td><td></td><td></td></tr><tr><td><strong>Sphingomonadales & Caulobacterales</strong></td><td></td><td></td><td></td><td></td></tr><tr><td>Novosphingobium nitrogenifigens</td><td></td><td></td><td>precursor</td><td></td></tr><tr><td>Sphingomonas sp. 17</td><td></td><td></td><td>2 domains</td><td></td></tr><tr><td>Sphingomonas sp. PAMC26621</td><td></td><td></td><td>1 domain</td><td></td></tr><tr><td>Sphingopyxis alaskensis RB2256</td><td>yes</td><td></td><td></td><td></td></tr><tr><td>other 19 Sphingomonadales & 6 Caulobacterales</td><td>yes</td><td></td><td></td><td></td></tr><tr><td><strong>total α-proteobacteria</strong></td><td>ca. 100</td><td>10</td><td>12 precursors</td><td></td></tr><tr><td><strong>Eukaryotes</strong></td><td></td><td></td><td></td><td></td></tr><tr><td>Aspergillus fumigatus</td><td></td><td>yes</td><td>yes</td><td></td></tr><tr><td>other 130 fungi (predominantly Ascomycetes)</td><td></td><td>yes</td><td>yes</td><td></td></tr><tr><td>Ectocarpus silicosus</td><td></td><td>yes</td><td>yes</td><td></td></tr><tr><td>plus other 8heterokonts</td><td>(1 yes)</td><td>yes</td><td>yes</td><td></td></tr><tr><td>Aureococcus anophagefferens</td><td></td><td>yes</td><td>yes & 2 domains</td><td></td></tr><tr><td>Acanthamoeba castellani</td><td></td><td></td><td>yes</td><td></td></tr><tr><td><strong>total Eukaryotes</strong></td><td>1</td><td>140</td><td>141</td><td></td></tr></tbody></table>

Proteins closely related to *NirB*, *NirBD*, *NiaD* and *MxaF* are annotated as **yes**, or **precursor** in the case of *Nas/CysJ* nitrate reductase (Fig. 2). The column of *NiaD*-related proteins also lists the number of *NiaD* **domains** that have homologues proteins in each organism, e.g. flavohaem (cf. Fig. 2C).

*Its close relative *Beijerinckia mobilis* has been reported to grow on methanol and possess *MxaF*.

doi:10.1371/journal.pone.0096566.t001

the bioenergetic systems that are common between mitochondria and bacteria. An enormous increase in bioenergy production constitutes the major advantage gained in the endosymbiotic event that led to the evolution of eukaryotic cells [2]. Consequently, the mitochondrial systems that generate most cellular bioenergy must

define the minimal bioenergetic capacity of proto-mitochondria. Whereas aerobic α-proteobacteria such as *Pelagibacter* present the same two bioenergetic systems of animal mitochondria [4,12], other proposed ancestors of mitochondria such as *Rhodos pseudomonas palustris* [6–8] possess four additional bioenergetic systems in their
<figure><img src="image_4.png" /></figure>

<figure><img src="image_5.png" /></figure>

<figure><img src="image_6.png" /></figure>

<figure><img src="image_7.png" /></figure>

<figure><img src="image_8.png" /></figure>

<figure><img src="image_9.png" /></figure>

<figure><img src="image_10.png" /></figure>

<figure><img src="image_11.png" /></figure>

eukaryotic nitrate reductase mitochondrial sulfite oxidase

<figure><img src="image_12.png" /></figure>

sister groups

Neighbour joining

0.5
**Figure 2.** Graphical representation of assimilatory nitrate reduction in protists and α-proteobacteria. **A** – The diagram shows the gene clusters of assimilatory, NAD(P)H-dependent nitrate reduction in bacteria and eukaryotes. The various elements of *Nas* operon of *Klebsiella* [36] and the *NiiA-NiaD* operon in fungi [35] are colour coded as indicated in the quandrant on the top right. **B** – Possible molecular evolution of fungal *NiaD* nitrate reductase. Each domain is identified by a specific symbol - see the text for details. **C** – Representative distance tree of various proteins containing the bacterial FNR-like conserved domain. The tree was obtained with Neighbour Joining (maximal distance 0.9) using the DELTABLAST program [80] with methane monooxygenase subunit c of *Methylocella silvestris* (MMOc, Accession: YP_002361598) as query. This reductase subunit of methane monooxygenase contains a FNR-like domain similar to that of assimilatory nitrate reductases [43] lying in a sister group as indicated.
doi:10.1371/journal.pone.0096566.g002

terminal respiratory chain (Fig. 1A). These systems are character-
istic of bacteria living under anaerobic or micro-oxic conditions,
exploiting also bioenergy-producing elements of N-metabolism
which are partially retained in some eukaryotic microorganisms
[10,22,23]. It is thus likely that the current bioenergetic portfolio of
mitochondria has evolved from a larger genomic endowment of
bioenergetic systems which has been reduced via sequential loss.

We have reconstructed the possible pathways of this sequential
loss leading to the bioenergetic systems of current mitochondria by
evaluating all the genomes of α-proteobacteria which are currently
available. Results obtained with complementary approaches then
converged in indicating that methylotrophic α-proteobacteria
could be the closest living relatives to proto-mitochondria, while
excluding the majority of bacteria previously proposed as
mitochondrial relatives.

**Results and Discussion**

1.1 Reconstructed pathways of bioenergetic evolution of
bacteria into mitochondria

The bioenergetic capacity of mitochondria has been instru-
mental in the evolution of eukaryotic cells and complex life forms
[1–3]. It is generally assumed that proto-mitochondria had an
aerobic energy metabolism equivalent to that of today’s mito-
chondria [1,4,12], with the central part of the respiratory chain
consisting of ubiquinol-cytochrome c reductase (the cytochrome bc1
complex) and a single terminal oxidase, cytochrome aa3 oxidase
(Fig. 1A). However, geophysical evidence indicates that proterozoic oceans were essentially anoxic during the period in which the
eukaryotic cell evolved [24]. Consequently, it is likely that proto-mitochondria were adapted to different levels of environmental
oxygen, exploiting also the terminal oxidases of facultatively
anaerobic bacteria to obtain bioenergy [10]. For example,
*Rhodopseudomonas* strains possess cytochrome bd and bo ubiquinol
oxidases [25,26], plus an additional cytochrome c oxidase of the
cbb3 type [27] (Fig. 1B). Endocellular parasites have the bd
ubiquinol oxidase either alone (in several species of *Rickettsia* [28])
or together with cbb3 oxidase (in *Midichloria mitochondrii* [21]). Other
organisms, moreover, possess proteins of the anaerobic bioenergetic process of denitrification, which are found also in mitochondria of fungi that can adapt to anaerobiosis [10,23,29].

Fungi and heterokont protists additionally possess an assimila-
tory nitrite reductase which is involved in ammonia fermentation,
*NirB* fused with *NirD* [23,29] – hereby defined as *NirBD*. In some
bacteria, this NAD(P)H-dependent enzyme forms part of the
nitrogen cycle that enables their growth from the oxidation of
methane or ammonia, the oxidation of C1 compounds such as
methanol (methylotrophy) and ammonification of nitrite [30–32].
Because various elements of this nitrogen cycle are associated with
bioenergy production [23,29–32], we have considered them within
the broad bioenergetic system of N-metabolism (Fig. 1).

The metabolic versatility of current bacteria suggests that the
ancestors of α-proteoproteobacteria had six bioenergetic systems
from ubiquinol to oxygen (Fig. 1B), like diverse extant bacteria
(Table S1 in File S1). To deduce the pathways of differential loss

that led to the reduced subset of current mitochondria, we have
developed a model based upon the bioenergetic systems coded in
all available genomes of α-proteobacteria, including those we have
recently sequenced (*Asaia platicody* and *Saccharibacter sp.* [22]). For
parsimony, we allowed only single-step connections between the
various subsets, thus obtaining two alternative pathways which
directly lead to the subset of bioenergetic systems that is present in
contemporary mitochondria of fungi and protists (Fig. 1B, cf. Fig.
S1 in File S1). Pathway A stems from the subset present in
predatory *Micavibrio* [19] and also *Beijerinckia indica*, a metabolically
versatile organism closely related to methylotrophs [33] which has
been shown to possess several proteins strongly related to their
mitochondrial homologues [8]. Alternative pathway B originates
from the subset present in some *Magnetospirillum* species and two
Rhodobacterales (Fig. 1B): *Roseobacter litoralis*, which retains a
functional photosynthetic apparatus, and *Maricaulis maris*, which
has a dimorphic biological cycle. The loss of N-metabolism from
the *Micavibrio/Beijerinckia* subset leads to the subset of *Rickettsia* [28]
and *Wolbachia* organisms which retain the *bd* ubiquinol oxidase
system (Fig. 1B). The loss of this bioenergetic system would also
lead to the subset of metazoan (but not fungal) mitochondria, a
possibility considered unlikely in view of the unique symbiotic
event producing mitochondria [1,2,10]. Moreover, it occurs in
related species of the same Rickettiales order (Fig. 1B) and other
taxa, for example within the *Bartonella* genus (Fig. S1 in File S1),
suggesting phenomena of convergent evolution.

1.2 Testing the alternative pathways for mitochondrial
bioenergy evolution

So, comparative genomic analysis has allowed a reconstruction
of two possible reductive pathways in the bioenergetic capacity of
bacteria evolving into mitochondria (Fig. 1). How can we establish
which of these pathways is most likely, and thus identify extant
models for proto-mitochondria? Probabilistic approaches based
upon the frequency of gene loss from each subset would not
produce conclusive evidence, because of the biased phylogenetic
distribution of available bacterial genomes. We have then carried
out the classical phylogenomic approach of computing the overall
relationships of the organisms in the model of Fig. 1B by using
concatenated proteins that are common to most eubacteria (cf.
Ref. [21]). Although the obtained trees could be globally consistent
with the sequence of either pathway A or B, they did not offer
discriminatory evidence in favour of one or the other, while
consistently placing *Midichloria* and other Rickettsiales close to the
mitochondrial clade. This tree topology has been reported before
[1,4,5,21] but is inconsistent with our new model of Fig. 1B and
other evidence [1], as discussed above.

We next followed the alternative approach of exploiting the
molecular diversity of key bioenergetic proteins, including their
multiple duplication [34]. To enhance the discriminatory power of
this approach, we have chosen proteins of energy metabolism that
have a clear bacterial origin, but are encoded or located in
different compartments of eukaryotic cells (cf. [34]). The
hypothesis underlying our approach is that such diverse proteins,
A

<figure><img src="image_13.png" /></figure>

<figure><img src="image_14.png" /></figure>

<figure><img src="image_15.png" /></figure>

<figure><img src="image_16.png" /></figure>

Cyt_c_oxidase_III, CD01665

Type a

a Rhodopseudomonas

a-I Methylocystis

a-II Methylobacterium

a-III Acetobacteraceae AT-5488

<figure><img src="image_17.png" /></figure>

<figure><img src="image_18.png" /></figure>

Variovorax paradoxus

Transition a-b

<figure><img src="image_19.png" /></figure>

Type b

Beijerinckia

<figure><img src="image_20.png" /></figure>

Magnetospirillum

<figure><img src="image_21.png" /></figure>

<figure><img src="image_22.png" /></figure>

Micavrio

<figure><img src="image_23.png" /></figure>

<figure><img src="image_24.png" /></figure>

Roseobacter

<figure><img src="image_25.png" /></figure>

<figure><img src="image_26.png" /></figure>

syntheny Protist mitochondria

B

<figure><img src="image_27.png" /></figure>

0.2

sister groups

C

<figure><img src="image_28.png" /></figure>

<figure><img src="image_29.png" /></figure>
**Figure 3.** α-proteobacteria have different types of COX operons and catalytic subunits of aa₃ oxidase. A - Graphical representation of aa₃ oxidase gene clusters. The different COX clusters of α-proteobacteria are classified by considering gene sequence variations and the features of flanking genes (see also "Classification of bacterial COX operons" in File S1). Specific graphical symbols identify COX subunits as indicated; other types of proteins are labelled as follows: white hexagon, enzyme working with RNA or DNA; red diamond with enclosed c, cytochrome c type protein; truncated triangle pointing left, ABC transporter/permease; grey sharp triangle, transcription regulator; PQQ, PQQ-dependent dehydrogenase; white diamond, protein belonging to a DUF family [41], e.g. DUF983; question mark within hexagon, completely unknown protein. Note that *SURF1* (Surfeit locus protein 1) and *SCO* (Synthesis of cytochrome c oxidase) are also involved in the biogenesis of oxidases. Distance between genes is arbitrary. COX operon type a-l is attached to a Nrf-like gene cluster, also called Alternative Complex III or Act [50], containing two homologues of the membrane subunit *NrfD* (called *NrfD2* and *NrfD*-like here, as shown at the side of the figure). The synthenic diads of protist mitochondria [48] are shown below the blue line. Each of the recognised subfamilies of COX3 [41] is represented by a different colour, as indicated in the middle of the illustration. B - Representative distance tree of COX1 proteins. The tree was obtained with Neighbour Joining (maximal distance 0.9) using the DELTABLAST program [80] with the COX1 protein of *Methylobacterium extorquens* PA1 (Accession: YP_001637594) as query. The group containing bacterial and mitochondrial proteins (mito.) is enclosed in the blue square. Protein length and type of COX operon are annotated on the right of the tree. C - Simplified pattern of typical phylogenetic trees of COX1 proteins. The tree is modelled to match distance trees of nitrate reductase (Fig. 2C) and COX1 (part B). Branch length is arbitrary.
doi:10.1371/journal.pone.0096566.g003

as well as their genetic clusters, would present transition forms between bacteria and mitochondria predominantly in those organisms that are close to the proto-mitochondrial lineage.

## 2. Molecular evolution of assimilatory N metabolism

The first bioenergetic system we considered is N metabolism, the presence or absence of which sharply determines the pathways leading to the mitochondria of fungi and metazoans (Fig. 1B). As mentioned above, fungi and heterokonts possess the assimilatory, NAD(P)H-dependent nitrite reductase *NirBD* [35], a cytosolic enzyme which is common among facultatively anaerobic γ-proteobacteria such as *Klebsiella*, where it was originally called *NasB* [36]. Structurally, *NirBD* is characterised by the fusion of the small protein *NirD* - belonging to the Rieske superfamily of Fe-S proteins coordinated by histidines and cysteines [37] - at the C-terminus of the *NirB* protein, which catalyses the reduction of nitrite and is structurally related to sulfite reductase (*SiR*) [38]. Interestingly, the distribution of *NirB* is restricted to a relatively narrow group of facultatively anaerobic bacteria [38,39], but that of *NirBD* is much narrower (Table 1). After finding *NirBD* in the genome of *Asaia*, we detected only ten homologous genes among α-proteoproteobacteria - compared with over one hundred in fungi (Table 1), all arranged in similar gene clusters comprising a regulator, nitrate transporters and an assimilatory nitrate reductase. The gene clusters are related to the *Nas* operon of *Klebsiella* (Fig. 2A), with its most compact version being present in fungi and Oomycetes [35].

Among the bacteria associated with pathway A and B in Fig. 1B, only *Beijerinckia* possesses *NirBD* and its cognate gene cluster. *Roseobacter litoralis* and *Magnetospirillum* have *NirB* within an operon similar to that of *Klebsiella* (Fig. 2A), whereas *Maricaulis* and *Micavibrio* do not have the same genes. This situation may well arise from secondary loss of metabolic traits in ecologically specialised organisms such as dimorphic *Maricaulis* and predatory *Micavibrio*. To gain further phylogenetic information, we then exploited the rare occurrence of *NirBD* and its associated nitrate reductase among α-proteoproteobacteria (Table 1), evaluating the molecular evolution of these modular proteins. The structure of *NirBD* is conserved in α-proteobacteria and eukaryotes [35] and apparently derives from *NirB* precursors that are present in methylotrophs such as *Methylocystis* (Fig. 2, cf. [35]).

Conversely, the structure of the large protein functioning as nitrate reductase in the *NirBD* gene cluster of α-proteobacteria resembles that of nitrate reductases from ancient bacteria such as *Gordonia*, which contains three redox modules formed by distinct domains. A typical Molybdenum cofactor-binding domain (Moco) occupies the N-terminus and includes a terminal part binding another molibdopterin cofactor as in *NapA* (periplasmic) and *NasA* (cytoplasmic) reductases [36–40]. This is followed by an intermediate domain homologous to the small redox protein flavodoxin

(Fig. 2B top, cf. [38]). The C-terminus then contains a flavoprotein reacting with the electron donor NAD(P)H which, in combination with flavodoxin, forms a domain closely related to sulfite reductase *CysJ* of *E.coli* (represented by a grey bar in Fig. 2B, cf. [38]). The *CysJ*-related domain belongs to the superfamily of Ferredoxin Reductase-like domains, cd 00322 FNR-like [41], which includes also the C-terminal domain of fungal nitrate reductase, *NiaD* [35,40].

Although the fine structure of the FNR-like domain indicates two separate subfamilies, cd01699 *SiR* like for the *NasA/CysJ* bacterial proteins and cd06183 *cytb5_reductase_like* for the eukaryotic proteins, our detailed sequence comparison uncovered phylogenetic relationships with other bacterial proteins belonging to the same superfamily. In particular, flavodoxin reductases of the genus *Methylobacterium* and the reductase subunits of soluble methane monoxygenase [42,43] (MMO, present also in close relatives of *Beijerinckia* such as *Methylocella*) were consistently found in sister clades to *NiaD* and related proteins of fungi, heterokonts and *Acanthamoeba* (Fig. 2C and Table 1). Moreover, the flavohaem oxidoreductase of *Beijerinckia* (accession YP_001833084), which contains a cytochrome *b*-related globin followed by a FNR-like domain, was found in an intermediate position between the *NiaD*-containing clade and the *NasA-CysJ* reductases of *Beijerinckia* and *Methylocystis parvus* (Fig. 2C). Notably, the gene of this protein is located at the beginning of *Beijerinckia* nitrate assimilation operon (Fig. 2A). Its Nitric Oxide dioxygenase activity is also similar to that of the hybrid nitrate reductase of microalgae from the heterokont group, e.g. *Chattonella subsalsa* (protein NR2-2/2HbN, accession: AER70127), which possess both a cytochrome *b*₅ and a globin in the intermediate domain [44]. These flavoproteins, therefore, could be considered transition forms between *NapA/CisJ* reductases and eukaryotic assimilatory nitrate reductases.

In further support of the modular similarity between bacterial and eukaryotic NAD(P)H-dependent nitrate reductases, we have found that the Moco domain of *NiaD*-like eukaryotic proteins is present also in the sulfite oxidase of methylotrophs such as *Methylobacterium mesophilicum* and *extorquens* (accession: WP_010685750 and WP_003602739, respectively - Table 1 and Fig. 2B). Moreover, the genome of *Methylobacterium extorquens* PA1 encodes a protein that is partially similar to bacterial cytochrome *b*₅ (accession: YP_001638730), which is present only in *Rhodopseudomonas palustris* among α-proteobacteria (Fig. 2B and data not shown). Consequently, all three functional domains of eukaryotic assimilatory reductases have homologous proteins in extant α-proteobacteria, particularly among those with methylotrophic metabolism, as indicated by the presence of the signature methanol dehydrogenase *MxaF* [45] (Table 1). Hence, our data suggests that *NasA-CisJ* reductases of *Beijerinckia* and acetic acid bacteria, e.g. *Asaia*, represent the likely **precursors** of eukaryotic,
A

<figure><img src="image_30.png" /></figure>

B

<figure><img src="image_31.png" /></figure>

C

<figure><img src="image_32.png" /></figure>
**Figure 4.** Analysis of the molecular architecture of *COX3* in bacteria and protists. **A** – Alignment of bacterial and mitochondrial *COX3* proteins. A set of aligned *COX3* sequences from bacteria and protists was initially obtained from the DELTABLAST option of multiple alignment and subsequently implemented manually following data available from the structure of beef [59,60], *Paracoccus* [61] and *Thermus* [54] *aa*₃ oxidase. Residues that bind phospholipids with either H or π bonds [60] are in yellow character and highlighted in dark grey, while those conserved are in bold character. Light grey areas indicate transmembrane helices (TM). **B** – Graphical representation of *COX1-3* fused proteins. The hydrophobic peaks in the hydropathy profile of the proteins, which was obtained using the program WHAT [81] with a fixed scanning window of 19 residues, is represented by the sharp triangles, that are commensurate to the peak height (maximum in the hydrophobicity profile) and width of the predicted TM [81], which closely correspond to those observed in 3D-structures [47,54,61]. **C** – Deduced sequence of the “minimal” *COX operon* of protists. The arrangement of *COX* genes essentially corresponds to the core sequence of a *COX* operon of type a (cf. Fig. 3) but in the reverse order of transcription. Dashed symbol represents a protein that may intermix with other *COX* subunits such as a *COX4*-like (Fig. S2 in File S1). doi:10.1371/journal.pone.0096566.g004

*NiaD*-related nitrate reductase (Table 1 and Fig. 2B,C). The parallel evolution of mitochondrial sulfite oxidase, which shares the same cytochrome *b*₅ and Moco domains with eukaryotic assimilatory nitrate reductases (Fig. 2B, cf. [38,40]), underlines the intersection of this molecular reconstruction with the evolutionary trajectory of proto-mitochondria.

**3. Evolution of COX genes and proteins from bacteria to mitochondria**

To test alternative evolutionary pathways for mitochondria (Fig. 1B) we next studied the cytochrome *c* oxidase of *aa*₃-type (also called *COX*), which appears to be the most common terminal oxidase in extant α proteobacteria (Fig. 1 and Table S1). In eukaryotes, this enzyme complex is embedded in the inner mitochondrial membrane, combining catalytic subunits of bacterial origin with various nuclear-encoded subunits of unknown function. Although all *aa*₃-type oxidases are of type A according to the classification of heme-copper oxygen reductases [26], the complexity of their gene clusters has not been considered before. Here, we have analysed in depth this complexity for it provides valuable phylogenetic information. Various aspects of our analysis are presented below in the following order: 1, diversity of *COX* operons; 2, evolution of *COX* operons; 3, possible *COX* operons of proto-mitochondria; 4, evolution of the molecular architecture of *COX*3; 5, phylogenetic distribution of *COX* operons.

**3.1 Diversity of COX operons.** We have initially undertaken a systematic analysis of the genomic diversity of *aa*₃-type oxidases. The scrutiny of all the gene clusters containing proteobacterial *COX* subunits [46–51] suggests that they fall into three distinctive types of *COX* operons, which we called type a, b and a–b transition (Fig. 3A – see Table S2 and “Classification of bacterial *COX* operons” in File S1 for a detailed account of this classification). *COX* operon type a is divided in four subtypes on the basis of *COX*1 length and diverse adjacent genes (Fig. 3). These subtypes form coherent clades in the phylogenetic trees of their *COX*1 subunit (Fig. 3B). Despite the variation in gene sequence, all *COX* operons appear to derive from the core structure of the *cta*4-G operon of *Bacillus subtilis* [46–51] (Fig. 3A), which consists of the catalytic subunits *ctaC* and *ctaD* (corresponding to mitochondrial *COX*2 and *COX*1, respectively) followed by the hydrophobic, non-catalytic subunit *ctaE* (corresponding to mitochondrial *COX*3) and *ctaF* (also called *COX*IV or *COX*4). Mitochondrial DNA (mtDNA) of eukaryotes generally encodes for *COX*1, *COX*2 and *COX*3 [48]. In bacteria, these principal subunits are often combined with proteins for the assembly of the metal cofactors of the oxidase: *ctaA* (heme A syntase or *COX*15), *ctaB* (protoporphyrin IX farnesyl transferase, or *COX*10) and *ctaG* (Cu-delivery protein, or *COX*11).

Our systematic analysis of bacterial *COX* subunits has revealed a novel fusion between *COX*1 and *ctaF/COX*4 (Fig. S2 in File S1). This fusion appears to be restricted to *COX* operon type a-II (Table S2 in File S1 and Fig. 3A) that often contains Pyrroloquino-line quinone (PQQ)-dependent dehydrogenases such as methanol dehydrogenase related to *MxaF* (Fig. 3A). *COX*4 is broadly related

to the *ctaF* subunit, which is the least conserved in the *caa*₃-type oxidase of *Thermus* and *Bacillus* [47] but can be recognized as part of *Cyt_c_ox_IV* (pfam12270 [52]). However, the diverse forms of short hypothetical proteins that intermix with *COX* subunits (Fig. 3A) are generally not recognized as members of this family in BLAST searches, due to the wide variation in their size and sequence [47]. Therefore, we have developed a method that quantifies the sequence similarity with the *COX*IV proteins from *Rhodobacter* [53] and *Thermus* [47,54], for which the 3D structure is available (see Fig. S2 in File S1 and its legend for details). Strong sequence similarity with these *COX*4 proteins was found in the C-terminal extension of bacterial *COX*1 proteins that are 630 to 670 aa long, as well as in mitochondrial *COX*1 of the pathogenic fungus, *Zymoseptoria tritici* [55] (Fig. S2A in File S1). We additionally identified the sequence signatures of *COX*4 in small proteins previously recognized as domain with unknown function (DUF [52]) families, namely DUF2909 and DUF983 (Figs. 3 and S3 in File S1). Morever, the C-terminal part of the mtDNA-encoded *COX*1 of ciliates, an ancient and diverse phylum of unicellular eukaryotes [56], shows some sequence similarity encompassing both transmembrane helices of *COX*4 proteins (Fig. S2A and B in File S1). Although this similarity is clearly weaker than that observed with bacterial *COX*1 proteins, it lies in a conserved region among ciliates (Fig. S2A in File S1 and data not shown) thereby suggesting that fusion of *COX*1 with *COX*4 might represent an additional trait shared by bacteria and mitochondria.

**3.2 Evolution of COX operons.** The identification of *COX*4-like proteins has been combined with phylogenetic analysis to deduce the possible evolution of *COX* operons. The long proteins derived from the fusion of *COX*1 with *COX*3 (hereafter called *COX*1-3) seem to be the most distant from their mitochondrial homologues (Fig. 3B). These proteins are characteristic of *caa*₃ oxidases [46,47], as well as of *COX* operon type a, which can therefore be considered the ancestral form of proteobacterial gene clusters for *aa*₃-type oxidases (Fig. 3A). The differentiation into other types of COX operons can be evaluated also from the phylogenetic trees of the catalytic subunit *COX*1, the analysis of which has offered new evidence for discriminating the evolutionary pathways in Fig. 1B.

*COX*1 proteins fused with *COX*4 (see above) appear to follow the ancestral *COX*1-3 in phylogenetic trees and are always upstream of a major bifurcation in two large groups: one containing only proteins of *COX* operon a-b transition that are present in β- and γ-proteobacteria, and the other containing bacterial *COX*1 proteins of *COX* operon type b together with their mitochondrial homologues (blue square in Fig. 3B). Mitochondrial *COX*1 proteins cluster in a monophyletic clade that lies in sister position of closely packed bacterial sub-branches, especially that containing Rhodospirillales (Fig. 3B). This overall tree topology is consistently found with all methods, whereas the branching order within the group containing the mitochondrial clade may vary, depending upon the method and taxa used to construct the phylogenetic trees (Fig. 3B and data not shown). Nevertheless, it is noteworthy that all the
A

<figure><img src="image_33.png" /></figure>

B

<figure><img src="image_34.png" /><figcaption>**Figure 5.** Structure-function features of COX3 gradually evolved from bacteria to mitochondria. A – Heatmap for the strength of phospholipid binding by COX3 proteins. The table summarises the molecular features of PL-binding sites (residues) in aligned COX 3 proteins (Table S4 in File S1); it is colour mapped according to the number of conserved sites to represent the increasing PL-binding strength along bacterial and mitochondrial protein sequences, as indicated by the legend on the right of the table. PL-binding is considered weak when less than 3 sites are</figcaption></figure>
conserved for each PL, the nomenclature of which is taken from Ref. [60]. PE, phosphatidyl-ethanolamine; PG, phosphatidyl-glycerol. The list includes conserved amino acids corresponding to E90 in beef *COX3*, which lies near bound PL modulating oxygen entry into the catalytic site of the oxidase [60]. Abbreviations for organisms are: *Rhodo_palu_BisA53*, *R. palustris* BisA53; *Variovorax_par*, *Variovorax paradoxus*; *Methylophi_bac*, *Methylophilales bacterium* HTCC2181; *Wolbachia_Dro_sim*, *Wolbachia* endosymbiont of *Drosophila simulans*. **B - Representative distance tree of COX 3 proteins.** The tree was obtained as described in the legend of Fig. 3B, using as a query the C-terminal region of the *COX1*-3 protein from *R. palustris* BisA53 (Accession: YP_782773, residues 550 to 841) that aligns with bacterial and mitochondrial *COX3* (Fig. 4A). The group containing bacterial proteins from *COX* operon type b and their mitochondrial homologues is enclosed in a blue square as in Fig. 3B.
doi:10.1371/journal.pone.0096566.g005

proteins belonging to *COX* operon type b lie in the same group containing the mitochondrial clade, as exemplified in Fig. 3C. Hence, bacteria having only *COX* operon type b cannot be the ancestors of mitochondria. This exclusion encompasses the majority of extant α-proteobacteria, because the presence of other *COX* operons is restricted to a fraction of these organisms (Table S2 in File S1). We then needed additional information to identify which of the organisms containing multiple *COX* operons may be close to proto-mitochondria. To this end, we next moved to the analysis of *COX* proteins of unicellular eukaryotes.

**3.3. Possible COX operons of proto-mitochondria.** Recently, *COX11* and *COX15* have been found in the mtDNA of Jakobida, an ancient lineage of protists, despite the fact that they are normally coded by nuclear DNA in eukaryotes [48]. The syntheny *COX11COX3*, as well as that of *COX1* adjacent to *COX2* (Fig. 3A), may be considered a relic of bacterial operons that has been retained in the mtDNA of eukaryotes [48]. Are these cues pointing to the original *COX* operon(s) of proto-mitochondria?

To answer this question, we searched the available mtDNA genomes of unicellular eukaryotes. Mitochondrial DNA normally contains separate genes for *COX1*, *COX2* and *COX3* [48] except for aerobic ciliates, in which *COX3* appears to be missing [56,58]. However, we have recognized the sequence signatures of the *COX3* protein within the very long *COX1* of the hyphotrichous ciliate, *Oxytricha* [56] (Fig. 4). The *COX1* protein of another hyphotrich, *Monoeuplotes minuta* [58], appears to contain a split version of *COX3* having its initial two transmembrane helices separated from the subsequent 5-transmembrane helices domain by the major part of *COX1* (Fig. 4). The mtDNA of ciliates often contains split genes [56,58], but in this case an ancestral splitting of *COX3* must have been subsequently intermixed with the *COX1* gene. The alternative possibility would be that *COX3* splitting may reflect a fusion between precursors of mitochondrial *COX3*, since in *Monoeuplotes* it occurs within the region joining the two transmembrane domains which form the V-shaped structure of the protein [53,59-61].

In any case, the novel identification of a *COX3*-like protein embedded within the long *COX1* gene of unicellular eukaryotes (Fig. 4) suggests that the primordial form of such a chimaeric gene was a *COX1*-3 protein equivalent to those of bacterial *COX* operons of type a. By considering the gene order in ciliate mtDNA [56,58], we have deduced the possible sequence of the “minimal” *COX* operon that might have been present in the ancestors of ciliate mitochondria (Fig. 4C). The gene sequence closely resembles the core structure of a *COX* operon of type a - in the opposite order of transcription (cf. Fig. 3A and 4C) - and is clearly different from the sequence of *COX* operon type b (Figs. 3A and S3 in File S1). In view of the consensus that a single event of symbiosis originated all mitochondria [1-10] and considering the presence of *COX11COX3* syntheny in Jakobide mitochondria [48], a feature characteristic of *COX* operon type b (Figs. 3 and S3 in File S1), we surmise that proto-mitochondria possessed two different *COX* operons: one of type a and another of type b. Differential loss of either operon might further explain some differences in the mtDNA-coded proteins of ciliates and other unicellular

eukaryotes, as well as the different types of accessory subunits of their bioenergetic complexes [1]. Of note, phenetic analysis sustains the similarity between the *COX* gene sequence of protists and bacterial *COX* operon of type a-II, in particular those lacking an isolated *COX4* as in *Methylobacterium extorquens* PA1 (Table S3 in File S1).

**3.4 Evolution of the molecular architecture of COX3.** In the 3D structures available for cytochrome *c* oxidases, the initial two transmembrane helices of the 7- helices *COX3* protein that is present in mitochondria and bacterial *COX* operon type b (Fig. 3A) are involved in the binding to membrane phospholipids (PL) [53,59-61]. The tight binding of two specific forms of these PL to mitochondrial *COX3* appears to modulate the entry of oxygen into the binuclear catalytic centre of the enzyme [60]. PL-binding residues are present also in other parts of the *COX3* protein that are common to all its forms and tend to be conserved [59-62]. Here, we have evaluated the amino acid substitutions of the PL-binding sites in *COX3* (Table S4 in File S1) by translating residue variation into PL-binding strength (Fig. 5A). The results of this analysis are consistent with the phylogenetic trees of *COX3*, in which a major bifurcation separates the β- and γ-proteobacterial proteins from those of α-proteobacteria that are grouped together with mitochondrial *COX3* (Fig. 5B). The overall tree topology of *COX3* proteins thus matches that of *COX1* proteins, even if the internal branching of α-bacteria with the mitochondrial clade appears to be different (Fig. 5B cf. Fig. 3B).

Quantitative evaluation of the PL-binding strength further refines the evolutionary relationship among *COX3* proteins. First, it shows that the 5-helices form of the protein belonging to *COX* operon type a-II occupies an intermediate position between ancestral *COX1*-3 and the 7-transmembrane form of *COX3* (Fig. 5A). Secondly, it allows the comparison with the highly divergent sequence of ciliate *COX3* embedded within *COX1* (Fig. 4), which shows a PL-binding strength lying mid-way between that of *COX3* proteins of type a-II operon and those of other protists (Fig. 5A and Table S4 in File S1). Finally, bacterial *COX3* of *COX* operon type b has essentially the same PL-binding strength as that of mitochondrial *COX3* (Fig. 5A and Table S4 in File S1), thereby weakening the structural and phylogenetic significance of variable inter-group branching between α-bacterial and mitochondrial *COX3* sequences (Fig. 5B and data not shown).

**3.5. Phylogenetic distribution of COX operons.** To acquire further information for differentiating the pathways of mitochondrial evolution in Fig. 1B, we studied the phylogenetic distribution of diverse *COX* operons. The vast majority of Rhodobacterales, Sphingomonadales and Caulobacterales, together with unclassified α-proteobacteria such as *Micavibrio* and the SAR11 clade - which we include here under the generic label of ‘pan-Thalassic’- possess only *COX* operons of type b. This implies that *Roseobacter* and *Micavibrio* cannot be related to the ancestors of mitochondria, as for *Pelagibacter* and similar marine organisms.

On the other hand, 40 α-proteobacterial organisms and several β-proteobacteria combine *COX* operon type b with a type a-II operon, the phylogenetic distribution of which is similar to that of *ba3* oxidases [26] (Fig. 6A). Conversely, *COX* operon type a-I has the broadest phylogenetic distribution among all types of *COX*
A

<figure><img src="image_35.png" /></figure>

B

<figure><img src="image_36.png" /></figure>

**Figure 6.** Taxonomic distribution of bioenergetic systems in bacteria. A - Distribution of COX operon types in major families of α-proteobacteria. The frequency of each type of COX operon was normalised to the number of α-proteobacterial organisms with genomic data that are currently available (from NCBI resources http://www.ncbi.nlm.nih.gov/taxonomy/- accessed 14 March 2014) [50]. See Table S2 in File S1 for a detailed list of the taxonomic distribution of diverse COX operon types. The definition 'pan-Thalassic' collects together organisms of the SAR clade
with Magnetococcus, Pelagibacter and Micavibrio. **B.** -Distribution of fused proteins and N-metabolism elements along diverse bacterial lineages. Fused proteins were identified with the combined ressources of NCBI and the Protein Family website (PFAM 27.0 - http://pfam.sanger.ac.uk/[52]). Multiple forms of ISP were counted as >1 ISP. Taxa are arranged according to their approximate phylogenetic position considering also metabolic features (cf. Refs [5,31]). For each group, the frequency is normalized as in A. Eukaryotes (·) include amoebozoa, ciliates and heterokonts. N-metabolism encompasses: methane monooxygenase, ammonia monooxygenase, nitrite oxidoreductase, *Nirf* nitrite reductase and its homologues in COX operon type a-I (Fig. 3A), ammonia oxidation and anaerobic ammonia fermentation [30,32]. doi:10.1371/journal.pone.0096566.g006

operon, encompassing taxonomic groups beyond the *phylum* of proteobacteria such as Planctomycetes [50]. Indeed, the *Niff*-like gene cluster that is associated with this *COX* operon was originally discovered in ancient eubacteria including Planctomycetes [63]. Although the functional implications of the combination of a *Niff*-like operon with a *COX* gene cluster remain unknown, we are intrigued by the possibility that the overall gene sequence would produce a compact electron transport chain from quinol, or products of N metabolism, to oxygen [32,50]. Consequently, *COX* operon type a-I would represent the ultimate bioenergetic connection between cytochrome *c* oxidase and N metabolism, a fundamental concept in our approach to discern mitochondrial evolution (Fig. 1).

## 4. Phylogenetic distribution of N metabolism and fused proteins in bacteria and mitochondria

To explore the phylogenetic dimension of the connection between *COX* operons and elements of N metabolism, we studied the taxonomic distribution of *NiffD* and other key elements of the N cycle in conjunction with that of fused subunits of *aa*₃-type oxidases (Fig. 6B). Indeed, *COX* operon type a-I invariably contains *COX*2 fused with a *c*-type cytochrome (Figs. 3A, a fusion which is frequently present also in other *COX* operons (Fig. 3A and Fig. S3 in File S1). Fusion between catalytic subunits of bacterial heme-copper oxidases has been noted before [47,64], but considered a nuisance for phylogenetic analyses [64]. However, it constitutes a relic of ancestral bacteria adapted to harsh conditions in which the compact structure of bioenergetic systems would have been advantageous [47]. Since we have now shown that fusion between *COX* subunits is present also in the mitochondria of unicellular eukaryotes (Fig. 4) and fungi such as *Phaeosphaera* [57], we could consider them as potential relics of the evolutionary past of mitochondrial bioenergetics.

We therefore evaluated the frequency and phylogenetic distribution of fused *COX* subunits and also of the fused proteins that are present in the cytochrome *bc*₁ complex, the cytochrome *b* subunit of which has been previously reported to be fused with the cytochrome *c*₁ subunit in *Bradyrhizobium* [65]. We found the same fusion in all members of the Bradyrhizobiaceae family plus some Rhodospirillales (Fig. 6B), as well as in Planctomycetes [66]. *α*-proteobacteria show the highest frequency of fused cytochrome *b* among proteobacterial lineages, thereby suggesting that this type of protein was present before the separation of *β*- and *γ*-proteobacteria. Conversely, many more *β*-proteobacteria possess fused *COX*2 proteins than *α*-proteobacteria (Fig. 6B).

Within *α*-proteobacteria, the distribution of fused *COX* and cytochrome *b* proteins follows a bell-shape profile along the likely evolutionary sequence of the taxonomic groups (Fig. 6B, cf. [5]). Some Sphingomonadales and Caulobacterales have fused *COX* proteins without possessing bioenergetic elements of N-metabolism (Fig. 6B). Parasitic Rhizobiales, Rickettsiales and pan-Thalassic organisms lack both fused bioenergetic proteins and elements of N-metabolism, in contrast with amoebozoa, fungi and heterokonts (Fig. 6B cf. Table 1). The absence of the above characters in parasitic and pan-Thalassic organisms could derive from their highly streamlined genomes. However, the high frequency of fused

genes in other taxa does not correlate with genome size, since acetic acid bacteria, which have a comparatively small genome, show a higher frequency of fused *COX*2 proteins than, for instance, Rhodobacterales (Fig. 6). Our interpretation of the data presented in Fig. 6 is that fused bioenergetic proteins and elements of N metabolism are preserved together in phylogenetically ancient groups of *α*-proteobacteria, from which they have been passed to proto-mitochondria but then progressively lost along the differentiation of other *α*-proteobacteria. This implies that Methyloptrophs, Bradyrhizobiaceae and several Rhodospirillales would be the oldest extant organisms of the *α*-proteobacterial lineage, and consequently close to the distal progenitors of proto-mitochondria.

The phylogenetic distribution and similar genomic arrangement of fused bioenergetic proteins (Fig. 6) raises the question as to whether they may derive from events of Lateral Gene Transfer (LGT), for example with Planctomycetes [67]. However, detailed analysis of the molecular architecture of cytochrome *b* proteins (M. Degli Esposti, unpublished data) and the overall consistency of distance trees of fused proteins with established phylogenetic relationships (Fig. 3) indicate that LGT events have minimally contributed to the observed distribution of fused bioenergetic proteins and their diverse genomic clusters.

## 5. A complementary approach: the molecular evolution of nuclear encoded ISP

To complement the above analysis of mtDNA-encoded proteins of the *aa*₃-type oxidase, we next examined the molecular evolution of the “Rieske” iron sulfur subunit (ISP) of the cytochrome *bc*₁ complex. This ubiquitous redox protein is coded by the nuclear DNA and therefore does not suffer from the distortions due to the fast mutation rate of mtDNA-encoded proteins [16,37,48]. Its precursor form, once imported into mitochondria, matures within the intermembrane space where its catalytic core resides. After implementing structure-based alignments (Fig. S4 in File S1), we noted diverse insertions that are present in the catalytic core of ISP proteins from different lineages, which we have named CIMit - Conserved Indels vs. Mitochondria (Fig. 7 and Fig. S4 in File S1). CIMit3 is the most prominent of these insertions, lying at the surface of bacterial *bc*₁ complexes [68,69] with parallel inserts in the partner protein, cytochrome *b* [68–72]. This and other indels (according to the definition in Ref. [73]) seem to carry valuable phylogenetic information, enabling the resolution of relationships that are blurred in phylogenetic trees (cf. Figs. 7C and 8). For instance, only *Tistrella* ISP has no residues corresponding to the CIMit5 insertion among the proteins from Rhodospirillaceae (Fig. 7), while in distance trees these proteins appear to be equally close within a sister sub-branch of their mitochondrial homologues (Fig. 8).

*Methylocystis* sp. SC2 and a few other Rhizobiales have a second, longer ISP (ISP2) that resembles the proteins from acetic acid, *β*- and *γ*-proteobacteria, with which it clusters together in distance trees (Figs. 7, 8 and S4 in File S1). Contrary to the latter organisms, ISP2 is not present within the *petABC* operon of the *bc*₁ complex but in isolated gene clusters that have no common flanking genes (not shown). Hence, ISP2 may have arisen from gene duplication as reported for the *β*-proteobacterium, *Rubrivivax*
A

<table><thead><tr><th>WP</th><th>2020226654</th><th>PG</th><th>PGKVVV</th><th>RGKPVWIMRTRPEMIAALSGQD</th><th>KLADFNSKDLALPE</th><th>ALRNPGRSERQDLFVAGICT</th><th>130</th><th>Acidovorax sp. MR-87/2</th></tr></thead><tbody><tr><td>YP</td><td>001900760</td><td>59</td><td>PGKVVV</td><td>RGKPVWLLRTPDMLESLKLTND</td><td>EVADFKSDVPTMTKPDY</td><td>KNKETNSRRAEKDLLVVGICS</td><td>130</td><td>Ralstonia pickettii 12/2</td></tr><tr><td>NP</td><td>275043</td><td>59</td><td>AGLLTAR</td><td>KGKPIVNRNTDQQLKDLGKLNLL</td><td>ELTDFNSDAQEOP</td><td>YAKNETSIKPNILVLAIGICT</td><td>125</td><td>Neisseria meningitidis</td></tr><tr><td>WP</td><td>020564984</td><td>59</td><td>SCGLLVV</td><td>RGKPVWILNTPEVLATLQTLD</td><td>ELRDFLSEEISIQPS</td><td>YTKNFVRSIPEKFIVAIGICT</td><td>125</td><td>Methylosarcina fibrata</td></tr><tr><td>YP</td><td>006958287</td><td>73</td><td>ACGIVV</td><td>RGKPVWFRQRTPEMLKTLQDP</td><td>KLQDFRESFICQQPE</td><td>DATNWSRVSPDIGVMIGICT</td><td>141</td><td>Gluconobacter oxydans/1</td></tr><tr><td>YP</td><td>002277526</td><td>59</td><td>PGQIVV</td><td>HGSPVFITHRTPESLARLQEALA</td><td>ARLDFRSSGALQQP</td><td>YANWHRISKEPFGVVIGICT</td><td>139</td><td>Gluconacetobacter diazo/2</td></tr><tr><td>YP</td><td>010510616</td><td>62</td><td>PGQIVV</td><td>KGKPVFITHRTPESLAALQDAALT</td><td>RLGRDCQSNDRQQP</td><td>YARNWHRSLDFRGVVGICT</td><td>139</td><td>Gluconacetobacter_europa/2</td></tr><tr><td>CCD32085</td><td>59</td><td>PGQIVV</td><td>RGKLVPAIFRDPDAELKLDPVLL</td><td>ALAFADFDESVQQP</td><td>YARNWSLDTYAVLVGCT</td><td>127</td><td>Methylocystis sp. SC2/2</td></tr><tr><td>YP</td><td>577370</td><td>69</td><td>PGQIVV</td><td>RDHPIVILNRSDAALTKLQDPKLL</td><td>AQLSDFQSEQQPEQ</td><td>YANWHRSANPEYGFVIGICT</td><td>137</td><td>Nitrobacterium exto PA1</td></tr><tr><td>YP</td><td>019172466</td><td>68</td><td>PGQIVV</td><td>RGKPVFVIINRAADALKLNKPSLL</td><td>ARLDFRDSQPVQQPE</td><td>YARNWSRSSNQPYAQVLVGCT</td><td>136</td><td>Pseudomonas salicyl/2</td></tr><tr><td>YP</td><td>002282274</td><td>64</td><td>PGSLTVV</td><td>RGKPIFIRNRTPREEVKAADVPLA</td><td>DLKDFVARNANLPEAQ</td><td>GVDRVGSGKKDKENWIVMVGCT</td><td>135</td><td>Rhizobium leguminosarum</td></tr><tr><td>YP</td><td>0385295</td><td>64</td><td>PGSLTVV</td><td>RGKPIFIRNRNTDKEVEEAKAVALE</td><td>ELKDFVARNILPADAAE</td><td>ASLDRLDRGSEGAGKENWIIMVGCT</td><td>135</td><td>Sinorhizobium meliloti/1</td></tr><tr><td>YP</td><td>004610841</td><td>59</td><td>PGSLTVV</td><td>RGKPVVVRNRTEQEMKDEAVKLS</td><td>DLKDFTARNILPADAP</td><td>ATDANRTTFGEAWMVMGVCT</td><td>136</td><td>Mesorhizobium opportunistum</td></tr><tr><td>Rubsphaer 3D</td><td>61</td><td>EGIVV</td><td>RGKPVWILRTGELT</td><td>CLT</td><td>QLVDTNARNH</td><td>AGDAEAS</td><td>132</td><td>Rhodobacter sphaeroides</td></tr><tr><td>YP</td><td>004691057</td><td>59</td><td>PGQIVV</td><td>RGKPVFIRARTEEIAAQARATDLT</td><td>DLFQDLAQNAALGADA</td><td>ADENRALSREDCGVLVGMGICT</td><td>130</td><td>Rhoseobacter litoralis/2</td></tr><tr><td>YP</td><td>006951099</td><td>60</td><td>EGIVV</td><td>RGKPVFVHRTEAAIKSAEDVLS</td><td>AFAPTRVKGH</td><td>AFAPTRVKGHSHDQVLVGVGCT</td><td>109</td><td>Methylocystis sp. SC2/1</td></tr><tr><td>YP</td><td>001640007</td><td>59</td><td>PGQIVV</td><td>RGKLVFIRKLTEKEVTDKMAVPS</td><td>EMID</td><td>AFAPTRVKGHGDQVLVSYGNCT</td><td>118</td><td>Methylobacterium exto PA1</td></tr><tr><td>YP</td><td>002502576</td><td>68</td><td>EGIVV</td><td>RGKLVFIRVRLGSKIEADIAMKAVLS</td><td>DLLDF</td><td>APFQARVKEGHDQVLVTYGNCT</td><td>126</td><td>Methylobacterium nodulans</td></tr><tr><td>YP</td><td>009763700</td><td>59</td><td>PGQIVV</td><td>RGKLVFWRGKLIFIRHRTPEEIKAAEDVN</td><td>QADSARVKPGKAQWLIVYGCT</td><td>121</td><td>Microvirga</td></tr><tr><td>YP</td><td>782883</td><td>61</td><td>EGIVV</td><td>RGKQGPIFIHRTPKIEEAAQNADWK</td><td>SFRDF</td><td>QPDSDRKVAGHEQWLVLSAICT</td><td>120</td><td>Rhodopsedo_palu_BisA53/3</td></tr><tr><td>YP</td><td>578436</td><td>60</td><td>EGIVV</td><td>RGKPIFISHIRHTKKQIEDARNVNA</td><td>SLPDF</td><td>ASDQSRVKEGHDQVLVGVIGICT</td><td>119</td><td>Nitrobacter hamburgensis/1</td></tr><tr><td>YP</td><td>006590199</td><td>62</td><td>EGIVV</td><td>RGKPVFVHRTEAAIKSAEDVLS</td><td>ALPDF</td><td>EPDAKRVKQ</td><td>PEWLVVIGCT</td><td>120</td><td>Methylocystis sp. SC2/1</td></tr><tr><td>YP</td><td>009856367</td><td>60</td><td>EGIVV</td><td>RGKPVFVHRTEAAIEVANAVDS</td><td>ALKDF</td><td>ATDQSRVKQ</td><td>PEWLVVIGCT</td><td>120</td><td>Methylocystis sp. SC2/1</td></tr><tr><td>YP</td><td>01831301</td><td>59</td><td>EGIVV</td><td>RGKLVFIRHRTKEKEIDAAVPS</td><td>ELRDF</td><td>QTDSRVKQ</td><td>PEWLVVIGCT</td><td>116</td><td>Beijerinckia indica</td></tr><tr><td>YP</td><td>019459664</td><td>91</td><td>EGIVV</td><td>RGKPVFIRHRTPEEVKAAADVTPS</td><td>ALKDF</td><td>ATDSRTKPGKEPWLVVGVICT</td><td>151</td><td>Roseomonas sp. B-5</td></tr><tr><td>YP</td><td>002295952</td><td>69</td><td>EGIVV</td><td>RGKPVFVHRTEAAEIASAQKTDLG</td><td>SLIDF</td><td>QPDSDARKEGHEQWLIVAGCT</td><td>128</td><td>Rhodospirillum centenum/2</td></tr><tr><td>YP</td><td>007438995</td><td>73</td><td>EGIVV</td><td>RGKPVFVHRTEAAIEEAAQVFLS</td><td>DLRDF</td><td>QTDSQRVRL</td><td>PEWLVVGVCT</td><td>130</td><td>Acosporhizobium brasilense</td></tr><tr><td>YP</td><td>004985728</td><td>71</td><td>EGIVV</td><td>RGKPVFVHRTEAAIEEARTVLVN</td><td>ELRDF</td><td>AADDARVKK</td><td>PEWLVVGVCT</td><td>128</td><td>Acetobacter bacter AF-5844</td></tr><tr><td>YP</td><td>423451</td><td>66</td><td>PGQIVV</td><td>RGKPVFIRHREPAIDEAGKVALA</td><td>DLRDF</td><td>QADADRRAKK</td><td>PEWLLILGCT</td><td>123</td><td>Magnetospirillum magneticum</td></tr><tr><td>YP</td><td>009853370</td><td>65</td><td>PGQIVV</td><td>RGKPVFVHRTEIEANEADVN</td><td>ELRDF</td><td>QTDDEERVKK</td><td>PEWLVVAGCT</td><td>122</td><td>Caenispirillum salinarum/2</td></tr><tr><td>YP</td><td>006373746</td><td>68</td><td>EGIVV</td><td>RGKPVFIRHTEKEIEEARAVNA</td><td>DLRDF</td><td>QTDDEARVK</td><td>KEWLVVGVCT</td><td>122</td><td>Thalassospira profundimaris</td></tr><tr><td>XP</td><td>004356972</td><td>116</td><td>EGIVV</td><td>RGKPVFIRHTEARIMT</td><td>DMRDF</td><td>QDADRVRKE</td><td>PEWLVVGVCT</td><td>125</td><td>Tistrella mobilis</td></tr><tr><td>CIMit</td><td></td><td></td><td></td><td></td><td>helix 2</td><td></td><td>CIMit2</td><td>3a--3b</td><td>3-10H</td><td>CIMit3</td><td></td></tr></tbody></table>

<table><tbody><tr><td>NP</td><td>020226654</td><td>131</td><td>HGLCSPSAVAAAGTSNFSGVSEDWEGGGFFC</td><td>SGTDFLAGRVFKNPKAPTNLEIPHRFLSC</td><td>RVKDAE</td><td>DESA</td><td>201</td><td>Acidovorax sp. MR-87/2</td></tr><tr><td>YP</td><td>001900760</td><td>131</td><td>HGLCSPSGPFAG-ANVQ</td><td>LAADPGVFPCFGSTDFLAGRVFKNPKAPNQLDVPPYMFLS</td><td>LVKDAE</td><td>GEARA</td><td>202</td><td>Ralstonia pickettii 12/2</td></tr><tr><td>NP</td><td>275043</td><td>126</td><td>HGLCSPTRFTRDIAPADLG</td><td>ADWKGGFFCPCFGSKDFLAGRVYKGVPAPTNLVPPYKLS</td><td>TLV</td><td>AG</td><td>193</td><td>Neisseria meningitidis</td></tr><tr><td>YP</td><td>020929484</td><td>126</td><td>HGLCSPTRFPIAPADLG</td><td>DKWKGFFCPCFGSKDFLAGRVYKGVPAPTNLVPPYKLS</td><td>TLV</td><td>ESTNEAS</td><td>199</td><td>Neisseria meningitidis fibrata</td></tr><tr><td>YP</td><td>006958287</td><td>142</td><td>HGLCVPTFDAPTQ</td><td>AEPAGKYLPCFGSQFSDAGRAYRNAPAYNLPVPPVTMIS</td><td>TLV</td><td>ESKNDDP</td><td>218</td><td>Gluconobacter oxydans/1</td></tr><tr><td>YP</td><td>002277526</td><td>140</td><td>HGLCVPTYFAPDPATPIAN</td><td>WPGGYA-CPCFGSKDFLAGRVFTGAPAYNLPVPPYSMPF</td><td>TLV</td><td>QNFAGPSD</td><td>211</td><td>Gluconacetobacter diazo/2</td></tr><tr><td>YP</td><td>010510616</td><td>131</td><td>HGLCVPAYKLFEGQGG</td><td>GWNPGYA-CPCFGSKDFLAGRVFRGAPAYNLPVPPYSMPF</td><td>TLV</td><td>QNFAGD</td><td>211</td><td>Gluconacetobacter_europa/1</td></tr><tr><td>CCD32085</td><td>128</td><td>HGLCIPILYTPSFAGPPT</td><td>ADWGGFFCPCFGSKDFLAGRVYKGVPAPTNLVPPYKLS</td><td>TLV</td><td>ENPPGE</td><td>9</td><td>109</td><td>Methylocystis sp. SC2/2</td></tr><tr><td>YP</td><td>577370</td><td>138</td><td>HGLCIPLYYPSPSNANHWA</td><td>SDLGGYFCPCFGSKDFLAGRVSGFVAPNLPVPPYFVR</td><td>TLV</td><td>ENPSN</td><td>129</td><td>Nitrobacter hamburgensis/2</td></tr><tr><td>YP</td><td>019172466</td><td>137</td><td>HGLCIDEPOFAADFQ</td><td>RAWGGYFCPCFGSKDFLAGRVFKNVPAYNLPVPPYHFTSA</td><td>TLV</td><td>ENPSFV</td><td>215</td><td>Pseudaminobacter salicyl/2</td></tr><tr><td>YP</td><td>002282274</td><td>137</td><td>HGLCVPLG</td><td>AGEYGWFPCFGSKYDTAGRIRKG</td><td>FAPNQLIPTFSYSC</td><td>TLV</td><td>192</td><td>Rhizobium leguminosarum</td></tr><tr><td>YP</td><td>001900757</td><td>133</td><td>HGLCVLGV</td><td>SDF</td><td>FAPENLPIT</td><td>TLV</td><td>192</td><td>Minorhizobium meliloti/1</td></tr><tr><td>YP</td><td>004610841</td><td>131</td><td>HGLCIPLOG</td><td>EGDFGGFCPCFGSCYDTAGRIRKG</td><td>FAPENMAVPVFKFI</td><td>TLV</td><td>186</td><td>Mesorhizobium opportunistum/1</td></tr><tr><td>Rubsphaer 3D</td><td>133</td><td>HGLCIPLOG</td><td>SGDF</td><td>FAPENLPIT</td><td>TLV</td><td>AG</td><td>187</td><td>Rhodobacter sphaeroides</td></tr><tr><td>YP</td><td>009763700</td><td>118</td><td>HGLCVLGV</td><td>AGDFGGWFPCFGSKYDTAGRIRKG</td><td>FAPNLPVFTFSYSC</td><td>TLV</td><td>190</td><td>Rhoseobacter litoralis/2</td></tr><tr><td>YP</td><td>001753517</td><td>127</td><td>HGLCVPIG</td><td>QGNFEGWACPCFGSQFDAVRVRHG</td><td>FAPINLPIPPYFAFET</td><td>TLV</td><td>EGGKEA</td><td>189</td><td>Methylobacterium radio</td></tr><tr><td>YP</td><td>001640007</td><td>119</td><td>HGLCVPIG</td><td>SGNYEGWSPCFCFGSQFDAVRVRHG</td><td>FAPINLPIPPYFAFES</td><td>TLK</td><td>EGGRAV</td><td>189</td><td>Methylobacterium nodulans</td></tr><tr><td>YP</td><td>002502576</td><td>127</td><td>HGLCVPIG</td><td>QGDFFEGWACPCFGSQFDAVRVRHG</td><td>FAPINLPIPPYFAQFL</td><td>TLV</td><td>SGAAA</td><td>182</td><td>Microvirga</td></tr><tr><td>YP</td><td>009763700</td><td>122</td><td>HGLCVPLG</td><td>QGEYHGWFPCFGSFOTSGRVSG</td><td>FAPINLPIPPYFTFS</td><td>TLV</td><td>DEATA</td><td>178</td><td>Rhodopsedo_palu_BisA53/3</td></tr><tr><td>YP</td><td>782883</td><td>121</td><td>HGLCIPTEH</td><td>MGNYEGWFCPCFGSQDSSGRARL</td><td>FAPINLALVPYFEFL</td><td>TLV</td><td>TA</td><td>175</td><td>Nitrobacter hamburgensis/1</td></tr><tr><td>YP</td><td>578436</td><td>120</td><td>HGLCVPIAH</td><td>EGAYDGGFCPCFGSVDTSDGRIRGG</td><td>FAPINLPVPPYAVFSL</td><td>TLK</td><td>---</td><td>176</td><td>Methylocystis sp. SC2/1</td></tr><tr><td>YP</td><td>006590199</td><td>121</td><td>HGLCIPCTK</td><td>EGYDGGFCPCFGSVDTSDGRIRGG</td><td>FAPINLVPYFAFIAE</td><td>TLK</td><td>---</td><td>175</td><td>Methylocystis sp. SC2/1</td></tr><tr><td>YP</td><td>000264045</td><td>118</td><td>HGLCVPLG</td><td>EGYHGFFCPCFGSKYDTSDGRIRGG</td><td>FAPINLPVPYKFVSL</td><td>TLK</td><td>---</td><td>173</td><td>Methylocystis</td></tr><tr><td>YP</td><td>001831301</td><td>117</td><td>HGLCVPIG</td><td>EGQYEGWFPCFGSVDTSDGRIRGG</td><td>FAPINLNPAYRVFSD</td><td>TLK</td><td>---</td><td>172</td><td>Beijerinckia indica</td></tr><tr><td>YP</td><td>0019459664</td><td>152</td><td>HGLCVPLGQKPTDE</td><td>RGAYGGWFPCFGSVDTAGRIRKG</td><td>FAPINLVPVPAFTND</td><td>TLK</td><td>---</td><td>172</td><td>Roseomonas sp. B-5</td></tr><tr><td>YP</td><td>002299592</td><td>129</td><td>HGLCVPLGKRTSTD</td><td>RGDYGGWFPCFGSKYDTAARIRKG</td><td>FAPINLNAIDPYTFLDC</td><td>TLV</td><td>6</td><td>7-C</td><td>189</td><td>Rhodospirillum centenum/2</td></tr><tr><td>YP</td><td>007438995</td><td>131</td><td>HGLCVPLGKRTSTD</td><td>RGDYGGWFPCFGSKYDTAGRIRKG</td><td>FAPINLNAPEYEFRSD</td><td>TLV</td><td>6</td><td>7-C</td><td>191</td><td>Acetobacter bacter AF-5844</td></tr><tr><td>YP</td><td>004985728</td><td>129</td><td>HGLCVPLGKRTSTD</td><td>RGDYGGWFPCFGSKYDTAGRIRKG</td><td>FAPINLPVPQYAFTND</td><td>TLV</td><td>6</td><td>7-C</td><td>189</td><td>Acosporhizobium brasiliense</td></tr><tr><td>YP</td><td>423451</td><td>124</td><td>HGLCVPLGKRPADP</td><td>REGEGGWFPCFGSKYDTSDGRIRGG</td><td>FAPINLPVPYQFTSD</td><td>TLV</td><td>6</td><td>7-C</td><td>184</td><td>Magnetospirillum magneticum</td></tr><tr><td>YP</td><td>009542637</td><td>123</td><td>HGLCVPLGKPGEP</td><td>KGEMGYFCPCFGSKYDTSDGRIRGG</td><td>FAPINLPVPGYFIEC</td><td>TLV</td><td>6</td><td>7-C</td><td>183</td><td>Caenispirillum salinarum/2</td></tr><tr><td>YP</td><td>008898443</td><td>123</td><td>HGLCIPMCTAGET</td><td>RGDYGWFCPCFGSKYDTSDGRIRGG</td><td>FAPINLPVEYEFLTH</td><td>TLV</td><td>6</td><td>7-C</td><td>183</td><td>Thalassospira profundimaris</td></tr><tr><td>YP</td><td>006373746</td><td>126</td><td>HGLCVPLG</td><td>QGYDGYFCPCFGSKYDTSDGRIRGG</td><td>FAPINLNPAYEVFFD</td><td>TLV</td><td>6</td><td>7-C</td><td>181</td><td>Tistrella mobilis</td></tr><tr><td>XP</td><td>004356972</td><td>176</td><td>HGLCVLOG</td><td>QGEY</td><td>FAPENLPIT</td><td>TLV</td><td>6</td><td>7-C</td><td>235</td><td>Acanthamoeba castellanii</td></tr><tr><td>CIMit</td><td></td><td></td><td></td><td></td><td>CIMit5---</td><td></td><td></td><td></td><td></td><td>CIMit7</td><td></td></tr></tbody></table>

B

<figure><img src="image_37.png" /></figure>
A

<figure><img src="image_38.png" /></figure>

B

<figure><img src="image_39.png" /></figure>

**Figure 8.** Phylogenetic relationships between diverse forms of ISP. A – Distance tree encompassing proteobacteria and mitochondria. The tree was obtained as described in the legend of Fig. 3B using the alignment of Fig. 7A and two ISP proteins from the *b6f* complex as outgroup (top). The group containing bacterial ISP1 proteins together with their mitochondrial homologues is enclosed in the blue square to
highlight a likely ancestral duplication separating it from the group with ISP2. **B – Long distance phylogenetic relationships of bacterial ISP.**
The phylogenetic tree (maximal likelihood method) of ISP proteins was computed from the structure-based alignments in Fig. S4 in File S1. Th small
green circle indicates ancient nitrogen or methylotrophic metabolism [29–32] (Fig. 6B). The dashed green bracket indicates the paralogue proteins
belonging to the *b*<sub>ef</sub> complex. Other brackets indicate proteobacterial subdivisions and mitochondria as in A. Note how the bootstrap values are
much lower within the bottom branch containing mitochondrial ISP than in the upper branch containing ISP2.
doi:10.1371/journal.pone.0096566.g008

frequency of these characters than α-proteobacteria (Fig. 6B). However, some α-proteobacteria show a high frequency of fused proteins and elements of N metabolism (Fig. 6B), namely methylotrophs - encompassing the families of Methylocystaceae, Methylobacteraceae, Beijerinckiaceae and part of Hyphomicrobiaceae, as well as Bradyrhizobiaceae such as *Afipia felis* and *Rhodopseudomonas palustris* BisA53 [77] - several Acetobacteraceae and some Rhodospirillaceae. These organisms also have a wide range of ancestral characters such as type a COX operons and ISP2 (Table S2 in File S1and Fig. 8).

The information just discussed can be integrated with the timeline of bacterial evolution [31], which positions the separation of the β-lineage near the time at which oxygen levels dramatically increased, at least in the photic zone of marine environments and emerged land. The invention of the metabolic pathways of methane, ammonia and nitrite oxidation immediately followed,

allowing autothrophic ways of life which are now retained by a few
groups of proteobacteria [30]. These bacteria also possess the
largest variety of COX operons and molecular forms of their
catalytic subunits, as the result of multiple events of operon and
gene duplication. Some of these duplications are still evident in
extant organisms, as indicated by the doublet of COX3 proteins in
COX operon type a-III (Fig. 3A) and the presence of concatenated
COX operons in some genomes (Table S2 in File S1). Our
reconstruction of the molecular evolution of COX3 proteins and
their binding strength for oxygen-modulating phospholipids (Fig. 5)
seems to recapitulate a progressive adaptation to increasing levels
of O₂, which had to be gauged in terms of decreasing oxygen
affinity to maintain maximal efficiency of the oxidase reactions,
with minimal damage by radicals and potential suicidal reactions
[47,60,78]. We have also found multiple forms of other terminal
oxidases in methylotrophs and Rhodospirillales, in particular for

<figure><img src="image_40.png" /></figure>

**Figure 9. Possible progenitors for the bioenergetic evolution of mitochondria.** This diagram is modified from that in Fig. 1B to take into account the deduction that proto-mitochondria probably had two different types of COX operons (type a is labelled in dark olive background) and the evidence for multiple ISP forms. ISP2 is represented in a grey box while ISP1 in dark blue. Various steps of differential loss or acquisition via LGT are indicated for the possible pathways of evolution from extant or extinct α-proteobacteria into proto-mitochondria. By considering the complexities arisen from our data, pathway A in Fig. 1B stemming from *Beijerinckia* would require one loss and one acquisition, while pathway B would theoretically imply two losses and two acquisitions. However, we now exclude that this pathway may have contributed to the evolution of mitochondria (see text). Pathway C, sustained by most results presented here, bypasses the *Beijerinckia* subset with the combined loss of two bioenergetic systems and ISP2. Finally, pathway D would require the combined loss of three bioenergetic systems from organisms such as *Tistrella*, but of two systems plus ISP2 for *R. palustris* BisA53, which has already lost *bo*-type oxidase (Table S1 in File S1). The obvious possibility that yet undiscovered, or extinct bacteria may be among the originators of the proto-mitochondrion is considered, as indicated. Eventual loss of photosynthesis is not shown, but it would apply only to *Methylobacterium*, *R. palustris* and *Roseobacter* among the organisms shown. The grey vertical arrow on the left indicates the possible equivalence of COX operon type a with dual function (cytochrome *c* and ubiquinol) oxidases in some *Rhodobacterales*.
doi:10.1371/journal.pone.0096566.g009
the *bd*-type ubiquinol oxidase (Table S1 in File S1). The additional forms usually correspond to the Cyanide Insensitive Oxidase (CIO) [79], which has lower affinity for oxygen than classical *bd* oxidases [25].

We believe that the large increase in ambient oxygen that occurred during the evolution of primordial proteobacteria [31] was the driving force for the genomic expansion and diversification of oxygen-reacting enzymes. High levels of O₂ also led to the wide availability of nitrate and nitrite that can function as alternative terminal acceptors for electron transfer and bioenergy production [22,32]. This underlines the strong link between oxygen respiration and key elements of N metabolism that we have taken in consideration here. The separation of proto-mitochondria is estimated to have occurred when oxygen levels were still very low in the oceans [10,24], where most primordial life thrived. It is therefore plausible that the distal progenitors of mitochondria were related to organisms that had experimented with a wide variety of oxygen-reacting systems and thus retained great plasticity in their adaptation to micro-oxic or even anoxic environments, a trait that is partially retained in eukaryotes adapted to anaerobic environments [10]. With this conceptual framework in mind, we can now look back to the initial approach of our work (Fig. 1) and consider the most plausible pathways for mitochondrial evolution (Fig. 9).

Following the separation of the β- and γ-proteobacterial lineages, proto-mitochondria may have branched off along one of the pathways illustrated in Fig. 9. Pathways A and B are the same as in Fig. 1B, with the additional complexities that have emerged from the detailed analysis of COX operons and ISP proteins plus possible acquisitions via LGT. Pathway A, stemming from *Beijerinckia* (we now exclude *Micavibrio* for it lacks key elements of N metabolism, cf. Fig. 2), would require one loss (*bd* oxidase) plus one acquisition (*COX* operon type a-II), while pathways B would theoretically require two losses and two acquisitions of bioenergetic systems. However, our results indicate that mitochondrial evolution is unlikely to have followed pathway B, since the organisms from which it departs do not have key elements of N-metabolism that are present in some eukaryotes (Figs. 2 and 6B) nor a ISP comparable to that of eukaryotes (Figs. 7 and 8). Additional pathway C bypasses the *Beijerinckia* subset with the combined loss of two bioenergetic systems and ISP2, the latter being a facile evolutionary step for only six organisms have retained ISP2 (Figs 7 and 8). This pathway stems from methylotrophic bacteria such as *Methylocystis* and *Methylobacterium*. Indeed, the analysis of three different types of bioenergy-producing systems - cytosolic nitrate assimilation, mitochondria-encoded subunits of cytochrome *c* oxidase and nuclear-encoded ISP subunit of the cytochrome *bc*₁ complex – converges in indicating methylotrophs as the most likely relatives to proto-mitochondria. Moreover, by combining the analysis of nitrate metabolism (Fig. 2) with that of *COX* (Figs. 3–6) and ISP evolution (Figs. 7, 8 and S4 in File S1), only *Tistrella* [48] and *Rhodopseudomonas palustris* [6] remain among all the bacteria that have been previously proposed as possible ancestors of mitochondria (cf. Figs. 1B and Table S1 in File S1). We have thus considered also pathway D, which would require the combined loss of three bioenergetic systems from those possessed by *Tistrella* (Fig. 9). Finally, *Rhodopseudomonas palustris* BisA53 does not have the *bo*-type oxidase as other organisms of the same genus, but possesses a methanol dehydrogenase close to that of methylotrophs (Table 1). However, it still retains a photosynthetic system, the loss of which would add to the other steps required to resemble proto-mitochondria (Fig. 9). The obvious possibility that yet undiscovered, or extinct bacteria may be among the originators of the proto-mitochondrion is also considered in Fig. 9. Yet, these

unknown organisms would probably have the subsets of bioenergy systems shown in the top part of the diagram.

Taken all our results together, methylotrophic organisms emerge as the closest living models for mitochondrial ancestors. In perspective, our work provides new means for selecting bacterial organisms that are most suitable for experimentally evolving proto-mitochondria with mitochondria-depleted eukaryotic cells.

## Methods

To identify genes and their products with others currently present in National Center for Biotechnology Information (NCBI) resources, we have extensively used the program DELTABLAST, Domain Enhanced Lookup time Accelerated BLAST [80], integrated with hydropathy analysis conducted with in house algorithms [72] or the program WHAT (Web-based Hydropathy, Amphipathicity and Topology http://saier-144-21.ucsd.edu/barwhat.html [81]). Manually refined alignments of bioenergetic proteins were subjected to phylogenetic analysis with maximum likelihood algorithm and 100 bootstrap resamplings, using the program PhyML 3.0 and evolutionary models selected with Prottest3, as described earlier [21]. The results obtained with this rigorous method essentially matched those obtained with the recent options of DELTABLAST (cf. Fig. 8). The genomes of *Asaia platicody* and *Saccharibacter sp.* (EMBL accession: CBLX010000001/27 and CBLY010000001/09, respectively) were recently reported by Chouaia *et al* [22]. See Supporting Information for additional methods and procedures of gene recognition, operon classification (cf. [82]) and sequence analysis of proteins (cf. [41,52,83]).

## Supporting Information

**File S1 We enclose File S1 with Supporting Information containing a detailed account of the classification of bacterial COX operons (2 pages), 4 additional Figures and 4 additional Tables. Figure S1, Pathways for the bioenergetic evolution of a bacterial not leading to mitochondria.** The diagram shows the additional subsets of bioenergetic systems that are not shown in Fig. 1B, including those of *Asaia* and *Saccharibacter* (Table S1B in File S1). The asterisk* labels the same subset as in Fig. 1B (main text), but with fewer representative taxa. Underlined organisms are symbionts or pathogens. Each of the six bioenergetic systems presented in Fig. 1 was identified from its catalytic protein subunits and was considered functionally absent when one or more of these subunits were not found in their completeness, as indicated by the profile of their conserved domains (cf. [41]). The functional absence of a given system is represented by an empty square as in Fig. 1B. **Figure S2, Sequence analysis to identify the fusion of COX4 subunit with COX1 proteins. A.** Sequences of recognised or putative *COX4* were manually aligned to reference proteins having known 3D structure around the first transmembrane helix (TM1, highlighted in grey): subunit IV of *Thermus caa*₃ oxidase (accession: pdb|2YEV [54]) and subunit IV (*COX4_**-**pro_2 super family [cl06738]) of *Rhodobacter Sphaeroides aa*₃ oxidase (chain D, accession: pdb|1M57 [53]). *Residues in **bold** have positive scores (≥ 0) in the BLOSUM62 substitution matrix [83], those **yellow-highlighted** are identical with either reference protein, while those highlighted in purple are identical to *Janibacter COXIV* (accession: ZP_00994995) with scores ≥ 5 [83]. The total count of identities is also highlighted in yellow (tot) before the description of the protein on the right. It was used to identify other *COX4*-like proteins such as DUF983 (see Fig. 3A and the section entitled “classification of bacterial *COX* operons” in File S1). The
minimal count for deeming a protein as “COX4-like” was considered to be 10, but several COX1 proteins exhibited larger numbers of identities. The region of ciliate COX1 showing similarity with COX4 partially overlaps the last transmembrane region (TM12) of aligned COX1, which is well conserved among all available COX1 sequences from ciliates. However, the COX4-like region in bacterial COX1 and that of the pathogenic fungus *Zymospetoria* [55] lies outside the conserved domains of other COX1 proteins. Azospirillum_bras, *Azospirillum brasilense*, *Methylobac_extor*, *Methylobacterium extorquens*. **B** - This panel shows the alignment of COX4 subunits around the second transmembrane helix (TM2), the structure of which is known only for subunit IV of *Thermus caa*3 [54] that was used as the reference for aligning bacterial COX4 and mtDNA-encoded proteins. In **bold black** are the residues that are identical in the aligned position of at least two COX4 sequences, or are positive substitutions [83] across at least three aligned COX4 sequences; they are additionally **yellow-highlighted** when identical between at least one bacterial COX4 and one mtDNA-encoded protein (cf. A). In **bold dark blue** are the residues that are positive substitutions between bacterial COX4 and mtDNA-encoded proteins, while those in **bold light blue** are identical or positive substitutions among the aligned mtDNA-coded proteins. This colour labelling enhances the limited similarity between the sequences shown. **Figure S3, Gene sequence of additional COX operons in diverse bacteria.** The reference gene name for each cluster is indicated on the right of the figure. Symbols identify the same proteins as in Fig. 3A, with the addition of the small gray bar, protein related to nucleotide exchange factor EF-TS. These short proteins were recognised after alignment to the sequence with known 3D structure of Chain A, dimerization domain of Ef-Ts from *Thermus thermophilus* (Accession: pdb|1TFE|A) using a sequence analysis similar to that shown in Fig. S2 in File S1. Hypothetical steps in the evolution of COX operons are indicated. **Figure S4, Structure-based alignment of bacterial and mitochondrial “Rieske” ISP.** The protein sequences of various ISP of the *bc*1 complex were aligned following structures available from various sources matching the alignment gaps or insertions with the most refined 3D data [68–71]. The limits of secondary structures (alpha helices, highlighted in green, and beta sheets, highlighted in purple) were deduced from a consensus of the latest coordinates deposited in the NCBI databanks [68–71]. Common insertions and deletions (Indels [72]) between mitochondrial and bacterial sequences are consecutively labelled CIMit1-7 (cf. Fig. 7A). The C terminus of some sequences is truncated at the residue indicated by the numeral before the slash. Key residues for the iron-sulfur cluster, including Y165 influencing its redox potential [71], are in **bold**. Note that *Nitrospira*, *Nitrosomonas*, *Nitrosococcus* and *Methylocystis* are metabolically related by ammonia/methane autothropy. The organisms follow established phylogenetic distance from top to bottom according to the following taxonomic groups and species.
**Cyanobacteria:** Synechocystis (*b*of complex), *Synechocystis* sp. PCC 6803, 192 aa; **Nitrospirales:** Nitrospira, *Candidatus Nitrospira defluvii* [73], 183 aa; **ε-proteobacteria:** Epsilon, *Helicobacter pylori*, 167 aa; **Planctomycetes:** Kuenenia_2, *Candidatus Kuenenia stuttgartiensis* (in-operon Kuste3096 [66]), 173 aa; Schlesneria_2, *Schlesneira paludicula* DSM 18645 (accession: ZP_11092182), 189 aa. **γ-proteobacteria:** Nitrosoc, *Nitrosococcus watsonii* C-113, 201 aa; Frateuria, *Frateuria aurantia*, 201 aa; **β-proteobacteria:** Nitrosomonas, *Nitrosomonas europaea* ATCC 19718, 201 aa; Beta, *Neisseria meningitidis* MC58, 193 aa. **α-proteobacteria:** Methylocy_1 &_2, *Methylocystis* sp. SC2 [84], _1 in-operon, 176 aa, _2 in isolated gene cluster, 209 aa; *Methylobacter_r*, *Methylobacterium radiotolerans* JCM 2831, 189 aa; Nitrobacter,

*Nitrobacter hamburgensis* ISP2, 219 aa; *Gluc_dia*, *Gluconacetobacter diazotrophicus* PAI 5 (in isolated gene cluster), 221 aa; *Saccharib*, *Saccharibacter* sp. (Chouaia *et al.* [22]), 223 aa; *Glu_oxyd*, *Gluconobacter oxydans* H24, 218 aa; *Beijerinckia*, *Beijerinckia indica*, 172 aa; *Roseobacter* A2, *Roseobacter litoralis* petA2 in-operon, 186 aa; *Maricaulis_1*, *Maricaulis maris* in-operon, 207 aa; *Micavibrio*, *Micavibrio aeruginosavorus* [25], 185 aa; *Magnetococcus*, *Magnetococcus marinus* [76], 178 aa; *Rickettsia*, *Rickettsia felis*, 177 aa. **Mitochondria:** *Acanthamoeba*, *Acanthamoeba castellanii*, 235 aa; *S_cerevisiae*, *Saccharomyces cerevisiae*, mature 185 aa (3D structure available [85]); Chicken, *Gallus gallus*, mature 192 aa (3D structure available [68]). C-terminal extensions are highlighted in pale blue with some conserved residues in gray. **Table S1, Genomic distribution of bienergetic systems in α-proteobacteria. A.** The genomes of *ca.* 120 α-proteobacterial organisms were studied from the latest version of the genome NCBI database http://www.ncbi.nlm.nih.gov/genome/browse/- accessed on 14 March 2014, verifying also the completeness of genomic data (*). Reconstruction of the various bioenergetic systems (see text) was deduced by combining genomic information with biochemical and microbiological data. The organisms are listed following the left-right sequence in the model of Fig. 1B. Major types of *bd* oxidases are classified as *bd*-I or *CIO* [25,79]. The organisms directly shown in Fig. 1B are yellow highlighted and those proposed to be relatives of mitochondria are shown in italics with pertinent references (including [86,87]). Underlined organisms are symbionts or pathogens. **B.** This table lists the organisms that have been analysed but are not included in the model of Fig. 1B, also because they are in parallel paths of evolution with respect to the mitochondrial subset of bioenergetic systems. The organisms highlighted in pale yellow are shown in Fig. S1 in File S1, while other annotations are the same as in **A.** Complementary information is in Table S2 in File S1. **Table S2, Diverse gene clusters for aa₃ -type oxidase in α-proteobacteria.** The table lists the diverse types of COX operons (Fig. 3A). COX1 proteins recognised as *ba3-like_Oxidase_I* [cd01660] [41] are under the column *ba3^* and correspond to class B [26]. Concatenated operons are framed in blue and connected by a thick line. Incomplete (or ‘dead’ [82]) operons, indicated by the asterisk*, lack one or more of core subunits *ctaC-E* (Fig. 3A). Functional capacity of the oxidase has been deduced also from biochemical studies [88,89]. **Table S3, Phylogenetic distribution of the main characters of COX gene operons.** We constructed a matrix of 11 independent characters (indicated concisely on top of the columns) that could differentiate the gene sequence of COX subunits in the mitochondria of some protists from the gene sequence of bacterial COX operons. The cumulative phenetic analysis indicate that COX operon type a-II of methylotrophs and *Tistrella* (highlighted) share the largest number of characters with COX gene clusters of protist mitochondria (F. Comandatore and C. Bandi, unpublished). **Table S4, Conserved phospholipid binding sites in COX3 proteins.** The alignment in Fig. 4A was enlarged and the residues corresponding to the PL-binding sites and E90 (close to O2 entry in beef COX3 [60]) were considered conserved when producing positive substitutions [83] (bold amino acid symbols in white background). Other substitutions are highlighted in pale brown while identities are identified as **yes**. Organisms are abbreviated as in Fig. 4. (PDF)

## Acknowledgments

We thank Ed Berry (SUNY, Albany, USA), Marta d'Amora, Diego Sona, Alberto Diaspro and Roberto Cingolani (IIT, Italy) for helpful discussion and support.
## Author Contributions

Conceived and designed the experiments: MDE BC FC EC DS CB. Performed the experiments: MDE BC FC EC DS PMJL. Analyzed the data: MDE BC FC DS PMJL CB DD. Contributed reagents/materials/

## References

1. Gray MW (2012) Mitochondrial evolution. Cold Spring Harb Perspect Biol 4: a011403.

2. Lane N, Martin W (2010) The energetics of genome complexity. Nature 467: 929-934.

3. Margulis L (1996) Archaeal-eubacterial mergers in the origin of Eukarya: phylogenetic classification of life. Proc Natl Acad Sci U S A 93: 1071-1076.

4. Andersson SG, Karlberg O, Canbäck B, Kurland CG (2003) On the origin of mitochondria: a genomics perspective. Philos Trans R Soc Lond B Biol Sci 358: 165-177.

5. Williams KP, Sobral BW, Dickerman AW (2007) A robust species tree for the alphaproteobacteria. J Bacteriol 189: 4578-4586.

6. Abhishek A, Bavishi A, Bavishi A, Choudhary M (2011) Bacterial genome chimaerism and the origin of mitochondria. Can J Microbiol 57: 49-61.

7. Georgiades K, Raoult D (2011) The rhizome of *Reclinomonas americana*, *Homo sapiens*, *Pediculus humanus* and *Saccharomyces cerevisiae* mitochondria. Biol Direct 6: 55.

8. Thiergart T, Landan G, Schenk M, Dagan T, Martin WF (2012) An evolutionary network of genes present in the eukaryote common ancestor polls genomes on eukaryotic and mitochondrial origin. Genome Biol Evol 4: 466-485.

9. Gribaldo S, Poole AM, Daubin V, Fortere P, Brochier-Armanet C (2010) The origin of eukaryotes and their relationship with the Archaea: are we at a phylogenomic impasse? Nat Rev Microbiol 8: 743-752.

10. Müller M, Mentel M, van Hellemon JJ, Henze K, Woehle C, et al (2012) Biochemistry and evolution of anaerobic energy metabolism in eukaryotes. Microbiol Mol Biol Rev 76: 444-495.

11. Searcy DG (2003) Metabolic integration during the evolutionary origin of mitochondria. Cell Res 13: 229-238.

12. Gabaldón T, Huynen MA (2003) Reconstruction of the proto-mitochondrial metabolism. Science 301: 609.

13. Brindefalk B, Ettema TJG, Viklund J, Thollesson M, Andersson SGE (2011) A phylogeneticomic exploration of oceanic alphaproteobacteria reveals mitochondrial relatives unrelated to the SAR11 clade. PLOS ONE 6: e24457.

14. Georgiades K, Madoui M-A, Le P Robert C, Raoult D (2011) Phylogenomic analysis of *Odyssella thessalonicensis* fortifies the common origin of Rickettsiales, *Pelagibacter ubique* and *Reclinomonas americana* mitochondrion. PLOS ONE 6: e24857.

15. Rodriguez-Ezpeleta N, Embley TM (2012) The SAR11 group of alphaproteobacteria is not related to the origin of mitochondria. PLOS ONE 7: e30520.

16. Esser C, Ahmadinejad N, Wiegand C, Rotte C, Sebastiani F, et al (2004) A genome phylogeny for mitochondria among alpha-proteobacteria and a predominantly eubacterial ancestry of yeast nuclear genes. Mol Biol Evol 21: 1643-1660.

17. Yip C, Harbour ME, Jayawardena K, Fearnley IM, Sazanov LA (2011) Evolution of respiratory complex I: 'supernumerary' subunits are present in the alpha-proteobacterial enzyme. J Biol Chem 286: 5023-5033.

18. Clements A, Bursac D, Gatos X, Perry AJ, Cívircistov S, et al (2009) The reducible complexity of a mitochondrial molecular machine. Proc Natl Acad Sci U S A 106: 15791-15795.

19. Davidov Y, Huchon D, Koval SF, Jurkevitch E (2006) A new alphaproteobacterial clade of Bdellovibrio-like predators: implications for the mitochondrial endosymbiotic theory. Environ Microbiol 8: 2179-2188.

20. Atteia A, Adrait A, Brugière S, Tardif M, van Lis R, et al (2009) A proteomic survey of *Chlamydomonas reinhardtii* mitochondria sheds new light on the metabolic plasticity of the organelle and on the nature of the alpha-proteobacterial mitochondrial ancestor. Mol Biol Evol 26: 1533-1548.

21. Sassera D, Lo N, Epis S, D'Auria G, Montagna M, et al (2011) Phylogenomic evidence for the presence of a flagellum and cbb(3) oxidase in the free-living mitochondrial ancestor. Mol Biol Evol 28: 3285-3296.

22. Chouaia B, Gaiarsa S, Crotti E, Comandatore F, Degli Esposti M, et al (2014) Acetic acid bacteria genomes reveal functional traits for adaptation to life in insect guts. Genome Biol Evol, in press.

23. Kim SW, Fushinobu S, Zhou S, Wakagi T, Shoun H (2009) Eukaryotic nirK genes encoding copper-containing nitrite reductase: originating from the protomitochondrion? Appl Environ Microbiol 75: 2652-2658.

24. Johnston DT, Wolfe-Simon F, Pearson A, Knoll AH (2009). Anoxygenic photosynthesis modulated Proterozoic oxygen and sustained Earth's middle age. Proc Natl Acad Sci U S A 106: 16925-16929.

25. Borisov VB, Gennis RB, Hemp J, Verkhovsky MI (2011) The cytochrome bd respiratory oxygen reductases. Biochim Biophys Acta 1807: 1398-1413

26. Sousa FL, Alves RJ, Ribeiro MA, Pereira-Leal JB, Teixeira M, et al (2012) The superfamily of heme-copper oxygen reductases: types and evolutionary considerations. Biochim Biophys Acta 1817: 629-637

27. Ducluzeau AL, Ouchane S, Nitschke W (2008) The cbb3 oxidases are an ancient innovation of the domain bacteria. Mol Biol Evol 25: 1158-1166.

analysis tools: MDE CB FC CB DD. Wrote the paper: MDE PMJL CB DD. Conceived the work and wrote the bulk of the manuscript: MDE. Inspired various aspects of the work and participated to the writing and refining of the article: CB DD.

28. McLeod MP, Qin X, Karpathy SE, Gioia J, Highlander SK, et al (2004) Complete genome sequence of *Rickettsia typhi* and comparison with sequences of other rickettsiae. J Bacteriol 186: 5842-5855.

29. Takaya N (2009) Response to hypoxia, reduction of electron acceptors, and subsequent survival by filamentous fungi. Biosci Biotechnol Biochem 73: 1-8.

30. Vlaeminck SE, Hay AG, Maignien L, Verstraete W (2011) In quest of the nitrogen oxidizing prokaryotes of the early Earth. Environ Microbiol 13: 283-295.

31. Battistuzzi FU, Feijao A, Hedges SB (2004) A genomic timescale of prokaryote evolution: insights into the origin of methanogenesis, phototrophy, and the colonization of land. BMC Evol Biol 4: 44.

32. Simon J, Klotz MG (2013) Diversity and evolution of bioenergetic systems involved in microbial nitrogen compound transformations. Biochim Biophys Acta 1827: 114-135.

33. Tamas I, Dedysh SN, Liesack W, Stott MB, Alam M, et al (2010) Complete genome sequence of *Beijerinckia indica* subsp. indica. J Bacteriol 192: 4532-4533.

34. Shih PM, Matzke NJ (2013) Primary endosymbiosis events date to the later Proterozoic with cross-calibrated phylogenetic dating of duplicated ATPase proteins. Proc Natl Acad Sci U S A 110: 12355-12360.

35. Slot JC, Hibbett DS (2007) Horizontal transfer of a nitrate assimilation gene cluster and ecological transitions in fungi: a phylogenetic study. PLOS ONE 2: e1097.

36. Lin JT, Goldman BS, Stewart V (1994) The nasFEDCBA operon for nitrate and nitrite assimilation in *Klebsiella pneumoniae* M5aL. J Bacteriol 176: 2551-2559.

37. Lebrun E, Santini JM, Brugna M, Ducluzeau AL, Ouchane S et al (2006) The Rieske protein: a case study on the pitfalls of multiple sequence alignments and phylogenetic reconstruction. Mol Biol Evol 23: 1180-1191.

38. Moreno-Vivián C, Cabello P, Martínez-Luque M, Blasco R, Castillo F (1999) Prokaryotic nitrate reduction: molecular properties and functional distinction among bacterial nitrate reductases. J Bacteriol 181: 6573-6584.

39. Mohan SB, Schmid M, Jetten M, Cole J (2004) Detection and widespread distribution of the nrA gene encoding nitrite reduction to ammonia, a short circuit in the biological nitrogen cycle that competes with denitrification. FEMS Microbiol Ecol 49: 433-443.

40. Zhang Y, Rump S, Gladyshev VN (2011) Comparative Genomics and Evolution of Molybdenum Utilization. Coord Chem Rev 255: 1206-1217.

41. Marchler-Bauer A, Lu S, Anderson JB, Chitsaz F, Derbyshire MK, et al (2011) CDD: a Conserved Domain Database for the functional annotation of proteins. Nucleic Acids Res 39 (Database issue): D225-9.

42. Lee SJ, McCormick MS, Lippard SJ, Cho US (2013) Control of substrate access to the active site in methane monooxygenase. Nature 494: 380-384.

43. Chistoserdova L, Kalyuzhnaya MG, Lidstrom ME (2009) The expanding world of methylotrophic metabolism. Annu Rev Microbiol 63: 477-499.

44. Stewart JJ, Coyne KJ (2011) Analysis of raphidophyte assimilatory nitrate reductase reveals unique domain architecture incorporating a 2/2 hemoglobin. Plant Mol Biol 77: 565-575.

45. Lau E, Fisher MC, Steudler PA, Cavanaugh CM (2013) The methanol dehydrogenase gene, mxaF, as a functional and phylogenetic marker for proteobacterial methanotrophs in natural environments. POS ONE 8: e56993.

46. Liu X, Taber HW (1998) Catabolite regulation of the Bacillus subtilis ctaBCDEF gene cluster. J Bacteriol 180: 6154-6163.

47. Radzi Noor M, Soulimane T (2012) Bioenergetics at extreme temperature: *Thermus thermophilus* ba(3)- and caa(3)-type cytochrome c oxidases. Biochim Biophys Acta 1817: 638-649.

48. Burger G, Gray MW, Forget L, Lang BF (2013) Strikingly Bacteria-Like and Gene-Rich Mitochondrial Genomes throughout jakobid protists. Genome Evol 5: 418-438.

49. Hussain H, Grove J, Griffiths L, Busby S, Cole J (1994) A seven-gene operon essential for formate-dependent nitrite reduction to ammonia by enteric bacteria. Mol Microbiol 12: 153-163.

50. Refojo PN, Sousa FL, Teixeira M, Pereira MM (2010) The alternative complex III: a different architecture using known building systems. Biochim Biophys Acta 1797: 1869-1876.

51. Starkenburg SR, Larimer FW, Stein LY, Klotz MG, Chain PS, et al (2008) Complete genome sequence of *Nitrobacter hamburgensis* X14 and comparative genomic analysis of species within the genus *Nitrobacter*. Appl Environ Microbiol 74: 2852-2863.

52. Punta M, Coggill PC, Eberhardt RY, Mistry J, Tate J (2012). The Pfam protein families database. Nucleic Acids Res 40 (Database issue): D290-301.

53. Svensson-Ek M, Abramson J, Larsson G, Törnroth S, Brzezinski P, et al (2002) The X-ray crystal structures of wild-type and EQI-286 mutant cytochrome c oxidases from *Rhodobacter sphaeroides*. J Mol Biol 321: 329-339.

54. Lyons JA, Aragão D, Slattery O, Pisiakov AV, Soulimane T, et al (2012). Structural insights into electron transfer in caa3-type cytochrome oxidase. Nature 487: 514-518.
55. Torriani SF, Goodwin SB, Kema GH, Pangilinan JL, McDonald BA (2008) Intraspecific comparison and annotation of two complete mitochondrial genome sequences from the plant pathogenic fungus *Mycosphaerella graminicola*. Fungal Genet Biol 45: 628–637.

56. Swart EC, Bracht JR, Magrini V, Minx P, Chen X, et al (2013) The *Oxytricha trifallax* macronuclear genome: a complex eukaryotic genome with 16,000 tiny chromosomes. PLoS Biol 11: e1001473.

57. Hane JK, Lowe RG, Solomon PS, Tan KC, Schoch CL, et al (2007) Dothideomycete plant interactions illuminated by genome sequencing and EST analysis of the wheat pathogen *Stagonospora nodorum*. Plant Cell 19: 3347–3368.

58. de Graaf RM, van Alen TA, Dutilh BE, Kuiper JW, van Zoggel HJ, et al (2009) The mitochondrial genomes of the ciliates *Euplotes minuta* and *Euplotes crassus*. BMC Genomics 10: 514.

59. Tsukihara T, Aoyama H, Yamashita E, Tomizaki T, Yamaguchi H, et al (1996) The whole structure of the 13-subunit oxidized cytochrome c oxidase at 2.8 Å. Science 272: 1136–1144.

60. Shinzawa-Itoh K, Aoyama H, Muramoto K, Terada H, Kurauchi T, et al (2007) Structures and physiological roles of 13 integral lipids of bovine heart cytochrome c oxidase. EMBO J 26: 1713–1725.

61. Harrenga A, Michel H (1999) The cytochrome c oxidase from *Paracoccus denitrificans*: does not change the metal center ligation upon reduction. J Biol Chem 274: 33296–33299.

62. Qin L, Hiser C, Mulichak A, Garavito RM, Ferguson-Miller S (2006) Identification of conserved lipid/detergent-binding sites in a high-resolution structure of the membrane protein cytochrome c oxidase. Proc Natl Acad Sci U S A 103: 16117–16122.

63. Yanyushin MF, del Rosario MC, Brune DC, Blankenship RE (2005) New class of bacterial membrane oxidoreductases. Biochemistry 44: 10037–10045.

64. Brochier-Armanet C, Talla E, Gribaldo S (2009) The multiple evolutionary histories of dioxygen reductases: Implications for the origin and evolution of aerobic respiration. Mol Biol Evol 26: 285–297.

65. Thöny-Meyer L (1997) Biogenesis of respiratory cytochromes in bacteria. Microbiol Mol Biol Rev 61: 337–376.

66. Kartal B, de Almeida NM, Maalcke WJ, Op den Camp HJ, Jetten MS, et al (2013) How to make a living from anaerobic ammonium oxidation. FEMS Microbiol Rev 37: 428–461.

67. Budd A, Devos DP (2012) Evaluating the Evolutionary Origins of Unexpected Character Distributions within the Bacterial Planctomycetes-Verrucomicrobia-Chlamydiae Superphylum. Front Microbiol 3: 401.

68. Berry EA, Huang LS, Saechao LK, Pon NG, Valkova-Valchanova M, et al (2004) X-Ray Structure of *Rhodobacter Capsulatus* Cytochrome bc (1): Comparison with its Mitochondrial and Chloroplast Counterparts. Photosynth Res 81: 251–275.

69. Esser L, Elberry M, Zhou F, Yu CA, Yu L, et al (2008) Inhibitor-complexed structures of the cytochrome bc1 from the photosynthetic bacterium *Rhodobacter sphaeroides*. J Biol Chem 283: 2846–2857.

70. Zhang Z, Huang L, Shulmeister VM, Chi YI, Kim KK, et al (1998) Electron transfer by domain movement in cytochrome bc1. Nature 392: 677–684.

71. Kolling DJ, Brunzelle JS, Lhee S, Crofts AR, Nair SK (2007) Atomic resolution structures of rieske iron-sulfur protein: role of hydrogen bonds in tuning the redox potential of iron-sulfur clusters. Structure 15: 29–38.

72. Degli Esposti M, De Vries S, Crimi M, Ghelli A, Patarnello T, et al (1993). Mitochondrial cytochrome b: evolution and structure of the protein. Biochim Biophys Acta 1143: 243–271.

73. Valas RE, Bourne PE (2009) Structural analysis of polarizing indels: an emerging consensus on the root of the tree of life. Biol Direct 4: 30.

74. Ouchane S, Nitschke W, Bianco P, Vermeglio A, Astier C (2005) Multiple Rieske genes in prokaryotes: exchangeable Rieske subunits in the cytochrome bc-complex of *Rubrivivax gelatinosus*. Mol Microbiol 57: 261–275.

75. Lücker S, Wagner M, Maixner F, Pelletier E, Koch H, et al (2010) *A. Nitrospira* metagenome illuminates the physiology and evolution of globally important nitrite-oxidizing bacteria. Proc Natl Acad Sci U S A 107: 13479–13484.

76. Schübbe S, Williams TJ, Xie G, Kiss HE, Brettin TS, et al (2009) Complete genome sequence of the chemolithoautotrophic marine magnetotactic coccus strain MC-1. Appl Environ Microbiol 75: 4835–4852.

77. Simmons SS, Isokpehi RD, Brown SD, McAllister DL, Hall CC, et al (2011) Functional Annotation Analytics of *Rhodopseudomonas palustris* Genomes. Bioinform Biol Insights 5: 115–129.

78. Bratton MR, Pressler MA, Hosler JP (1999) Suicide inactivation of cytochrome c oxidase: catalytic turnover in the absence of subunit III alters the active site. Biochemistry 38: 16236–16245.

79. Cunningham L, Pitt M, Williams HD (1997) The *cioAB* genes from *Pseudomonas aeruginosa* code for a novel cyanide-insensitive terminal oxidase related to the cytochrome bd quinol oxidases. Mol Microbiol 24: 579–591.

80. Boratyn GM, Schäffer AA, Agarwala R, Altschul SF, Lipman DJ, et al (2012). Domain enhanced lookup time accelerated BLAST. Biol Direct 7: 12.

81. Cuff JA, Clamp ME, Siddiqui AS, Finlay M, Barton GJ (1998) Bioinformatics 14: 892–893.

82. Price MN, Arkin AP, Alm EJ (2006) The life-cycle of operons. PLoS Genet 2: e96.

83. Hung CL, Lee C, Lin CY, Chang CH, Chung YC, et al (2010) Feature amplified voting algorithm for functional analysis of protein superfamily. BMC Genomics 11 (Suppl 3): S14.

84. Dam B, Dam S, Kube M, Reinhardt R, Liesack W (2012) Complete genome sequence of *Methylozymis* sp. strain SC2, an aerobic methanotroph with high-affinity methane oxidation potential. J. Bacteriol 194: 6008–6009.

85. Lange C, Hunte C (2002) Crystal structure of the yeast cytochrome bc1 complex with its bound substrate cytochrome c. Proc Natl Acad Sci U S A 99: 2800–2805.

86. Yang D, Oyaizu Y, Oyaizu H, Olsen GJ, Woese CR (1985) Mitochondrial origins. Proc Natl Acad Sci U S A 82: 4443–4447.

87. Fitzpatrick DA, Creevey CJ, McInerney JO (2006) Genome phylogenies indicate a meaningful alpha-proteobacterial phylogeny and support a grouping of the mitochondria with the Rickettsiales. Mol Biol Evol 23: 74–85.

88. Sakurai K, Arai H, Ishii M, Igarashi Y (2011) Transcriptome response to different carbon sources in Acetobacter aceti. Microbiology 157 (Pt 3): 899–910.

89. Gómez-Manzo S, Chavez-Pacheco JL, Contreras-Zentella M, Sosa-Torres ME, Arreguin-Espinosa R, et al (2010) Molecular and catalytic properties of the aldehyde dehydrogenase of *Gluconacetobacter diazotrophicus*, a quinoheme protein containing pyrroloquinoline quinone, cytochrome b, and cytochrome c. J Bacteriol 192: 5718–5724.