E. P. Denise, . S. Rocha-;-sophie, E. P. Abby, and . Rocha, Investigation: Rémi Denise

S. S. Abby and E. P. Rocha, Writing -original draft: Rémi Denise

S. S. Writing--review-&-editing:-rémi-denise, E. P. Abby, and . Rocha, References 1. Gould SJ, Vrba ES. Exaptation-a Missing Term in the Science of Form, Paleobiology, vol.8, issue.1, pp.4-15, 1982.

C. Pal, B. Papp, and M. J. Lercher, An integrated view of protein evolution, Nat Rev Genet, vol.7, p.16619049, 2006.

F. Jacob, Evolution and tinkering, Science, vol.196, issue.4295, p.860134, 1977.

H. Ochman, J. G. Lawrence, and E. A. Groisman, Lateral gene transfer and the nature of bacterial innovation, Nature, vol.405, issue.6784, p.10830951, 2000.

J. P. Gogarten and J. P. Townsend, Horizontal gene transfer, genome innovation and evolution, Nat Rev Microbiol, vol.3, issue.9, p.16138096, 2005.

R. Jain, M. C. Rivera, J. E. Moore, and J. A. Lake, Horizontal gene transfer accelerates genome innovation and evolution, Mol Biol Evol, vol.20, issue.10, p.12777514, 2003.

B. Szappanos, J. Fritzemeier, B. Csorgo, V. Lazar, X. Lu et al., Adaptive evolution of complex innovations through stepwise metabolic niche expansion, Nat Commun, vol.7, p.27197754, 2016.

S. S. Abby and E. P. Rocha, The non-flagellar type III secretion system evolved from the bacterial flagellum and diversified into host-cell adapted systems, PLoS Genet, vol.8, issue.9, p.23028376, 2012.
URL : https://hal.archives-ouvertes.fr/pasteur-01374947

J. Guglielmini, F. De-la-cruz, and E. P. Rocha, Evolution of conjugation and type IV secretion systems, Mol Biol Evol, vol.30, issue.2, p.22977114, 2013.
URL : https://hal.archives-ouvertes.fr/pasteur-01374951

L. G. Pell, V. Kanelis, L. W. Donaldson, P. L. Howell, and A. R. Davidson, The phage lambda major tail protein structure reveals a common evolution for long-tailed phages and the type VI bacterial secretion system, Proc Natl Acad Sci U S A, vol.106, issue.11, p.19251647, 2009.

P. G. Leiman, M. Basler, U. A. Ramagopal, J. B. Bonanno, J. M. Sauder et al., Type VI secretion apparatus and phage tail-associated protein complexes share a common evolutionary origin, Proc Natl Acad Sci U S A, vol.106, issue.11, p.19251641, 2009.

C. R. Peabody, Y. J. Chung, M. R. Yen, D. Vidal-ingigliardi, A. P. Pugsley et al., Type II protein secretion and its relationship to bacterial type IV pili and archaeal flagella, Microbiology, vol.149, p.14600218, 2003.

K. F. Jarrell and S. V. Albers, The archaellum: an old motility structure with a new name, Trends Microbiol, vol.20, issue.7, p.22613456, 2012.

J. L. Berry and V. Pelicic, Exceptionally widespread nanomachines composed of type IV pilins: the prokaryotic Swiss Army knives, FEMS Microbiol Rev, vol.39, issue.1, p.25793961, 2015.

V. Gold and M. Kudryashev, Recent progress in structure and dynamics of dual-membrane-spanning bacterial nanomachines, Curr Opin Struct Biol, vol.39, p.26995496, 2016.

K. V. Korotkov, M. Sandkvist, and W. G. Hol, The type II secretion system: biogenesis, molecular architecture and mechanism, Nat Rev Microbiol, vol.10, issue.5, p.22466878, 2012.

S. S. Abby, J. Cury, J. Guglielmini, N. B. Touchon, M. Rocha et al., Identification of protein secretion systems in bacterial genomes, Sci Rep, vol.6, p.26979785, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01677379

P. J. Planet, S. C. Kachlany, R. Desalle, and D. H. Figurski, Phylogeny of genes for secretion NTPases: identification of the widespread tadA subfamily and development of a diagnostic key for gene classification, Proc Natl Acad Sci U S A, vol.98, issue.5, p.11226268, 2001.

