How did dogs become our best friend?

Dogs

Editor's Introduction

Complete mitochondrial genomes of ancient canids suggest a European origin of domestic dogs

annotated by
Barthélémy Caron, Cécile Gaston, Amaury Monmeyran

At some point in our lives, we have all had a friendship with a dog.  So did the generations before us, as well as the generation before them.  When, exactly, did the friendship between dogs and humans take shape?  Research in this paper challenges current theories regarding the original location of wolf domestication. The authors sequenced DNA from mitochondrial genomes of both prehistoric canids and modern wolves and compared this data with previously known mitochondrial sequences of wolves and dogs. They used these data to construct a new phylogenetic tree. By comparing this updated tree with the location and age of dog fossils, the authors are able to draw new conclusions on the origins of dog domestication.

Paper Details

Original title
Complete mitochondrial genomes of ancient canids suggest a European origin of domestic dogs
Authors
Olaf Thalmann Mietje Germonpr
Original publication date
Reference
Vol. 342 no. 6160 pp. 871-874
Issue name
Science
DOI
10.1126/science.1243650

Abstract

The geographic and temporal origins of the domestic dog remain controversial, as genetic data suggest a domestication process in East Asia beginning 15,000 years ago, whereas the oldest doglike fossils are found in Europe and Siberia and date to >30,000 years ago. We analyzed the mitochondrial genomes of 18 prehistoric canids from Eurasia and the New World, along with a comprehensive panel of modern dogs and wolves. The mitochondrial genomes of all modern dogs are phylogenetically most closely related to either ancient or modern canids of Europe. Molecular dating suggests an onset of domestication there 18,800 to 32,100 years ago. These findings imply that domestic dogs are the culmination of a process that initiated with European hunter-gatherers and the canids with whom they interacted.

Report

Dogs are one of the best known examples of domestication, the process of species modification over time by human-induced selection (1). Domestication often leads to increased phenotypic variation and a geographic distribution that can be heavily influenced by human dispersal. The extensive phenotypic variation among dog breeds hinders a simple inference of dog origins based on the presence of traits shared between dogs and any specific population of the gray wolf (Canis lupus) from which dogs derive (24). Furthermore, inferences from genetic data are confounded by a long history of trade and admixture among dogs from disparate geographic areas, ancient and ongoing local admixture with wolves, intense inbreeding within some lineages, and the stochastic effects of incomplete lineage sorting. Nevertheless, centers of dog origins from genetic data have been proposed, including the Middle East and East Asia (57). However, the oldest putative dog remains are found in Western Europe and Siberia and date from 15,000 to 36,000 years ago (28), although the classification of these specimens remains contentious (9). The earliest putative dog remains from the Middle East and East Asia are no older than about 13,000 years ago [see table S3 (10)].

DNA extracted from the earliest canids showing phenotypic evidence of domestication (281114) can potentially be used to test hypotheses about the origin of modern dogs. We generated complete and partial mitochondrial genomes from 18 prehistoric canids and 20 modern wolves of Eurasian and American origin (Table 1 and table S2) by performing DNA capture followed by high-throughput sequencing (15). The DNA fragments recovered from these samples show patterns expected of ancient DNA, including a correlation between sequence length and sample age (fig. S1) and deamination patterns typical of ancient DNA (15) (fig. S2). After filtering, iterative assembly, and exclusion of mitochondrial genomes with less than 50% of the length recovered, we obtained a median 12-fold (1.9 to 625.7) coverage of the 18 ancient genomes, with on average 15,014 (8667 to 16,415) nucleotides supported by at least twofold coverage. These mtDNA assemblies from ancient canids were compared with complete mitochondrial genome sequences from 49 wolves; 77 dogs, including divergent dog breeds such as Basenji and Dingo; three recently published Chinese indigenous dogs (7); and four coyotes totaling 148 mitochondrial genomes.

picture1_0.png

Table 1.  Ancient specimens used and summary of sequencing statistics.  (A) Ancient specimens captured using custom designed capture arrays. (B) Specimens enriched for mtDNA using long range PCR-products and custom designed biotinylated adapters (15). Morphological classification and approximate age are from the respective references (see table S1). Ancient specimens with ambiguous morphological classification are shown in italic font. Nucleotides were retained with a minimum of two reads per base. Further information on filtering parameters is available (15).

What data is in this chart?

Complete and partial mitochondrial genomes from 18 prehistoric canids.  This genomic information from ancient canids was then compared to complete mitochondrial genome sequences from 49 wolves; 77 dogs, including divergent dog breeds such as Basenji and Dingo; three recently published Chinese indigenous dogs (7); and four coyotes totaling 148 mitochondrial genomes.

Phylogenetic analyses of the mitochondrial genome data using maximum likelihood, coalescence and Bayesian approaches all reveal a well-resolved phylogeny (Fig. 1). Although dogs and wolves are not reciprocally monophyletic, all modern dogs and many wolf populations fall within one of several well-supported clades (Fig. 1and fig. S9). Within this tree topology, dogs fall within one of four clades (Dog A to D) (Fig. 1 and fig. S9), with clade A containing the majority of dog sequences (64%). Three haplotypes from ancient Belgian canids form the most deeply diverging group in the tree. Although the cranial morphology of one of these, the Goyet dog (Belgium 36,000) (Table 1 and table S1) has been interpreted as doglike (2), its mtDNA relation to other canids places it as an ancient sister-group to all modern dogs and wolves rather than a direct ancestor of dogs. One of the Belgian specimens (Belgium 26,000) has been found to be uniquely large (2) and could be related to a genetically and morphologically distinct form of wolves from Late Pleistocene deposits of the High Arctic permafrost (16). However, none of the sequences from the three northerly permafrost wolves (Alaska 28,000, Alaska 21,000, and Alaska 20,800) (Fig. 1) fall within or are sister to this clade. Given their mitochondrial distinctiveness, the Belgian canids, including the Goyet dog, may represent an aborted domestication episode or a phenotypically distinct, and not previously recognized, population of gray wolf.

