C. O. , C. C. , and V. B. , This publication has been written with the support of the AgreenSkillsþ fellowship program that has received funding from the EU's Seventh Framework Programme under grant agreement N FP7-609398 (AgreenSkillsþ contract). We are grateful to the genotoul bioinformatics platform Toulouse Midi-Pyrenees (Bioinfo Genotoul) for providing help and/or computing and/or storage resources. The authors are grateful to the CBGP-HPC computational platform. The funders had no role in study design, AgreenSkillsþ fellowship program cofunded by the EU's Seventh Framework Programme (FP7-609398) to A.M.M., the Agropolis foundation/Labex Agro

A. Gü-ndü-z, E. Douglas, and A. E. , Symbiotic bacteria enable insect to use a nutritionally inadequate diet, Proc R Soc Lond B Biol Sci, vol.276, pp.987-991, 1658.

S. F. Altschul, Gapped BLAST and PSI-BLAST: a new generation of protein database search programs, Nucleic Acids Res, vol.25, issue.17, pp.3389-3402, 1997.

H. Anbutsu, Small genome symbiont underlies cuticle hardness in beetles, Proc Natl Acad Sci U S A, vol.114, issue.40, pp.8382-8391, 2017.

M. Aschner, Studies on the symbiosis of the body louse: I. Elimination of the symbionts by centrifugalisation of the eggs, Parasitology, vol.26, issue.03, pp.309-314, 1934.

A. Bankevich, SPAdes: a new genome assembly algorithm and its applications to single-cell sequencing, J Comput Biol, vol.19, issue.5, pp.455-477, 2012.

G. M. Bennett and N. A. Moran, Small, smaller, smallest: the origins and evolution of ancient dual symbioses in a phloem-feeding insect, 2013.

, Genome Biol Evol, vol.5, issue.9, pp.1675-1688

R. L. Blackman and V. F. Eastop, Aphids on the world's trees: an identification and information guide, CAB International, Natural History Museum, 1994.

G. M. Boratyn, Domain enhanced lookup time accelerated BLAST, Biol Direct, vol.7, p.12, 2012.

G. Bourque and P. A. Pevzner, Genome-scale evolution: reconstructing gene orders in the ancestral species, Genome Res, vol.12, issue.1, pp.26-36, 2002.

P. Buchner, Endosymbiose der Tiere mit Pflanzlichen Mikroorganismen. Basel: Birkh? auser, 1953.

G. R. Burke and N. A. Moran, Massive genomic decay in Serratia symbiotica, a recently evolved symbiont of aphids, Genome Biol Evol, vol.3, issue.0, pp.195-208, 2011.

G. R. Burke, B. B. Normark, C. Favret, and N. A. Moran, Evolution and diversity of facultative symbionts from the aphid subfamily Lachninae, Appl Environ Microbiol, vol.75, issue.16, pp.5328-5335, 2009.

C. Camacho, BLASTþ: architecture and applications, BMC Bioinformatics, vol.10, p.421, 2009.

H. Charles and H. Ishikawa, Physical and genetic map of the genome of Buchnera, the primary endosymbiont of the pea aphid Acyrthosiphon pisum, J Mol Evol, vol.48, issue.2, pp.142-150, 1999.

F. Chen, A. J. Mackey, J. K. Vermunt, and D. S. Roos, Assessing performance of orthology detection strategies applied to eukaryotic genomes, PLoS ONE, vol.2, issue.4, p.383, 2007.

R. A. Chong and N. A. Moran, Evolutionary loss and replacement of Buchnera, the obligate endosymbiont of aphids, ISME J, vol.12, issue.3, pp.898-908, 2018.

A. L. Clayton, A novel human-infection-derived bacterium provides insights into the evolutionary origins of mutualistic insectbacterial symbioses, PLoS Genet, vol.8, issue.11, p.1002990, 2012.

P. H. Degnan, A. B. Lazarus, and J. J. Wernegreen, Genome sequence of Blochmannia pennsylvanicus indicates parallel evolutionary trends among bacterial mutualists of insects, Genome Res, vol.15, issue.8, pp.1023-1033, 2005.

P. H. Degnan, Dynamics of genome evolution in facultative symbionts of aphids, Environ Microbiol, vol.12, issue.8, pp.2060-2069, 2010.

P. H. Degnan, H. Ochman, and N. A. Moran, Sequence conservation and functional constraint on intergenic spacers in reduced genomes of the obligate symbiont Buchnera, PLoS Genet, vol.7, issue.9, p.1002252, 2011.