L. M. Iyer, K. S. Makarova, E. V. Koonin, and L. Aravind, Comparative genomics of the FtsK-HerA superfamily of pumping ATPases: implications for the origins of chromosome segregation, cell division and viral capsid packaging, Nucleic Acids Res, vol.32, issue.17, p.15466593, 2004.

E. Desmond, C. Brochier-armanet, and S. Gribaldo, Phylogenomics of the archaeal flagellum: rare horizontal gene transfer in a unique motility structure, BMC Evol Biol, vol.7, p.17605801, 2007.
URL : https://hal.archives-ouvertes.fr/hal-00698404

C. K. Ellison, J. Kan, R. S. Dillard, D. T. Kysela, A. Ducret et al., Obstruction of pilus retraction stimulates bacterial surface sensing, Science, vol.358, issue.6362, p.29074778, 2017.

S. S. Abby, B. Neron, H. Menager, M. Touchon, and E. P. Rocha, MacSyFinder: a program to mine genomes for molecular systems with an application to CRISPR-Cas systems, PLoS ONE, vol.9, issue.10, p.25330359, 2014.
URL : https://hal.archives-ouvertes.fr/pasteur-01080418

S. S. Abby and E. Rocha, Identification of Protein Secretion Systems in Bacterial Genomes Using MacSyFinder, Methods Mol Biol, vol.1615, p.28667599, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01677379

J. Soding, Protein homology detection by HMM-HMM comparison, Bioinformatics, vol.21, issue.7, p.15531603, 2005.

Q. Xu, B. Christen, H. J. Chiu, L. Jaroszewski, H. E. Klock et al., Structure of the pilus assembly protein TadZ from Eubacterium rectale: implications for polar localization, Mol Microbiol, vol.83, issue.4, p.22211578, 2012.

B. A. Perez-cheeks, P. J. Planet, I. N. Sarkar, S. A. Clock, Q. Xu et al., The product of tadZ, a new member of the parA/minD superfamily, Aggregatibacter actinomycetemcomitans

, Mol Microbiol, vol.83, issue.4, p.22239271, 2012.

D. N. Nunn and S. Lory, Product of the Pseudomonas aeruginosa gene pilD is a prepilin leader peptidase, Proc Natl Acad Sci U S A, vol.88, issue.8, p.1901657, 1991.

C. M. Pepe, M. W. Eklund, and M. S. Strom, Cloning of an Aeromonas hydrophila type IV pilus biogenesis gene cluster: complementation of pilus assembly functions and characterization of a type IV leader peptidase/N-methyltransferase required for extracellular protein secretion, Mol Microbiol, vol.19, issue.4, p.8820654, 1996.

J. W. Marsh and R. K. Taylor, Identification of the Vibrio cholerae type 4 prepilin peptidase required for cholera toxin secretion and pilus formation, Mol Microbiol, vol.29, issue.6, p.9781884, 1998.

L. T. Nguyen, H. A. Schmidt, V. Haeseler, A. Minh, and B. Q. , IQ-TREE: a fast and effective stochastic algorithm for estimating maximum-likelihood phylogenies, Mol Biol Evol, vol.32, issue.1, p.25371430, 2015.

D. J. Sherratt, L. K. Arciszewska, E. Crozat, J. E. Graham, and I. Grainge, The Escherichia coli DNA translocase FtsK, Biochem Soc Trans, vol.38, issue.2, p.20298190, 2010.

S. Nolivos, F. Touzain, C. Pages, M. Coddeville, P. Rousseau et al., Co-evolution of segregation guide DNA motifs and the FtsK translocase in bacteria: identification of the atypical Lactococcus lactis KOPS motif, Nucleic Acids Res, vol.40, issue.12, p.22373923, 2012.
URL : https://hal.archives-ouvertes.fr/hal-01003421

N. Iwabe, K. Kuma, M. Hasegawa, S. Osawa, and T. Miyata, Evolutionary relationship of archaebacteria, eubacteria, and eukaryotes inferred from phylogenetic trees of duplicated genes, Proc Natl Acad Sci U S A, vol.86, issue.23, p.2531898, 1989.

J. P. Gogarten, H. Kibak, P. Dittrich, L. Taiz, E. J. Bowman et al., Evolution of the vacuolar H +-ATPase: implications for the origin of eukaryotes, Proc Natl Acad Sci U S A, vol.86, issue.17, p.2528146, 1989.