wey.jpg

Fig. 1.  Phylogenetic arrangement of modern and ancient dog (blue) and wolf sequences (orange) as obtained from coalescence-based, maximum likelihood, and Bayesian methods.  The outgroup (four coyotes) and two Chinese wolf sequences were excluded [see (15) for more details]. Ancient specimens are labeled with the respective country of origin and their approximate reported age (italicized; in years before present). Fossil specimens with ambiguous taxonomic classification are indicated by a gray color. Whenever modern canid sequences form a monophyletic cluster, the number of sequences in the cluster is indicated in brackets. Asterisks highlight statistical support whenever both bootstrap values are >90% and posterior support is >0.9 for the maximum likelihood and Bayesian analyses, respectively.

What does this graph show? 

Phylogenetic arrangement showing the most probable relations between wolves, modern, and ancient dogs.

The x axis represent the approximate age of the specimens. It shows that different domestication events have occurred.

What kinds of mutations occured? 

What are the kind of mutations induced by artificial selection in dogs?

1. An improved ability to use starch as a source of energy

2. Reduced teeth, brains, and skull sizes and reduced aggressiveness

3. Modified social cognition capabilities

Darwin and the origin of dogs

In "On the Origin of Species," Charles Darwin stated that he believed that the dogs species that he observed couldn't come from only one species of wolf. 

How could Darwin have guessed this in a time where DNA and genes were not known?

The earliest evidence of dog domestication 

Here is an article chronicling the discovery of the remains of older dogs.

Dog clades A, C, and D, which make up 78% of dog sequences in our study, are each sister to one or more ancient canids of Europe. The most diverse of these groups is clade A, which includes divergent breeds, such as Basenji and Dingo, and two of the Chinese indigenous dogs (7). Moreover, three pre-Colombian New World dogs, ranging in age from 1000 to 8500 years ago, fall within dog clade A (Table 1 and table S1). The calculated time to the most recent common ancestor (MRCA) of dog clade A and ancient New World dog sequences is ~18,800 years ago [95% highest posterior density (HPD): 15,100 to 22,600] (fig. S10), which supports the hypothesis that pre-Colombian dogs in the New World share ancestry with modern dogs. Thus, these dogs likely arrived with the first humans in the New World (1718). The clade comprising these ancient New World dogs and modern dog clade A is most closely related to an ancient wolf sequence from the Kesslerloch cave in Switzerland (Switzerland 2 14,500) with a MRCA that existed ~32,100 years ago (95% HPD: 27,500 to 36,700).

The lowest diversity dog clade (D) contains only sequences from two Scandinavian breeds and is sister to an ancient wolflike canid from Switzerland with a common ancestor that existed ~18,300 years ago (95% HPD: 15,300 to 21,900). This grouping is most closely related to another sequence from ancient European wolves, as well as extant wolves from Poland and Italy, and is rooted with the sequence from a putative early dog from the Altai Mountains in Russia (13). The grouping of clade D with ancient wolf lineages and the association of the Altai specimen with this clade do not support recent common ancestry of the Altai specimen lineage with the great majority of modern dogs. However, clade D dog haplotypes could have been captured as a result of interactions between ancient wolves and early humans that migrated into Scandinavia (19).

The closest sister group for dogs in clade C, which makes up 12% (9 of 77) of modern dog sequences, are two morphologically distinct ancient dogs from Bonn-Oberkassel (12) and the Kartstein cave in Germany (14) (Germany 14,700 and Germany 12,500, respectively) having a MRCA that existed ~16,000 to 24,000 years ago (95% HPD: 13,500 to 28,100). Last, dog clade B, which contains 22% (17 of 77) of dog sequences has the closest phylogenetic associations with sequences from modern wolves from Sweden and the Ukraine and shares a MRCA with them some ~9200 years ago (95% HPD: 6500 to 12,300).

The association of sequences from modern dogs in clades A, C, and D with ancient European canid specimens and of modern dogs from clade B with European wolves suggests an origin of dogs in Europe, rather than the Middle East or East Asia, as previously suggested (57). Critically, none of the modern wolf sequences from other putative centers of origins such as the Middle East (Saudi Arabia, Oman, Israel, Iran, and India) or East Asia (China, Japan, and Mongolia) show close affinity with modern dog clades. Bayesian analysis of divergence times implies a European origin of the domestic dog dating to as much as 18,800 to 32,100 years ago, given an upper limit of the MRCA of an ancient wolf sequence and dogs clustered in clade A and the MRCA of the most diverse dog clade as a lower limit (Fig. 1). Consequently, our results support the hypothesis that dog domestication preceded the emergence of agriculture (20) and occurred in the context of European hunter-gatherer cultures.

