(a) Mastodon shotgun 454 sequencing. We ligated 454-adaptors (green and blue) to the ends of the DNA molecules and sequenced the libraries on a Roche 454 GS. (b) Bioinformatic analysis of shotgun 454 sequences. To identify proboscidean sequence, we compared the sequences to databases consisting of the savanna elephant draft genome (loxAfr1), the human genome (hg18), the mouse genome (mm8), NCBI's nucleotide database of environmental samples (env), and NCBI's non-redundant nucleotide database (nr). The 454 sequences with a best match to loxAfr1 (in red) were aligned to loxAfr1. Alignments of at least 90 bp in length and with a similarity higher than 87% were used for primer design after filtering out known repeat elements (using the UCSC RepeatMasker database). Primers were based on loxAfr1 sequence flanking the mastodon sequence. (c) Multiplex PCR and sequencing of the targeted loci in modern elephants and mammoth. We show the protocol for the first of four rounds of the project (Table S3 provides details of the further rounds). A total of 213 primer pairs were randomly divided into 5 multiplex primer mixes with 41–44 primer pairs per mix. These mixes were used for the first step of the two-step multiplex PCR approach, for each of the 5 samples (La, Loxodonta africana; Lc, L. cyclotis; Em 1, Elephas maximus 1; Em 2, E. maximus 2; Mp, Mammuthus primigenius). Dilutions of these products were used as templates to amplify the loci individually in the second step (shown for L. africana), resulting in 213 distinct products per sample. These products were quantified, normalized, and merged into one pool per sample. A 454 library was prepared and sequenced on 1/16^th of a picotiter plate of a Roche 454 GS.

Demographic model that is fit by MCMCcoal, in which all population splits are instantaneous (without subsequent gene flow), and all population sizes are assumed to be constant over intervals. Here, T_FS refers to forest-savanna elephant population divergence time, T_AM refers to Asian elephant-mammoth population divergence time, T_Lox-Eur refers to African-Eurasian population divergence time, and T_{Elephantid-Mastodon} refers to elephantid-mastodon population divergence time, presented here in millions of years. The Ν quantities refer to constant diploid effective population sizes ancestral to each of these splits (in thousands). For obtaining estimates of years and population sizes, we assume that the elephantids have an average of 31 years per generation, based on estimates of 17–20 years for females [53],[54] and 40–49 years for males [43],[55]. A lower or higher number of years per generation would produce a proportionate effect on the population size estimates. For each parameter, two sets of numbers are shown. The upper set shows the range consistent with the fossil record, calibrating to an assumed African-Eurasian population split of T_Lox-Eur = 4.2–9 Mya (justified in Text S5). For example for forest-savanna population divergence, this leads to T_FS = 2.6–5.6 Mya given that MCMCcoal estimates T_FS/T_Lox-Eur = 62%. The lower set of numbers (in parentheses) provides MCMCcoal's 90% credible interval for the parameters as a fraction of the best estimate (e.g. 76%–126% for T_FS). In the main text, we conservatively quote a range that combines the uncertainty from the fossil record and from MCMCcoal (e.g. T_FS = 1.9–7.1 Mya).