Deciphering past human population movements in Oceania: provably optimal trees of 127 mtDNA genomes

Abstract

The settlement of the many island groups of Remote Oceania occurred relatively late in prehistory, beginning approximately 3,000 years ago when people sailed eastwards into the Pacific from Near Oceania, where evidence of human settlement dates from as early as 40,000 years ago. Archeological and linguistic analyses have suggested the settlers of Remote Oceania had ancestry in Taiwan, as descendants of a proposed Neolithic expansion that began approximately 5,500 years ago. Other researchers have suggested that the settlers were descendants of peoples from Island Southeast Asia or the existing inhabitants of Near Oceania alone. To explore patterns of maternal descent in Oceania, we have assembled and analyzed a data set of 137 mitochondrial DNA (mtDNA) genomes from Oceania, Australia, Island Southeast Asia, and Taiwan that includes 19 sequences generated for this project. Using the MinMax Squeeze Approach (MMS), we report the consensus network of 165 most parsimonious trees for the Oceanic data set, increasing by many orders of magnitude the numbers of trees for which a provable minimal solution has been found. The new mtDNA sequences highlight the limitations of partial sequencing for assigning sequences to haplogroups and dating recent divergence events. The provably optimal trees found for the entire mtDNA sequences using the MMS method provide a reliable and robust framework for the interpretation of evolutionary relationships and confirm that the female settlers of Remote Oceania descended from both the existing inhabitants of Near Oceania and more recent migrants into the region.

Fig. 1

Map of Oceania. Dates provided are the earliest archeological evidence of anatomically modern human settlement (O'Connell and Allen 2004). Sources of new mtDNA sequences are numbered as follows: 1, Taiwan; 2, Trobriand Islands; 3, Kapingamarangi Atoll; 4, Majuro Atoll; 5, Vanuatu; 6, Tonga; 7, Samoa; and 8, Cook Islands.

Fig. 2

Oceania data set consensus networks. (a) Consensus of 582,624 most parsimonious trees found by heuristic search; upper bound 412, lower bound 410. The entire coding region (282 parsimony-informative characters) of the mtDNA sequence of 127 haplotypes was analyzed. The 2 major areas of conflict among the trees at the M and N/R vertices are enlarged. (b) Consensus network of 165 provably optimal trees found by heuristic search when 2 characters—nt1598 and nt10398—were excluded from the analysis. The MMS guarantees the heuristic search score of 399 to be minimal. Sequences reported here are shown in bold; haplogroups are labeled according to existing nomenclature. The N/R/B4a1a haplogroup is highlighted in green.

Fig. 3

B4a consensus network and B4a1a base-labeled phylogeny. (a) The consensus network of 1,274 provably optimal trees (57 parsimony-informative characters over complete mtDNA sequence, parsimony score 87) found by heuristic search on the N/R/B4a haplogroup data set of 47 sequences including L3 outgroup (AF347014). Sequences in B4a2 are from Taiwan and Japan, B4a1b sequences are from Japan and Korea, and B4a1c sequences are from Japan and Siberia. All B4a1a sequences are from Taiwan and Oceania. Sequences from this study are shown in bold type. (b) A base-labeled phylogeny reconstructed from the consensus network for B4a1a sequences. Length variations in the poly-C region from nt303 to nt315 are not shown. Substitutions are transitions to the base shown, unless marked “tvN,” where N is the base in the rCRS. Synonymous substitutions are shown in red type, and sites that change more than once within a lineage in the labeled phylogeny are followed by the number of the change in brackets. When a substitution results in the same nucleotide as in the rCRS, it is shown in italics. The polymorphisms relative to the rCRS at the N/R vertex are: 73G, 263G, 750G, 1438G, 2706G, 3106del, 4769G, 7028T, 8860G, 11719A, 14766T, and 15326G. The conflicts between the trees seen in the consensus network have been resolved here by invoking a reversion at nt16247 from G to A in sequence AY289093. Other positions causing conflict in the phylogeny shown are nt16129 (AJ842746 and DQ372873) and nt16093 (AJ842744 and AY289083).