Previous research suggested that modern dogs experienced a two-phase bottleneck. The first was at the origin of the domestication process, and the second was more recent during breed formation over the past several hundred years (21). To investigate the demographic history of dogs, we used a Bayesian Skygrid analysis (22) applied to dog clade A and the closely related pre-Columbian dogs. We find a continuous population size increase from the time of the MRCA to about 5000 years ago, which may be attributable to the earliest domestication phase (Fig. 2). A more recent decline occurred between 5000 and 2500 years ago and was followed by a sharp increase in population size (Fig. 2). This increase parallels the trajectory of human population size (23), which suggests demographic dependence of dogs on human populations. In contrast, wolf numbers declined during this period, consistent with the emergence of agrarian cultures and the loss of vital wolf habitat and wild game.

fgh.jpg

Fig. 2.  Bayesian Skygrid plot depicting the demographic trajectory of dog clade A and closely related pre-Columbian dogs.  Times are given in years before present and the effective population size is indicated in median logNe (solid line) with the accompanying 95% HPD interval.

Question being asked?

How does the human population and lifestyle change the evolution of dogs populations?

Conclusion

This figure show the evolution of the dog clade A population.

Both human and dog demographic trajectory show the same variations (ref. 23).

The authors suggest that the evolution of the dog population is linked to the human variations of population.

Our findings support the conclusion that the mitochondrial legacy of dogs derives from wolves of European origin. Past mitochondrial and Y chromosome analyses that suggested a non-European location for the onset of domestication were more limited in sampling of modern or ancient wolves or prehistoric dogs and had weak statistical support for phylogenetic branching points (4624). The modern dog clades A to D are well-supported in our tree of complete mtDNA sequence. We find that the sequence diversity that exists today in dogs can all be found in ancient (clades A, C, and D) or modern (clade B) European canids. The inferred recent divergence of clade B from wolves now found in Sweden and the Ukraine implies that it might represent a mitochondrial genome introgressed from wolves rather than one established by domestication, because dogs were clearly domesticated by this time (81214).

Notably, our ancient panel does not contain specimens from the Middle East or China, two proposed centers of origin (56). In fact, no ancient dog remains older than ~13,000 years are known from these regions (10). However, ancient wolf and dog remains from these areas would need to be rooted more closely to the four dominant dog clades than any ancient or modern European canids to contradict our primary conclusions. We consider this scenario unlikely as it would require a common recent coalescence of these ancestral wolf and dog sequences from geographically disparate areas. Nevertheless, a more complete and nuanced picture of dog domestication will likely emerge with the addition of ancient canine mtDNA data from the Middle East and Asia. A further caveat to our conclusions is that although the mtDNA sequence tree is well supported, it represents a single genetic locus. The rapid coalescence of mtDNA genomes and the lack of recombination are important advantages; however, both mitochondrial and nuclear genomes suffer from incomplete lineage sorting, which, given the recent divergence of dogs and wolves, can potentially confound evolutionary inference. The availability of multiple independent loci in the nuclear genome potentially offers more power to resolve phylogenetic relations. We attempted to capture multiple nuclear loci using a densely tiled capture array, but were not able to obtain sufficient coverage to call genotypes confidently in any of the ancient specimens, which reflects their poor state of DNA preservation (15). Nonetheless, our mtDNA genome tree shows that three of four modern dog clades are more closely related to sequences from ancient European rather than extant wolves. Further, analysis of coalescence times support a dog-wolf divergence time of >15,000 years ago. An evolutionary scenario consistent with these results is that dog domestication was initiated close to the Last Glacial Maximum when hunter-gathers preyed on megafauna (25). Conceivably, proto-dogs might have taken advantage of carcasses left on site by early hunters, assisted in the capture of prey, or provided defense from large competing predators at kills. Finally, our results imply that some of the earliest putative dog remains, such as the Goyet dog from Belgium (2) or Altai Mountain specimen from Russia (13), may represent aborted domestication episodes. If true, this suggests that the conditions for dog domestication were not unique to one place or time and adds a role for serendipity to the process that led to the early and singular domestication of a large and dangerous carnivore.

Supplementary Materials

www.sciencemag.org/content/342/6160/871/suppl/DC1

Materials and Methods

Supplementary Text

Figs. S1 to S9

Tables S1 to S5

References (2678)