P. H. Degnan, Y. Yu, N. Sisneros, R. A. Wing, and N. A. Moran, Hamiltonella defensa, genome evolution of protective bacterial endosymbiont from pathogenic ancestors, Proc Natl Acad Sci U S A, vol.106, issue.22, pp.9063-9068, 2009.

A. Douglas, Reproductive failure and the free amino acid pools in pea aphids (Acyrthosiphon pisum) lacking symbiotic bacteria, J Insect Physiol, vol.42, issue.3, pp.247-255, 1996.

R. C. Edgar, B. J. Haas, J. C. Clemente, C. Quince, and R. Knight, UCHIME improves sensitivity and speed of chimera detection, Bioinformatics, vol.27, issue.16, pp.2194-2200, 2011.

R. Gil, The genome sequence of Blochmannia floridanus: comparative analysis of reduced genomes, Proc Natl Acad Sci U S A, vol.100, issue.16, pp.9388-9393, 2003.

G. W. Griffiths and S. D. Beck, Ultrastructure of pea aphid mycetocytes: evidence for symbiote secretion, Cell Tissue Res, vol.159, issue.3, pp.351-367, 1975.

A. K. Hansen and N. A. Moran, Aphid genome expression reveals hostsymbiont cooperation in the production of amino acids, Proc Natl Acad Sci U S A, vol.108, issue.7, pp.2849-2854, 2011.

T. Hosokawa, Y. Kikuchi, N. Nikoh, M. Shimada, and T. Fukatsu, Strict hostsymbiont cospeciation and reductive genome evolution in insect gut bacteria, PLoS Biol, vol.4, issue.10, p.337, 2006.

C. Y. Huang, Z. L. Sabree, and N. A. Moran, Genome sequence of Blattabacterium sp. strain BGIGA, Endosymbiont of the Blaberus giganteus Cockroach, J Bacteriol, vol.194, issue.16, pp.4450-4451, 2012.

F. Husn-ik, C. , T. , H. , and V. , Multiple origins of endosymbiosis within the Enterobacteriaceae (c-Proteobacteria): convergence of complex phylogenetic approaches, BMC Biol, vol.9, issue.1, p.87, 2011.

F. Husnik and J. P. Mccutcheon, Repeated replacement of an intrabacterial symbiont in the tripartite nested mealybug symbiosis, Proc Natl Acad Sci U S A, vol.113, issue.37, pp.5416-5424, 2016.

E. Jousselin, Assessment of a 16S rRNA amplicon Illumina sequencing procedure for studying the microbiome of a symbiontrich aphid genus, Mol Ecol Resour, vol.16, issue.3, pp.628-640, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01449134

S. Kambhampati, A. Alleman, and Y. Park, Complete genome sequence of the endosymbiont Blattabacterium from the cockroach Nauphoeta cinerea (Blattodea: blaberidae), Genomics, vol.102, issue.5-6, pp.479-483, 2013.

K. Katoh and D. M. Standley, MAFFT Multiple Sequence Alignment Software Version 7: improvements in performance and usability, Mol Biol Evol, vol.30, issue.4, pp.772-780, 2013.

A. Klein, A novel intracellular mutualistic bacterium in the invasive ant Cardiocondyla obscurior, ISME J, vol.10, issue.2, pp.376-388, 2016.

R. Koga and N. A. Moran, Swapping symbionts in spittlebugs: evolutionary replacement of a reduced genome symbiont, ISME J, vol.8, issue.6, pp.1237-1246, 2014.

R. Koga, T. Tsuchida, and T. Fukatsu, Changing partners in an obligate symbiosis: a facultative endosymbiont can compensate for loss of the essential endosymbiont Buchnera in an aphid, Proc R Soc Lond B Biol Sci, vol.270, pp.2543-2550, 1533.

J. J. Kozich, S. L. Westcott, N. T. Baxter, S. K. Highlander, and P. D. Schloss, Development of a dual-index sequencing strategy and curation pipeline for analyzing amplicon sequence data on the MiSeq Illumina Sequencing Platform, Appl Environ Microbiol, vol.79, issue.17, pp.5112-5120, 2013.

A. Lamelas, Serratia symbiotica from the aphid Cinara cedri: a missing link from facultative to obligate insect endosymbiont, PLoS Genet, vol.7, issue.11, p.1002357, 2011.