S. Imam, Z. Chen, D. S. Roos, and M. Pohlschroder, Identification of surprisingly diverse type IV pili, across a broad range of gram-positive bacteria, PLoS ONE, vol.6, issue.12, p.22216142, 2011.

X. Wang, Q. Han, G. Chen, W. Zhang, and W. Liu, A Putative Type II Secretion System Is Involved in Cellulose Utilization in Cytophaga hutchisonii, Front Microbiol, vol.8, p.28848505, 2017.

L. Zeng, Y. Zhang, Y. Zhu, H. Yin, X. Zhuang et al., Extracellular proteome analysis of Leptospira interrogans serovar Lai, OMICS, vol.17, issue.10, p.23895271, 2013.

B. D. Nguyen and R. H. Valdivia, Virulence determinants in the obligate intracellular pathogen Chlamydia trachomatis revealed by forward genetic approaches, Proc Natl Acad Sci, vol.109, issue.4, p.22232666, 2012.

G. Achaz, E. P. Rocha, P. Netter, and E. Coissac, Origin and fate of repeats in bacteria, Nucleic Acids Res, vol.30, issue.13, p.12087185, 2002.

P. J. Planet, S. C. Kachlany, D. H. Fine, R. Desalle, and D. H. Figurski, The Widespread Colonization Island of Actinobacillus actinomycetemcomitans, Nat Genet, vol.34, issue.2, p.12717435, 2003.

J. G. Lawrence and J. R. Roth, Selfish operons: horizontal transfer may drive the evolution of gene clusters, Genetics, vol.143, issue.4, 1996.

S. El-gebali, J. Mistry, A. Bateman, S. R. Eddy, A. Luciani et al., The Pfam protein families database in 2019, Nucleic Acids Res, vol.47, issue.D1, p.30357350, 2019.

M. Iwata, H. Imamura, E. Stambouli, C. Ikeda, M. Tamakoshi et al., Crystal structure of a central stalk subunit C and reversible association/dissociation of vacuole-type ATPase, Proc Natl Acad Sci U S A, vol.101, issue.1, p.14684831, 2004.

L. Rico, A. Zheng, W. Petiot, N. Egelman, E. H. Francetic et al., Functional reconstitution of the type IVa pilus assembly system from enterohaemorrhagic Escherichia coli, Mol Microbiol, vol.111, issue.3, p.30561149, 2019.

M. Nivaskumar, J. Santos-moreno, C. Malosse, N. Nadeau, J. Chamot-rooke et al., Pseudopilin residue E5 is essential for recruitment by the type 2 secretion system assembly platform, Mol Microbiol, vol.101, issue.6, p.27260845, 2016.

V. J. Goosens, A. Busch, M. Georgiadou, M. Castagnini, K. T. Forest et al., Reconstitution of a minimal machinery capable of assembling periplasmic type IV pili, Proc Natl Acad Sci, vol.114, issue.25, p.28588140, 2017.

K. Raymann, C. Brochier-armanet, and S. Gribaldo, The two-domain tree of life is linked to a new root for the Archaea, Proc Natl Acad Sci, vol.112, issue.21, p.25964353, 2015.
URL : https://hal.archives-ouvertes.fr/hal-02018983

M. O'connell-motherway, A. Zomer, S. C. Leahy, J. Reunanen, F. Bottacini et al., Functional genome analysis of Bifidobacterium breve UCC2003 reveals type IVb tight adherence (Tad) pili as an essential and conserved host-colonization factor, Proc Natl Acad Sci U S A, vol.108, issue.27, p.21690406, 2011.

D. B. Nair, K. Uchida, S. Aizawa, and K. F. Jarrell, Genetic analysis of a type IV pili-like locus in the archaeon Methanococcus maripaludis, Arch Microbiol, vol.196, issue.3, p.24493292, 2014.

S. A. Clock, P. J. Planet, B. A. Perez, and D. H. Figurski, Outer membrane components of the Tad (tight adherence) secreton of Aggregatibacter actinomycetemcomitans, J Bacteriol, vol.190, issue.3, p.18055598, 2008.

L. C. Antunes, D. Poppleton, A. Klingl, A. Criscuolo, B. Dupuy et al., Phylogenomic analysis supports the ancestral presence of LPS-outer membranes in the Firmicutes, Elife, vol.5, p.27580370, 2016.
URL : https://hal.archives-ouvertes.fr/pasteur-01362343