References and Notes

  1. G. Larson, J. Burger, A population genetics view of animal domestication. Trends Genet. 29, 197–205 (2013).

  2. M. Germonpré, M. V. Sablin, R. E. Stevens, R. E. M. Hedges, M. Hofreiter, M. Stiller, V. R. Després, Fossil dogs and wolves from Palaeolithic sites in Belgium, the Ukraine and Russia: osteometry, ancient DNA and stable isotopes. J. Archaeol. Sci. 36, 473–490 (2009).

  3. S. J. Olsen, J. W. Olsen, The chinese wolf, ancestor of new world dogs. Science 197, 533–535 (1977).

  4. C. Vilà, P. Savolainen, J. E. Maldonado, I. R. Amorim, J. E. Rice, R. L. Honeycutt, K. A. Crandall, J. Lundeberg, R. K. Wayne, Multiple and ancient origins of the domestic dog. Science 276, 1687–1689 (1997).

  5. B. M. vonHoldt, J. P. Pollinger, K. E. Lohmueller, E. Han, H. G. Parker, P. Quignon, J. D. Degenhardt, A. R. Boyko, D. A. Earl, A. Auton, A. Reynolds, K. Bryc, A. Brisbin, J. C. Knowles, D. S. Mosher, T. C. Spady, A. Elkahloun, E. Geffen, M. Pilot, W. Jedrzejewski, C. Greco, E. Randi, D. Bannasch, A. Wilton, J. Shearman, M. Musiani, M. Cargill, P. G. Jones, Z. Qian, W. Huang, Z. L. Ding, Y. P. Zhang, C. D. Bustamante, E. A. Ostrander, J. Novembre, R. K. Wayne, Genome-wide SNP and haplotype analyses reveal a rich history underlying dog domestication. Nature 464, 898–902 (2010).

  6. P. Savolainen, Y. P. Zhang, J. Luo, J. Lundeberg, T. Leitner, Genetic evidence for an East Asian origin of domestic dogs. Science 298, 1610–1613 (2002).

  7. G. D. Wang, W. Zhai, H. C. Yang, R. X. Fan, X. Cao, L. Zhong, L. Wang, F. Liu, H. Wu, L. G. Cheng, A. D. Poyarkov, N. A. Poyarkov Jr., S. S. Tang, W. M. Zhao, Y. Gao, X. M. Lv, D. M. Irwin, P. Savolainen, C. I. Wu, Y. P. Zhang, The genomics of selection in dogs and the parallel evolution between dogs and humans. Nat Commun 4, 1860 (2013).

  8. M. Sablin, G. Khlopachev, The earliest Ice Age dogs: Evidence from Eliseevichi 11. Curr. Anthropol. 43, 795–799 (2002).

  9. S. J. Crockford, Y. V. Kuzmin, Comments on Germonpré et al., Journal of Archaeological Science 36, 2009 “Fossil dogs and wolves from Palaeolithic sites in Belgium, the Ukraine and Russia: Osteometry, ancient DNA and stable isotopes”, and Germonpré, Lázni?ková-Galetová, and Sablin, Journal of Archaeological Science 39, 2012 “Palaeolithic dog skulls at the Gravettian P?edmostí site, the Czech Republic.” J. Archaeol. Sci. 39, 2797–2801 (2012).

  10. G. Larson, E. K. Karlsson, A. Perri, M. T. Webster, S. Y. Ho, J. Peters, P. W. Stahl, P. J. Piper, F. Lingaas, M. Fredholm, K. E. Comstock, J. F. Modiano, C. Schelling, A. I. Agoulnik, P. A. Leegwater, K. Dobney, J. D. Vigne, C. Vilà, L. Andersson, K. Lindblad-Toh, Rethinking dog domestication by integrating genetics, archeology, and biogeography. Proc. Natl. Acad. Sci. U.S.A. 109, 8878–8883 (2012).

  11. H. Napierala, H.-P. Uerpmann, A ‘new’ palaeolithic dog from central Europe. Int. J. Osteoarchaeol. 22, 127–137 (2012).

  12. G. Nobis, Der älteste Haushund lebte vor 14000 Jahren. Umschau 79, 610 (1979).

  13. N. D. Ovodov, S. J. Crockford, Y. V. Kuzmin, T. F. Higham, G. W. Hodgins, J. van der Plicht, A 33,000-year-old incipient dog from the Altai Mountains of Siberia: Evidence of the earliest domestication disrupted by the Last Glacial Maximum. PLOS ONE 6, e22821 (2011).

  14. M. Baales, Umwelt und Jagdökonomie der Ahrensburger Rentierjäger im Mittelgebirge. Mongraphien RGZM, Mainz 38, 106 (1996).

  15. Supplementary materials are available on Science Online.

  16. J. A. Leonard, C. Vilà, K. Fox-Dobbs, P. L. Koch, R. K. Wayne, B. Van Valkenburgh, Megafaunal extinctions and the disappearance of a specialized wolf ecomorph. Curr. Biol. 17, 1146–1150 (2007).

  17. J. A. Leonard, R. K. Wayne, J. Wheeler, R. Valadez, S. Guillén, C. Vilà, Ancient DNA evidence for Old World origin of New World dogs. Science 298, 1613–1616 (2002).

  18. B. van Asch, A. B. Zhang, M. C. Oskarsson, C. F. Klütsch, A. Amorim, P. Savolainen, Pre-Columbian origins of Native American dog breeds, with only limited replacement by European dogs, confirmed by mtDNA analysis. Proc. Biol. Soc. 280, 20131142 (2013).

  19. H. Malmström, C. Vilà, M. T. Gilbert, J. Storå, E. Willerslev, G. Holmlund, A. Götherström, Barking up the wrong tree: Modern northern European dogs fail to explain their origin. BMC Evol. Biol. 8, 71 (2008).

  20. E. Axelsson, A. Ratnakumar, M. L. Arendt, K. Maqbool, M. T. Webster, M. Perloski, O. Liberg, J. M. Arnemo, A. Hedhammar, K. Lindblad-Toh, The genomic signature of dog domestication reveals adaptation to a starch-rich diet. Nature 495, 360–364 (2013).

  21. K. Lindblad-Toh, C. M. Wade, T. S. Mikkelsen, E. K. Karlsson, D. B. Jaffe, M. Kamal, M. Clamp, J. L. Chang, E. J. Kulbokas 3rd, M. C. Zody, E. Mauceli, X. Xie, M. Breen, R. K. Wayne, E. A. Ostrander, C. P. Ponting, F. Galibert, D. R. Smith, P. J. DeJong, E. Kirkness, P. Alvarez, T. Biagi, W. Brockman, J. Butler, C. W. Chin, A. Cook, J. Cuff, M. J. Daly, D. DeCaprio, S. Gnerre, M. Grabherr, M. Kellis, M. Kleber, C. Bardeleben, L. Goodstadt, A. Heger, C. Hitte, L. Kim, K. P. Koepfli, H. G. Parker, J. P. Pollinger, S. M. Searle, N. B. Sutter, R. Thomas, C. Webber, J. Baldwin, A. Abebe, A. Abouelleil, L. Aftuck, M. Ait-Zahra, T. Aldredge, N. Allen, P. An, S. Anderson, C. Antoine, H. Arachchi, A. Aslam, L. Ayotte, P. Bachantsang, A. Barry, T. Bayul, M. Benamara, A. Berlin, D. Bessette, B. Blitshteyn, T. Bloom, J. Blye, L. Boguslavskiy, C. Bonnet, B. Boukhgalter, A. Brown, P. Cahill, N. Calixte, J. Camarata, Y. Cheshatsang, J. Chu, M. Citroen, A. Collymore, P. Cooke, T. Dawoe, R. Daza, K. Decktor, S. DeGray, N. Dhargay, K. Dooley, K. Dooley, P. Dorje, K. Dorjee, L. Dorris, N. Duffey, A. Dupes, O. Egbiremolen, R. Elong, J. Falk, A. Farina, S. Faro, D. Ferguson, P. Ferreira, S. Fisher, M. FitzGerald, K. Foley, C. Foley, A. Franke, D. Friedrich, D. Gage, M. Garber, G. Gearin, G. Giannoukos, T. Goode, A. Goyette, J. Graham, E. Grandbois, K. Gyaltsen, N. Hafez, D. Hagopian, B. Hagos, J. Hall, C. Healy, R. Hegarty, T. Honan, A. Horn, N. Houde, L. Hughes, L. Hunnicutt, M. Husby, B. Jester, C. Jones, A. Kamat, B. Kanga, C. Kells, D. Khazanovich, A. C. Kieu, P. Kisner, M. Kumar, K. Lance, T. Landers, M. Lara, W. Lee, J. P. Leger, N. Lennon, L. Leuper, S. LeVine, J. Liu, X. Liu, Y. Lokyitsang, T. Lokyitsang, A. Lui, J. Macdonald, J. Major, R. Marabella, K. Maru, C. Matthews, S. McDonough, T. Mehta, J. Meldrim, A. Melnikov, L. Meneus, A. Mihalev, T. Mihova, K. Miller, R. Mittelman, V. Mlenga, L. Mulrain, G. Munson, A. Navidi, J. Naylor, T. Nguyen, N. Nguyen, C. Nguyen, T. Nguyen, R. Nicol, N. Norbu, C. Norbu, N. Novod, T. Nyima, P. Olandt, B. O’Neill, K. O’Neill, S. Osman, L. Oyono, C. Patti, D. Perrin, P. Phunkhang, F. Pierre, M. Priest, A. Rachupka, S. Raghuraman, R. Rameau, V. Ray, C. Raymond, F. Rege, C. Rise, J. Rogers, P. Rogov, J. Sahalie, S. Settipalli, T. Sharpe, T. Shea, M. Sheehan, N. Sherpa, J. Shi, D. Shih, J. Sloan, C. Smith, T. Sparrow, J. Stalker, N. Stange-Thomann, S. Stavropoulos, C. Stone, S. Stone, S. Sykes, P. Tchuinga, P. Tenzing, S. Tesfaye, D. Thoulutsang, Y. Thoulutsang, K. Topham, I. Topping, T. Tsamla, H. Vassiliev, V. Venkataraman, A. Vo, T. Wangchuk, T. Wangdi, M. Weiand, J. Wilkinson, A. Wilson, S. Yadav, S. Yang, X. Yang, G. Young, Q. Yu, J. Zainoun, L. Zembek, A. Zimmer, E. S. Lander, Genome sequence, comparative analysis and haplotype structure of the domestic dog. Nature 438, 803–819 (2005).

  22. M. S. Gill, P. Lemey, N. R. Faria, A. Rambaut, B. Shapiro, M. A. Suchard, Improving Bayesian population dynamics inference: A coalescent-based model for multiple loci. Mol. Biol. Evol. 30, 713–724 (2013).

  23. J. A. Tennessen, A. W. Bigham, T. D. O’Connor, W. Fu, E. E. Kenny, S. Gravel, S. McGee, R. Do, X. Liu, G. Jun, H. M. Kang, D. Jordan, S. M. Leal, S. Gabriel, M. J. Rieder, G. Abecasis, D. Altshuler, D. A. Nickerson, E. Boerwinkle, S. Sunyaev, C. D. Bustamante, M. J. Bamshad, J. M. Akey, , Broad GO, Seattle GO, on behalf of the NHLBI Exome Sequencing Project, Evolution and functional impact of rare coding variation from deep sequencing of human exomes. Science 337, 64–69 (2012

  24. Z. L. Ding, M. Oskarsson, A. Ardalan, H. Angleby, L. G. Dahlgren, C. Tepeli, E. Kirkness, P. Savolainen, Y. P. Zhang, Origins of domestic dog in southern East Asia is supported by analysis of Y-chromosome DNA. Heredity 108, 507–514 (2012).

  25. J. Alroy, A multispecies overkill simulation of the end-Pleistocene megafaunal mass extinction. Science 292, 1893–1896 (2001).

  26. M. Germonpré, M. Lázni?ková-Galetová, M. V. Sablin, Palaeolithic dog skulls at the Gravettian P?edmostí site, the Czech Republic. J. Archaeol. Sci. 39, 184–202 (2012).

  27. M. Germonpré, M. V. Sablin, V. Després, M. Hofreiter, M. Lázni?ková-Galetová, R. E. Stevens, M. Stiller, Palaeolithic dogs and the early domestication of the wolf: A reply to the comments of Crockford and Kuzmin (2012). J. Archaeol. Sci. 40, 786–792 (2013).

  28. D. F. Morey, M. D. Wiant, Early holocene domestic dog burials from the North American Midwest. Curr. Anthropol. 33, 224 (1992).

  29. N. Rohland, M. Hofreiter, Ancient DNA extraction from bones and teeth. Nat. Protoc. 2, 1756–1762 (2007).

  30. H. A. Burbano, E. Hodges, R. E. Green, A. W. Briggs, J. Krause, M. Meyer, J. M. Good, T. Maricic, P. L. Johnson, Z. Xuan, M. Rooks, A. Bhattacharjee, L. Brizuela, F. W. Albert, M. de la Rasilla, J. Fortea, A. Rosas, M. Lachmann, G. J. Hannon, S. Pääbo, Targeted investigation of the Neandertal genome by array-based sequence capture. Science 328, 723–725 (2010).

  31. L. Orlando, A. Ginolhac, G. Zhang, D. Froese, A. Albrechtsen, M. Stiller, M. Schubert, E. Cappellini, B. Petersen, I. Moltke, P. L. Johnson, M. Fumagalli, J. T. Vilstrup, M. Raghavan, T. Korneliussen, A. S. Malaspinas, J. Vogt, D. Szklarczyk, C. D. Kelstrup, J. Vinther, A. Dolocan, J. Stenderup, A. M. Velazquez, J. Cahill, M. Rasmussen, X. Wang, J. Min, G. D. Zazula, A. Seguin-Orlando, C. Mortensen, K. Magnussen, J. F. Thompson, J. Weinstock, K. Gregersen, K. H. Røed, V. Eisenmann, C. J. Rubin, D. C. Miller, D. F. Antczak, M. F. Bertelsen, S. Brunak, K. A. Al-Rasheid, O. Ryder, L. Andersson, J. Mundy, A. Krogh, M. T. Gilbert, K. Kjær, T. Sicheritz-Ponten, L. J. Jensen, J. V. Olsen, M. Hofreiter, R. Nielsen, B. Shapiro, J. Wang, E. Willerslev, Recalibrating Equus evolution using the genome sequence of an early Middle Pleistocene horse. Nature 499, 74–78 (2013).

  32. M. Meyer, M. Kircher, Illumina sequencing library preparation for highly multiplexed target capture and sequencing. Cold Spring Harb. Protoc. 2010, pdb.prot5448 (2010).

  33. M. Kircher, S. Sawyer, M. Meyer, Double indexing overcomes inaccuracies in multiplex sequencing on the Illumina platform. Nucleic Acids Res. 40, e3 (2012).

  34. W. Briggs, U. Stenzel, M. Meyer, J. Krause, M. Kircher, S. Pääbo, Removal of deaminated cytosines and detection of in vivo methylation in ancient DNA. Nucleic Acids Res. 38, e87 (2010).

  35. E. Hodges, Z. Xuan, V. Balija, M. Kramer, M. N. Molla, S. W. Smith, C. M. Middle, M. J. Rodesch, T. J. Albert, G. J. Hannon, W. R. McCombie, Genome-wide in situ exon capture for selective resequencing. Nat. Genet. 39, 1522–1527 (2007).

  36. T. Maricic, M. Whitten, S. Pääbo, Multiplexed DNA sequence capture of mitochondrial genomes using PCR products. PLoS ONE 5, e14004 (2010).

  37. M. Kircher, U. Stenzel, J. Kelso, Improved base calling for the Illumina Genome Analyzer using machine learning strategies. Genome Biol. 10, R83 (2009).

  38. R. E. Green, A. S. Malaspinas, J. Krause, A. W. Briggs, P. L. Johnson, C. Uhler, M. Meyer, J. M. Good, T. Maricic, U. Stenzel, K. Prüfer, M. Siebauer, H. A. Burbano, M. Ronan, J. M. Rothberg, M. Egholm, P. Rudan, D. Brajkovi?, Z. Ku?an, I. Gusi?, M. Wikström, L. Laakkonen, J. Kelso, M. Slatkin, S. Pääbo, A complete Neandertal mitochondrial genome sequence determined by high-throughput sequencing. Cell 134, 416–426 (2008).

  39. J. Sambrook, E. F. Fritsch, T. Maniatis, Molecular Cloning: A Laboratory Manual (Cold Spring Harbor Laboratory Press, Cold Spring Harbor, New York, ed. 2, 1989).

  40. M. Meyer, U. Stenzel, M. Hofreiter, Parallel tagged sequencing on the 454 platform. Nat. Protoc. 3, 267–278 (2008).

  41. M. Meyer, A. W. Briggs, T. Maricic, B. Höber, B. Höffner, J. Krause, A. Weihmann, S. Pääbo, M. Hofreiter, From micrograms to picograms: Quantitative PCR reduces the material demands of high-throughput sequencing. Nucleic Acids Res. 36, e5 (2008).

  42. U. Arnason, A. Gullberg, A. Janke, M. Kullberg, Mitogenomic analyses of caniform relationships. Mol. Phylogenet. Evol. 45, 863–874 (2007).

  43. K. Katoh, K. Kuma, H. Toh, T. Miyata, MAFFT version 5: Improvement in accuracy of multiple sequence alignment. Nucleic Acids Res. 33, 511–518 (2005).

  44. T. A. Hall, BioEdit: A user-friendly biological sequence alignment editor and analysis program for Windows 95/98/NT. Nucleic Acids Symp. Ser. 41, 95 (1999).

  45. P. Savolainen, L. Arvestad, J. Lundeberg, mtDNA tandem repeats in domestic dogs and wolves: Mutation mechanism studied by analysis of the sequence of imperfect repeats. Mol. Biol. Evol. 17, 474–488 (2000).

  46. H. A. Schmidt, K. Strimmer, M. Vingron, A. von Haeseler, TREE-PUZZLE: Maximum likelihood phylogenetic analysis using quartets and parallel computing. Bioinformatics 18, 502–504 (2002).

  47. M. Hasegawa, H. Kishino, T. Yano, Dating of the human-ape splitting by a molecular clock of mitochondrial DNA. J. Mol. Evol. 22, 160–174 (1985).

  48. B. Q. Minh, M. A. T. Nguyen, A. von Haeseler, Ultrafast approximation for phylogenetic bootstrap. Mol. Biol. Evol. 30, 1188–1195 (2013).

  49. D. Darriba, G. L. Taboada, R. Doallo, D. Posada, jModelTest 2: More models, new heuristics and parallel computing. Nat. Methods 9, 772 (2012).

  50. H. Akaike, in Proceedings of the Second International Symposium on Information Theory, Tsahkadsor, Armenia, [dates], N. Petrov and S. Caski, Eds. (Akadeniai Kiado, Budapest, 1973), pp. 267–281.

  51. F. Ronquist, M. Teslenko, P. van der Mark, D. L. Ayres, A. Darling, S. Höhna, B. Larget, L. Liu, M. A. Suchard, J. P. Huelsenbeck, MrBayes 3.2: Efficient Bayesian phylogenetic inference and model choice across a large model space. Syst. Biol. 61, 539–542 (2012).

  52. W. Xie, P. O. Lewis, Y. Fan, L. Kuo, M.-H. Chen, Improving marginal likelihood estimation for Bayesian phylogenetic model selection. Syst. Biol. 60, 150–160 (2011).

  53. P. Librado, J. Rozas, DnaSP v5: A software for comprehensive analysis of DNA polymorphism data. Bioinformatics 25, 1451–1452 (2009).

  54. C. Meng, H. Zhang, Q. Meng, Mitochondrial genome of the Tibetan wolf. Mitochondrial DNA 20, 61–63 (2009).

  55. J. Drummond, M. A. Suchard, D. Xie, A. Rambaut, Bayesian phylogenetics with BEAUti and the BEAST 1.7. Mol. Biol. Evol. 29, 1969–1973 (2012).

  56. Shapiro, A. Rambaut, A. J. Drummond, Choosing appropriate substitution models for the phylogenetic analysis of protein-coding sequences. Mol. Biol. Evol. 23, 7–9 (2006).

  57. J. Drummond, S. Y. Ho, M. J. Phillips, A. Rambaut, Relaxed phylogenetics and dating with confidence. PLoS Biol. 4, e88 (2006).

  58. Rambaut, A. Drummond, Tracer, version 1.4, Computer program and documentation distributed by the author; http://beast.bio.ed.ac.uk/Tracer (2007).

  59. R. E. Green, J. Krause, A. W. Briggs, T. Maricic, U. Stenzel, M. Kircher, N. Patterson, H. Li, W. Zhai, M. H. Fritz, N. F. Hansen, E. Y. Durand, A. S. Malaspinas, J. D. Jensen, T. Marques-Bonet, C. Alkan, K. Prüfer, M. Meyer, H. A. Burbano, J. M. Good, R. Schultz, A. Aximu-Petri, A. Butthof, B. Höber, B. Höffner, M. Siegemund, A. Weihmann, C. Nusbaum, E. S. Lander, C. Russ, N. Novod, J. Affourtit, M. Egholm, C. Verna, P. Rudan, D. Brajkovic, Z. Kucan, I. Gusic, V. B. Doronichev, L. V. Golovanova, C. Lalueza-Fox, M. de la Rasilla, J. Fortea, A. Rosas, R. W. Schmitz, P. L. Johnson, E. E. Eichler, D. Falush, E. Birney, J. C. Mullikin, M. Slatkin, R. Nielsen, J. Kelso, M. Lachmann, D. Reich, S. Pääbo, A draft sequence of the Neandertal genome. Science 328, 710–722 (2010).

  60. S. Sawyer, J. Krause, K. Guschanski, V. Savolainen, S. Pääbo, Temporal patterns of nucleotide misincorporations and DNA fragmentation in ancient DNA. PLoS ONE 7, e34131 (2012).

  61. M. Hofreiter, V. Jaenicke, D. Serre, A. von Haeseler, S. Pääbo, DNA sequences from multiple amplifications reveal artifacts induced by cytosine deamination in ancient DNA. Nucleic Acids Res. 29, 4793–4799 (2001).

  62. M. Stiller, R. E. Green, M. Ronan, J. F. Simons, L. Du, W. He, M. Egholm, J. M. Rothberg, S. G. Keates, N. D. Ovodov, E. E. Antipina, G. F. Baryshnikov, Y. V. Kuzmin, A. A. Vasilevski, G. E. Wuenschell, J. Termini, M. Hofreiter, V. Jaenicke-Després, S. Pääbo, Patterns of nucleotide misincorporations during enzymatic amplification and direct large-scale sequencing of ancient DNA. Proc. Natl. Acad. Sci. U.S.A. 103, 13578–13584 (2006).

  63. J.-F. Pang, C. Kluetsch, X. J. Zou, A. B. Zhang, L. Y. Luo, H. Angleby, A. Ardalan, C. Ekström, A. Sköllermo, J. Lundeberg, S. Matsumura, T. Leitner, Y. P. Zhang, P. Savolainen, mtDNA data indicate a single origin for dogs south of Yangtze River, less than 16,300 years ago, from numerous wolves. Mol. Biol. Evol. 26, 2849–2864 (2009).

  64. S. Björnerfeldt, M. T. Webster, C. Vilà, Relaxation of selective constraint on dog mitochondrial DNA following domestication. Genome Res. 16, 990–994 (2006).

  65. M. Hofreiter, D. Serre, H. N. Poinar, M. Kuch, S. Pääbo, Ancient DNA. Nat. Rev. Genet. 2, 353–359 (2001).

  66. R. E. Green, A. W. Briggs, J. Krause, K. Prüfer, H. A. Burbano, M. Siebauer, M. Lachmann, S. Pääbo, The Neandertal genome and ancient DNA authenticity. EMBO J. 28, 2494–2502 (2009).

  67. R. E. Green, J. Krause, S. E. Ptak, A. W. Briggs, M. T. Ronan, J. F. Simons, L. Du, M. Egholm, J. M. Rothberg, M. Paunovic, S. Pääbo, Analysis of one million base pairs of Neanderthal DNA. Nature 444, 330–336 (2006).

  68. J. D. Wall, S. K. Kim, Inconsistencies in Neanderthal genomic DNA sequences. PLoS Genet. 3, 1862–1866 (2007).

  69. W. Briggs, J. M. Good, R. E. Green, J. Krause, T. Maricic, U. Stenzel, C. Lalueza-Fox, P. Rudan, D. Brajkovic, Z. Kucan, I. Gusic, R. Schmitz, V. B. Doronichev, L. V. Golovanova, M. de la Rasilla, J. Fortea, A. Rosas, S. Pääbo, Targeted retrieval and analysis of five Neandertal mtDNA genomes. Science 325, 318–321 (2009).

  70. J. A. Leonard, O. Shanks, M. Hofreiter, E. Kreuz, L. Hodges, W. Ream, R. K. Wayne, R. C. Fleischer, Animal DNA in PCR reagents plagues ancient DNA research. J. Archaeol. Sci. 34, 1361–1366 (2007).

  71. K. Strimmer, A. von Haeseler, Likelihood-mapping: A simple method to visualize phylogenetic content of a sequence alignment. Proc. Natl. Acad. Sci. U.S.A. 94, 6815–6819 (1997).

  72. S. Druzhkova, O. Thalmann, V. A. Trifonov, J. A. Leonard, N. V. Vorobieva, N. D. Ovodov, A. S. Graphodatsky, R. K. Wayne, Ancient DNA analysis affirms the canid from Altai as a primitive dog. PLoS ONE 8, e57754 (2013).

  73. Acosta, D. Loponte, C. G. Esponda, Primer registro de perro doméstico prehispánico (Canis familiaris) entre los grupos cazadores recolectores del humedal de Paraná inferior (Argentina). Antipod. Rev. Antropol. Arqueol. 13, 175–199 (2011).

  74. E. Worthington, thesis, Florida State University (2008).

  75. M. Nei, Molecular Evolutionary Genetics (Columbia Univ. Press, New York, 1987).

  76. G. A. Watterson, On the number of segregating sites in genetical models without recombination. Theor. Popul. Biol. 7, 256–276 (1975).

  77. F. Tajima, Statistical method for testing the neutral mutation hypothesis by DNA polymorphism. Genetics 123, 585–595 (1989).

  78. Y. X. Fu, W. H. Li, Statistical tests of neutrality of mutations. Genetics 133, 693–709 (1993).

Acknowledgments: Mitochondrial sequences have been deposited at the NCBI database with the accession numbers (KF661036 to KF661096), and a complete alignment is available as a supplementary file. We would like to thank all colleagues who provided samples for this study, the Illinois State Museum and the Center for American Archeology for allowing us to sample the material from the Koster site, and the American Museum of Natural History, New York. O.T. is grateful to D. Wegmann and D. Schwochow-Thalmann for helpful discussions and comments on the manuscript; M. Bruneaux for help with R; and A. v. Haeseler for helpful advice with TREE-PUZZLE and IQ-TREE. We thank D. Ward, M. Riesenberg, J. Beier, I. Bergmann, H. Mutlu, and S. Bealek for assistance with ancient DNA extractions. R.E.G. is president of Dovetail Genomics. Financial support for this study was provided from the E. Aaltonen foundation and the Turun Yliopistosäätiö to O.T.; Molecular and Cellular Biology, Siberian Branch of the Russian Academy of Sciences, and Russian Foundation for Basic Research grants to A.S.G.; and NSF support to R.K.W. and B.S. (OPP 9617068, EF-1021387). J.K. and V.J.S. were supported by the Carl Zeiss Foundation. This work was further supported by the Max Planck Society. O.T. is financed by a Marie Curie Intra European Fellowship within the 7th European Community Framework Program. The authors declare no conflict of interest.