A. Lamelas, M. J. Gosalbes, A. Moya, and A. Latorre, New clues about the evolutionary history of metabolic losses in bacterial endosymbionts, provided by the genome of Buchnera aphidicola from the aphid Cinara tujafilina, Appl Environ Microbiol, vol.77, issue.13, pp.4446-4454, 2011.

A. Lamelas, Candidatus Serratia symbiotica" in Aphid Species of the Subfamily Lachninae, Appl Environ Microbiol, vol.74, issue.13, pp.4236-4240, 2008.

N. Lartillot, T. Lepage, and S. Blanquart, PhyloBayes 3: a Bayesian software package for phylogenetic reconstruction and molecular dating, Bioinformatics, vol.25, issue.17, pp.2286-2288, 2009.

D. Laslett and B. Canback, ARAGORN, a program to detect tRNA genes and tmRNA genes in nucleotide sequences, Nucleic Acids Res, vol.32, issue.1, pp.11-16, 2004.

A. Latorre and A. Manzano-mar-in, Dissecting genome reduction and trait loss in insect endosymbionts, Ann N Y Acad Sci, vol.1389, issue.1, pp.52-75, 2017.

S. Q. Le and O. Gascuel, An improved general amino acid replacement matrix, Mol Biol Evol, vol.25, issue.7, pp.1307-1320, 2008.
URL : https://hal.archives-ouvertes.fr/lirmm-00324106

L. Li, C. J. Stoeckert, and D. S. Roos, OrthoMCL: identification of ortholog groups for eukaryotic genomes, Genome Res, vol.13, issue.9, pp.2178-2189, 2003.

M. J. L-opez-s-anchez, Evolutionary convergence and nitrogen metabolism in Blattabacterium strain Bge, primary endosymbiont of the cockroach Blattella germanica, PLoS Genet, vol.5, issue.11, p.1000721, 2009.

T. M. Lowe and P. P. Chan, tRNAscan-SE On-line: integrating search and context for analysis of transfer RNA genes, Nucleic Acids Res, vol.44, issue.W1, pp.54-57, 2016.

. Manzano-mar-in-a and A. Latorre, Settling Down: the Genome of Serratia symbiotica from the Aphid Cinara tujafilina Zooms in on the process of accommodation to a cooperative intracellular life, Genome Biol Evol, vol.6, issue.7, pp.1683-1698, 2014.

A. Manzano-mar-in and A. Latorre, Snapshots of a shrinking partner: genome reduction in Serratia symbiotica, Sci Rep, vol.6, p.32590, 2016.

A. Manzano-mar-in, A. Oceguera-figueroa, A. Latorre, J. Enez-garc-ia, L. F. Moya et al., Solving a bloody mess: b-vitamin independent metabolic convergence among gammaproteobacterial obligate endosymbionts from blood-feeding arthropods and the Leech Haementeria officinalis, Genome Biol Evol, vol.7, issue.10, pp.2871-2884, 2015.

A. Manzano-mar-in, J. C. Simon, and A. Latorre, Reinventing the wheel and making it round again: evolutionary convergence in Buchnera -Serratia symbiotic Consortia between the distantly related Lachninae Aphids Tuberolachnus salignus and Cinara cedri, Genome Biol Evol, vol.8, issue.5, pp.1440-1458, 2016.

A. Manzano-mar-in, G. Szab-o, J. C. Simon, M. Horn, and A. Latorre, Happens in the best of subfamilies: establishment and repeated replacements of co-obligate secondary endosymbionts within Lachninae aphids, Environ Microbiol, vol.19, issue.1, pp.393-408, 2017.

M. G. Marinus, DNA mismatch repair. EcoSal Plus, vol.5, issue.1, 2012.

J. P. Mccutcheon and N. A. Moran, Functional convergence in reduced genomes of bacterial symbionts spanning 200 million years of evolution, Genome Biol Evol, vol.2, pp.708-718, 2010.

J. P. Mccutcheon and N. A. Moran, Extreme genome reduction in symbiotic bacteria, Nat Rev Microbiol, vol.10, issue.1, pp.13-26, 2011.

A. S. Meseguer, Buchnera has changed flatmate but the repeated replacement of co-obligate symbionts is not associated with the ecological expansions of their aphid hosts, Mol Ecol, vol.26, issue.8, pp.2363-2378, 2017.
URL : https://hal.archives-ouvertes.fr/hal-02623952

T. Mittler, Some effects on the aphid Myzus persicae of ingesting antibiotics incorporated into artificial diets, J Insect Physiol, vol.17, issue.7, pp.1333-1347, 1971.