N. N. Nickerson, S. S. Abby, E. P. Rocha, M. Chami, and A. P. Pugsley, A Single Amino Acid Substitution Changes the Self-Assembly Status of a Type IV Piliation Secretin, J Bacteriol, vol.194, issue.18, p.22773793, 2012.
URL : https://hal.archives-ouvertes.fr/pasteur-01374952

C. K. Ellison, J. Kan, J. L. Chlebek, K. R. Hummels, G. Panis et al., A bifunctional ATPase drives tad pilus extension and retraction

C. K. Ellison, T. N. Dalia, A. Vidal-ceballos, J. C. Wang, N. Biais et al., Retraction of DNA-bound type IV competence pili initiates DNA uptake during natural transformation in Vibrio cholerae, Nat Microbiol, vol.3, issue.7, p.29891864, 2018.

P. Seitz and M. Blokesch, DNA-uptake machinery of naturally competent Vibrio cholerae, Proc Natl Acad Sci U S A, vol.110, issue.44, p.24127573, 2013.

R. Laurenceau, G. Pehau-arnaudet, S. Baconnais, J. Gault, C. Malosse et al., A type IV pilus mediates DNA binding during natural transformation in Streptococcus pneumoniae, PLoS Pathog, vol.9, issue.6, p.23825953, 2013.
URL : https://hal.archives-ouvertes.fr/hal-00947054

M. D. Carruthers, E. N. Tracy, A. C. Dickson, K. B. Ganser, R. S. Munson et al., Biological roles of nontypeable Haemophilus influenzae type IV pilus proteins encoded by the pil and com operons, J Bacteriol, vol.194, issue.8, p.22328674, 2012.

M. Pohlschroder and R. N. Esquivel, Archaeal type IV pili and their involvement in biofilm formation, Front Microbiol, vol.6, p.25852657, 2015.

L. Tala, A. Fineberg, P. Kukura, and A. Persat, Pseudomonas aeruginosa orchestrates twitching motility by sequential control of type IV pili movements, Nat Microbiol, vol.4, issue.5, p.30804544, 2019.

M. Van-wolferen, A. Wagner, C. Van-der-does, and S. V. Albers, The archaeal Ced system imports DNA, Proc Natl Acad Sci, vol.113, issue.9, p.26884154, 2016.

S. Frols, M. Ajon, M. Wagner, D. Teichmann, B. Zolghadr et al., UV-inducible cellular aggregation of the hyperthermophilic archaeon Sulfolobus solfataricus is mediated by pili formation, Mol Microbiol, vol.70, issue.4, p.18990182, 2008.

A. Angelov, P. Bergen, F. Nadler, P. Hornburg, A. Lichev et al., Novel Flp pilus biogenesisdependent natural transformation, Front Microbiol, vol.6, p.25713572, 2015.

Z. T. Pimentel and Y. Zhang, Evolution of the Natural Transformation Protein, ComEC, in Bacteria. Front Microbiol, vol.9, p.30627116, 2018.

J. Claverys and B. Martin, Bacterial "competence" genes: signatures of active transformation, or only remnants?, Trends in Microbiology, vol.11, issue.4, p.12706993, 2003.

P. H. Oliveira, M. Touchon, and E. P. Rocha, The interplay of restriction-modification systems with mobile genetic elements and their prokaryotic hosts, Nucleic Acids Res, vol.42, issue.16, p.25120263, 2014.
URL : https://hal.archives-ouvertes.fr/pasteur-01374960

S. Sinha, A. D. Cameron, and R. J. Redfield, Sxy induces a CRP-S regulon in Escherichia coli, J Bacteriol, vol.191, issue.16, p.19502395, 2009.

S. Sinha and R. J. Redfield, Natural DNA uptake by Escherichia coli, PLoS ONE, vol.7, issue.4, p.22532864, 2012.

L. A. Ronish, E. Lillehoj, J. K. Fields, E. J. Sundberg, and K. H. Piepenbrink, The structure of PilA from Acinetobacter baumannii AB5075 suggests a mechanism for functional specialization in Acinetobacter type IV pili, J Biol Chem, vol.294, issue.1, p.30413536, 2019.

A. Cehovin, P. J. Simpson, M. A. Mcdowell, D. R. Brown, R. Noschese et al., Specific DNA recognition mediated by a type IV pilin, Proc Natl Acad Sci U S A, vol.110, issue.8, p.23386723, 2013.

T. F. Cooper, Recombination speeds adaptation by reducing competition between beneficial mutations in populations of Escherichia coli, PLoS Biol, vol.5, issue.9, p.17713986, 2007.

