When modern humans left Africa ca. 60,000 years ago (60 kya), they were already infected with Helicobacter pylori, and these bacteria have subsequently diversified in parallel with their human hosts. But how long were humans infected by H. pylori prior to the out-of-Africa event? Did this co-evolution predate the emergence of modern humans, spanning the species divide?
At the global level, H. pylori has been subdivided by population genetic tools such as STRUCTURE  into multiple, relatively distinct populations that are specific for large geographical areas: hpEurope, hpSahul, hpEastAsia, hpAsia2, hpNEAfrica, hpAfrica1 and hpAfrica2 (Figure 1) –.
|Neighbor-joining population tree of extant populations of H. pylori.|
Phylogeographic patterns in H. pylori have been shown to reflect significant demographic events in human prehistory , . H. pylori has accompanied anatomically modern humans since their migrations out of Africa some 60,000 years ago (60 kya), and mirrors the human pattern of increased genetic distance and decreased diversity with distance from Africa . However, the age of an association between humans and H. pylori has not been elucidated, other than that it predates 60 kya.
The distribution of H. pylori populations in Africa.
Bayesian cluster analysis was performed with the non-admixture model of STRUCTURE  for estimates of the total number of populations, K, between 2 and 5, which was the highest value of K that yielded consistent clustering and consistent probability estimates between individual runs. Almost half of the San haplotypes (26/56, 46%) belong to hpAfrica2 (Figure 3A, Figure 4A,B, Table 2). hpAfrica2 isolates were found in all three San communities, ranging in frequency from 28% of all haplotypes (!Xun) to 55% (Khwe, Khomani).We also identified 35 hpAfrica2 haplotypes among isolates from the Northern Sotho near Pretoria and from Xhosa and Europeans in Cape Town.
Bayesian population assignments using STRUCTURE V2.0.
The consensus tree from this analysis shows that the southern (Khomani, Bantu) San haplotypes fell into a young clade which emerged from an more ancestral population of hpAfrica2 haplotypes, all of which were from San and most of which were from the northern Khwe and !Xun (Figure 3C). These observations suggest that hpAfrica2 evolved within the San and was subsequently transmitted to Bantus.
Almost all non-other haplotypes from San were assigned to hpAfrica1. In contrast, to the results described above, these were less diverse (π 95% CL [2.50, 2.82%]) than hpAfrica1 from Bantus ([3.10, 3.20%]), suggesting that the San had acquired hpAfrica1 from Bantu.
We therefore shotgun sequenced the genome of H. cetorum strain MIT 99-5665, which represents the closest known relative of H. pylori and Hac  (Figure 2), and used the orthologous nucleotide sequences from that genome as an outgroup for rooting the CLONALFRAME tree. Independent analyses yielded the same rooting branch point when the tree was rooted with and based on orthologs that were shared between H. pylori and enterohepatic Helicobacter genomes (data not shown).
|A comparison of global H. pylori and human mtDNA phylogenies.|
The TMRCA of all H. pylori plus Hac lineages was 88–116 kya (CLONALFRAME: 88–92 kya; IMA: 92–116 kya; Table 4, Figure 6A). The date for the coalescence of non-recombining Y-chromosome lineages in modern humans is similar at 90 kya  to 141.5±15.6 kya  whereas the date of split between L0 and L1–6 mtDNA haplogroups in humans is older, 194.3±32.5 kya, (Figure 6B) , . Despite the different age estimates, the topology and branching pattern of the genealogies are strikingly similar between H. pylori and human mtDNA (Figure 6).
The TMRCA for the split between hpAfrica2 and Hac is 43–56 kya (Table 4), and hpAfrica2 subsequently split (32–47 kya) into the northern and southern isolates. We note that a similar date (40 kya) was recently estimated for the TMRCA of Y-chromosome haplogroup A-M51 among the San by Henn et al. , which also subsequently split between northern and southern San populations. Within the other super-lineage, the estimated TMRCA was 36–52 kya for the African populations hpAfrica1 and hpNEAfrica (Table 4).
Finally, the genetic diversity is greater among hpAfrica2 from San than from Bantu, indicating that it was transmitted to Bantu in the last few hundred years since their arrival in southern Africa.
Our data shows that anatomically modern humans were infected by H. pylori long before their migrations out of Africa of ~60 kya , . We estimate the minimum age of that association to be approximately 100 kyr (range 88–116). This is comparable to the age of the coalescence of the human Y-chromosome and about half of the coalescent for mtDNA. The age of a coalescent is a minimal date estimate because lineage sorting and bottlenecks lead to extinction of older lineages, resulting in a single genealogical source of all subsequent descendents.
We therefore propose that the association of H. pylori with humans also reflects a host jump to humans from an unknown species, which occurred approximately 100 kya or earlier. In principle, two later host jumps might explain the existence of two super-lineages of H. pylori, but this seems less likely because the similar phylogeographical patterns of H. pylori and mtDNA haplogroups indicate that they have undergone a parallel evolutionary history.
Chronological reconstruction of the major population events occurring during the intimate human-H. pylori association.
The phylogeographic diversity within H. pylori is inconsistent with a single human expansion from Africa. H. pylori accompanied humans on the migration of ~60 kya , reaching Oceania not long thereafter . However, European H. pylori possess distinct properties from most other global populations of these bacteria. H. pylori from Europe, the Middle East, western Asia and India belong to the hpEurope population , , , –, which unlike Europeans is typified by great genetic diversity, greater than in Africa except for southern Africa where strong genetic diversity results from the presence of the second super-lineage (hpAfrica2). The great diversity of hpEurope was attributed to the fact that it is a hybrid population which arose from the admixture of AE1 (Ancestral Europe 1) and AE2 (Ancestral Europe 2) (Figure 4B) , . AE1 arose in Central Asia after H. pylori was carried out of Africa during the Out of Africa migration of ~60 kya , and its descendants are found among extant hpAsia2. However, the data in Figure 6A indicate that AE2, whose extant descendents in hpNEAfrica are associated with northeast Africa, first split from its sister lineage hpAfrica1 36–52 kya, after the (first) Out of Africa migration. We therefore hypothesize that a second Out of Africa migration in the last 52 kya brought AE2 to the Levant, after which it came into secondary contact with AE1. Subsequent extensive admixture resulted in hpEurope, which subsequently spread to Europe and western Asia (Figure 8).
Thus, if initial Europeans were colonized with H. pylori, those bacteria were subsequently replaced by hpEurope, similar to the replacement of hspAmerind strains by hpEurope strains among Amerindians from South America . To illustrate these interpretations, we show approximate routes and timings for a second colonization of Europe based on the properties of H. pylori populations (Figure 8), in which migration waves from North East Africa and Central Asia met and admixed in the Middle East and/or Western Asia sometimes 10–52 kya. The widespread presence of hpEurope in Mediterranean Africa is then attributed to later migrations to northern Africa, including migrations from Iberia (mtDNA haplogroup H1; 8–9 kya) , the Near East (mtDNA haplogroup M1; 35 kya) ; autosomal DNA; >12 kya ), or even as recently as the expansion of the Islamic caliphate in the last 1200 years. Our model also summarizes the dates of other human migrations that have distributed H. pylori from its southern African source (Figure 8).