O. Mizrahi-man, E. R. Davenport, and Y. Gilad, Taxonomic classification of bacterial 16S rRNA genes using short sequencing reads: evaluation of effective study designs, PLoS One, vol.8, issue.1, p.53608, 2013.

N. A. Moran, Accelerated evolution and Muller's rachet in endosymbiotic bacteria, Proc Natl Acad Sci U S A, vol.93, issue.7, pp.2873-2878, 1996.

N. A. Moran and G. M. Bennett, The tiniest tiny genomes, Annu Rev Microbiol, vol.68, pp.195-215, 2014.

N. A. Moran, H. E. Dunbar, and J. L. Wilcox, Regulation of transcription in a reduced bacterial genome: nutrient-provisioning genes of the obligate symbiont Buchnera aphidicola, J Bacteriol, vol.187, issue.12, pp.4229-4237, 2005.

N. A. Moran, J. P. Mccutcheon, and A. Nakabachi, Genomics and evolution of heritable bacterial symbionts, Annu Rev Genet, vol.42, pp.165-190, 2008.

N. A. Moran and G. R. Plague, Genomic changes following host restriction in bacteria, Curr Opin Genet Dev, vol.14, issue.6, pp.627-633, 2004.

M. A. Munson, P. Baumann, and M. G. Kinsey, Buchnera gen.nov. and Buchnera aphidicola sp. nov., a Taxon Consisting of the Mycetocyte-Associated, Primary Endosymbionts of Aphids, Int J Syst Bacteriol, vol.41, issue.4, pp.566-568, 1991.

A. Nakabachi and H. Ishikawa, Provision of riboflavin to the host aphid, Acyrthosiphon pisum, by endosymbiotic bacteria, Buchnera. J Insect Physiol, vol.45, issue.1, pp.1-6, 1999.

E. P. Nawrocki, Rfam 12.0: updates to the RNA families database, Nucleic Acids Res, vol.43, pp.130-137, 2015.

E. P. Nawrocki and S. R. Eddy, Infernal 1.1: 100-fold faster RNA homology searches, Bioinformatics, vol.29, issue.22, pp.2933-2935, 2013.

N. Nikoh, Evolutionary origin of insect-Wolbachia nutritional mutualism, Proc Natl Acad Sci U S A, vol.111, issue.28, pp.10257-10262, 2014.

G. Nogge, Sterility in tsetse flies (Glossina morsitans Westwood) caused by loss of symbionts, Experientia, vol.32, issue.8, pp.995-996, 1976.

G. Nogge, Significance of symbionts for the maintenance of an optimal nutritional state for successful reproduction in haematophagous arthropods, Parasitology, vol.82, issue.4, pp.101-104, 1981.

. Nov-akov-a-e, Reconstructing the phylogeny of aphids (Hemiptera: aphididae) using DNA of the obligate symbiont Buchnera aphidicola, Mol Phylogenet Evol, vol.68, issue.1, pp.42-54, 2013.

K. F. Oakeson, Genome degeneration and adaptation in a nascent stage of symbiosis, Genome Biol Evol, vol.6, issue.1, pp.76-93, 2014.
URL : https://hal.archives-ouvertes.fr/hal-01449146

C. Ohtaka and H. Ishikawa, Effects of heat treatment on the symbiotic system of an aphid mycetocyte, Symbiosis, vol.11, pp.19-30, 1991.

K. Okonechnikov, O. Golosova, and M. Fursov, Unipro UGENE: a unified bioinformatics toolkit, Bioinformatics, vol.28, issue.8, pp.1166-1167, 2012.

R. Patiño-navarrete, A. Moya, A. Latorre, P. , and J. , Comparative genomics of Blattabacterium cuenoti: the Frozen Legacy of an Ancient Endosymbiont Genome, Genome Biol Evol, vol.5, issue.2, pp.351-361, 2013.

V. P-erez-brocal, A small microbial genome: the end of a long symbiotic relationship?, Science, vol.314, issue.5797, pp.312-313, 2006.

H. Philippe and B. Roure, Difficult phylogenetic questions: more data, maybe; better methods, certainly, BMC Biol, vol.9, issue.1, p.91, 2011.

A. Poliakov, Large-scale label-free quantitative proteomics of the pea aphid-Buchnera symbiosis, Mol Cell Proteomics, vol.10, issue.6, 2011.