F. W. Stahl and N. E. Murray, The evolution of gene clusters and genetic circularity in microorganisms, Genetics, vol.53, issue.3, p.5331527, 1966.

R. Provvedi and D. Dubnau, ComEA is a DNA receptor for transformation of competent Bacillus subtilis, Mol Microbiol, vol.31, issue.1, p.9987128, 1999.

L. L. Burrows, Pseudomonas aeruginosa twitching motility: type IV pili in action, Annu Rev Microbiol, vol.66, p.22746331, 2012.

L. Craig and J. Li, Type IV pili: paradoxes in form and function, Curr Opin Struct Biol, vol.18, issue.2, p.18249533, 2008.

K. S. Makarova, Y. I. Wolf, P. Forterre, D. Prangishvili, M. Krupovic et al., Dark matter in archaeal genomes: a rich source of novel mobile elements, defense systems and secretory complexes. Extremophiles, vol.18, p.25113822, 2014.
URL : https://hal.archives-ouvertes.fr/pasteur-01977394

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, p.23329690, 2013.

A. Criscuolo, S. Gribaldo, and . Bmge, Block Mapping and Gathering with Entropy): a new software for selection of phylogenetic informative regions from multiple sequence alignments, BMC Evol Biol, vol.10, p.20626897, 2010.

R. D. Finn, J. Clements, and S. R. Eddy, HMMER web server: interactive sequence similarity searching, Nucleic Acids Res, vol.39, p.21593126, 2011.

C. Camacho, G. Coulouris, V. Avagyan, N. Ma, J. Papadopoulos et al., BLAST+: architecture and applications, BMC Bioinformatics, vol.10, p.421, 2009.

V. Miele, S. Penel, and L. Duret, Ultra-fast sequence clustering from similarity networks with SiLiX, BMC Bioinformatics, vol.12, p.21513511, 2011.
URL : https://hal.archives-ouvertes.fr/hal-00698365

M. Gouy, S. Guindon, and O. Gascuel, SeaView version 4: A multiplatform graphical user interface for sequence alignment and phylogenetic tree building, Mol Biol Evol, vol.27, issue.2, pp.221-225, 2010.
URL : https://hal.archives-ouvertes.fr/lirmm-00511794

S. R. Eddy, Accelerated Profile HMM Searches, PLoS Comput Biol, vol.7, issue.10, p.22039361, 2011.

A. W. Dress, C. Flamm, G. Fritzsch, S. Grunewald, M. Kruspe et al., Noisy: identification of problematic columns in multiple sequence alignments, Algorithms Mol Biol, vol.3, p.18577231, 2008.

D. T. Hoang, O. Chernomor, V. Haeseler, A. Minh, B. Q. Vinh et al., UFBoot2: Improving the Ultrafast Bootstrap Approximation, Mol Biol Evol, vol.35, issue.2, p.29077904, 2018.

S. Kalyaanamoorthy, B. Q. Minh, T. Wong, V. Haeseler, A. Jermiin et al., ModelFinder: fast model selection for accurate phylogenetic estimates, Nat Methods, vol.14, issue.6, p.28481363, 2017.

K. Lagesen, P. Hallin, E. A. Rodland, H. H. Staerfeldt, T. Rognes et al., RNAmmer: consistent and rapid annotation of ribosomal RNA genes, Nucleic Acids Res, vol.35, issue.9, p.17452365, 2007.

S. Capella-gutierrez, J. M. Silla-martinez, and T. Gabaldon, trimAl: a tool for automated alignment trimming in large-scale phylogenetic analyses, Bioinformatics, vol.25, issue.15, p.19505945, 2009.

O. Gascuel, BIONJ: an improved version of the NJ algorithm based on a simple model of sequence data, Mol Biol Evol, vol.14, issue.7, p.9254330, 1997.
URL : https://hal.archives-ouvertes.fr/lirmm-00730410

H. Shimodaira, An approximately unbiased test of phylogenetic tree selection, Syst Biol, vol.51, issue.3, p.12079646, 2002.

G. J. Szollosi, A. A. Davin, E. Tannier, V. Daubin, and B. Boussau, Genome-scale phylogenetic analysis finds extensive gene transfer among fungi, Philos Trans R Soc Lond B Biol Sci, vol.370, p.26323765, 1678.
URL : https://hal.archives-ouvertes.fr/hal-01218565