C. Quast, The SILVA ribosomal RNA gene database project: improved data processing and web-based tools, Nucleic Acids Res. 41(Database issue, pp.590-596, 2013.

R. Rio, Insight into the transmission biology and speciesspecific functional capabilities of Tsetse (Diptera: glossinidae) obligate symbiont Wigglesworthia, mBio, vol.3, issue.1, pp.240-00211, 2012.

F. Ronquist, MrBayes 3.2: efficient Bayesian phylogenetic inference and model choice across a large model space, Syst Biol, vol.61, issue.3, pp.539-542, 2012.

C. W. Russell, S. Bouvaine, P. D. Newell, and A. E. Douglas, Shared metabolic pathways in a coevolved insect-bacterial symbiosis, Appl Environ Microbiol, vol.79, p.6117, 2013.

C. W. Russell, Matching the supply of bacterial nutrients to the nutritional demand of the animal host, Proc R Soc Lond B Biol Sci, vol.281, p.20141163, 1791.

Z. L. Sabree, S. Kambhampati, and N. A. Moran, Nitrogen recycling and nutritional provisioning by Blattabacterium, the cockroach endosymbiont, Proc Natl Acad Sci U S A, vol.106, pp.19521-19526, 2009.

L. Sacchi, A. Grigolo, G. Biscaldi, and U. Laudani, Effects of heat treatment on the symbiotic system of Blattoidea: morphofunctional alterations of bacteriocytes, Boll Zool, vol.60, issue.3, pp.271-279, 1993.

J. Sandstrom and N. Moran, How nutritionally imbalanced is phloem sap for aphids, Entomol Exp Appl, vol.91, issue.1, pp.203-210, 1999.

P. D. Schloss and S. L. Westcott, Assessing and improving methods used in operational taxonomic unit-based approaches for 16S rRNA gene sequence analysis, Appl Environ Microbiol, vol.77, issue.10, pp.3219-3226, 2011.

R. Schmieder and R. Edwards, Quality control and preprocessing of metagenomic datasets, Bioinformatics, vol.27, issue.6, pp.863-864, 2011.

S. Shigenobu, H. Watanabe, M. Hattori, Y. Sakaki, and H. Ishikawa, Genome sequence of the endocellular bacterial symbiont of aphids Buchnera sp, Nature, vol.407, issue.6800, pp.81-86, 2000.

B. E. Suzek, M. D. Ermolaeva, M. Schreiber, and S. L. Salzberg, A probabilistic method for identifying start codons in bacterial genomes, Bioinformatics, vol.17, issue.12, pp.1123-1130, 2001.

G. Szab-o, Convergent patterns in the evolution of mealybug symbioses involving different intrabacterial symbionts, ISME J, vol.11, issue.3, pp.715-726, 2017.

G. Talavera and J. Castresana, Improvement of phylogenies after removing divergent and ambiguously aligned blocks from protein sequence alignments, Syst Biol, vol.56, issue.4, pp.564-577, 2007.

I. Tamas, 50 million years of genomic stasis in endosymbiotic bacteria, Science, vol.296, issue.5577, pp.2376-2379, 2002.

G. Tokuda, Maintenance of essential amino acid synthesis pathways in the Blattabacterium cuenoti symbiont of a woodfeeding cockroach, Biol Lett, vol.9, issue.3, p.20121153, 2013.

G. H. Van-domselaar, BASys: a web server for automated bacterial genome annotation, Nucleic Acids Res, vol.33, pp.455-459, 2005.

R. Van-ham, Reductive genome evolution in Buchnera aphidicola, Proc Natl Acad Sci U S A, vol.100, issue.2, pp.581-586, 2003.

K. J. Vogel and N. A. Moran, Functional and evolutionary analysis of the genome of an obligate fungal symbiont, Genome Biol Evol, vol.5, issue.5, pp.891-904, 2013.

I. M. Wallace, O. O'sullivan, D. G. Higgins, and C. Notredame, M-Coffee: combining multiple sequence alignment methods with T-Coffee, Nucleic Acids Res, vol.34, issue.6, pp.1692-1699, 2006.

Q. Wang, G. M. Garrity, J. M. Tiedje, and J. R. Cole, Naïve Bayesian classifier for rapid assignment of rRNA sequences into the new bacterial taxonomy, Appl Environ Microbiol, vol.73, issue.16, pp.5261-5267, 2007.

L. E. Williams and J. J. Wernegreen, Genome evolution in an ancient bacteria-ant symbiosis: parallel gene loss among Blochmannia spanning the origin of the ant tribe Camponotini, PeerJ, vol.3, p.881, 2015.

H. Ziegler, Nature of Transported Substances, Encyclopedia of plant physiology, vol.1, pp.59-100, 1975.