# The Geography of Recent Genetic Ancestry across Europe.

Peter Ralph1 and Graham Coop2
1 Department of Evolution and Ecology & Center for Population Biology,
University of California, Davis.
2 Department of Molecular and Computational Biology,
University of Southern California.
To whom correspondence should be addressed:
plralph<EMAIL_ADDRESS>

## Abstract

The recent genealogical history of human populations is a complex mosaic
formed by individual migration, large-scale population movements, and other
demographic events. Population genomics datasets can provide a window into
this recent history, as rare traces of recent shared genetic ancestry are
detectable due to long segments of shared genomic material. We make use of
genomic data for 2257 Europeans (in the POPRES dataset) to conduct one of the
first surveys of recent genealogical ancestry over the past three thousand
years at a continental scale.

We detected 1.9 million shared long genomic segments, and used the lengths of
these to infer the distribution of shared ancestors across time and geography.
We find that a pair of modern Europeans living in neighboring populations
share around 2–12 genetic common ancestors from the last 1500 years, and
upwards of 100 genetic ancestors from the previous 1000 years. These numbers
drop off exponentially with geographic distance, but since these genetic
ancestors are a tiny fraction of common genealogical ancestors, individuals
from opposite ends of Europe are still expected to share millions of common
genealogical ancestors over the last 1000 years. There is also substantial
regional variation in the number of shared genetic ancestors. For example,
there are especially high numbers of common ancestors shared between many
eastern populations which date roughly to the migration period (which includes
the Slavic and Hunnic expansions into that region). Some of the lowest levels
of common ancestry are seen in the Italian and Iberian peninsulas, which may
indicate different effects of historical population expansions in these areas
and/or more stably structured populations.

Population genomic datasets have considerable power to uncover recent
demographic history, and will allow a much fuller picture of the close
genealogical kinship of individuals across the world.

## Author Summary

Few of us know our family histories more than a few generations back.
Therefore, it is easy to overlook the fact that we are all distant cousins,
related to one another via a vast network of relationships. Here we use
genome-wide data from European individuals to investigate these relationships
over the past three thousand years, by looking for long stretches of shared
genome between pairs of individuals inherited from common genetic ancestors.
We quantify this ubiquitous recent common ancestry, showing that for instance
even pairs of individuals on opposite ends of Europe share hundreds of genetic
common ancestors over this time period. Despite this degree of commonality,
there are also striking regional differences. For instance, southeastern
Europeans share large numbers of common ancestors which date to the era of the
Slavic and Hunnic expansions around 1500 years ago, while most common
ancestors that Italians share with other populations lived longer ago than
2500 years. The study of long stretches of shared genetic material holds the
promise of rich information about many aspects of recent population history.

##  1 Introduction

Even seemingly unrelated humans are distant cousins to each other, as all
members of a species are related to each other through a vastly ramified
family tree (their pedigree). We can see traces of these relationships in
genetic data when individuals inherit shared genetic material from a common
ancestor. Traditionally, population genetics has studied the distant bulk of
these genetic relationships, which in humans typically date from hundreds of
thousands of years ago (e.g. Cann et al., 1987; Takahata, 1993). Such studies
have provided deep insights into the origins of modern humans (e.g. Li and
Durbin, 2011), and into recent admixture between diverged populations (e.g.
Moorjani et al., 2011; Henn et al., 2012a).

Although most such genetic relationships among individuals are very old, some
individuals are related on far shorter time scales. Indeed, given that each
individual has $2^{n}$ ancestors from $n$ generations ago, theoretical
considerations suggest that all humans are related genealogically to each
other over surprisingly short time scales (Chang, 1999; Rohde et al., 2004).
We are usually unaware of these close genealogical ties, as few of us have
knowledge of family histories more than a few generations back, and these
ancestors often do not contribute any genetic material to us (Donnelly, 1983).
However, in large samples we can hope to identify genetic evidence of more
recent relatedness, and so obtain insight into the population history of the
past tens of generations. Here we investigate such patterns of recent
relatedness in a large European dataset.

The past several thousand years are replete with events that may have had
significant impact on modern European relatedness, such as the Neolithic
expansion of farming, the Roman empire, or the more recent expansions of the
Slavs and the Vikings.

Our current understanding of these events is deduced from archaeological,
linguistic, cultural, historical, and genetic evidence, with widely varying
degrees of certainty. However, the demographic and genealogical impact of
these events is still uncertain (e.g. Gillett, 2006). Genetic data describing
the breadth of genealogical relationships can therefore add another dimension
to our understanding of these historical events.

Work from uniparentally inherited markers (mtDNA and Y chromosomes) has
improved our understanding of human demographic history (e.g. Soares et al.,
2010). However, interpretation of these markers is difficult since they only
record a single lineage of each individual (the maternal and paternal
lineages, respectively), rather than the entire distribution of ancestors.
Genome-wide genotyping and sequencing datasets have the potential to provide a
much richer picture of human history, as we can learn simultaneously about the
diversity of ancestors that contributed to each individual’s genome.

A number of genome-wide studies have begun to reveal quantitative insights
into recent human history (Novembre and Ramachandran, 2011). Within Europe,
the first two principal axes of variation of the matrix of genotypes are
closely related to a rotation of latitude and longitude (Menozzi et al., 1978;
Novembre et al., 2008; Lao et al., 2008), as would be expected if patterns of
ancestry are mostly shaped by local migration (Novembre and Stephens, 2008).
Other work has revealed a slight decrease in diversity running from south-to-
north in Europe, with the highest haplotype and allelic diversity in the
Iberian peninsula (e.g. Lao et al., 2008; Auton et al., 2009; Nelson et al.,
2012), and the lowest haplotype diversity in England and Ireland (O’Dushlaine
et al., 2010). Recently, progress has also been made using genotypes of
ancient individuals to understand the prehistory of Europe (Patterson et al.,
2012; Skoglund et al., 2012; Keller et al., 2012). However, we currently have
little sense of the time scale of the historical events underlying modern
geographic patterns of relatedness, nor the degrees of genealogical
relatedness they imply.

In this paper, we analyze those rare long chunks of genome that are shared
between pairs of individuals due to inheritance from recent common ancestors,
to obtain a detailed view of the geographic structure of recent relatedness.
To determine the time scale of these relationships, we develop methodology
that uses the lengths of shared genomic segments to infer the distribution of
the ages of these recent common ancestors. We find that even geographically
distant Europeans share ubiquitous common ancestry even within the past 1000
years, and show that common ancestry from the past 3000 years is a result of
both local migration and large-scale historical events. We find considerable
structure below the country level in sharing of recent ancestry, lending
further support to the idea that looking at runs of shared ancestry can
identify very subtle population structure (e.g. Lawson et al., 2012).

Our method for inferring ages of common ancestors is conceptually similar to
the work of Palamara et al. (2012), who use total amount of long runs of
shared genome to fit simple parametric models of recent history, as well as to
Li and Durbin (2011) and Harris and Nielsen (2012), who use information from
short runs of shared genome to infer demographic history over much longer time
scales. Other conceptually similar work includes Pool and Nielsen (2009) and
Gravel (2012), who used the length distribution of admixture tracts to fit
parametric models of historical admixture. We rely less on discrete, idealized
populations or parametric demographic models than these other works, and
describe continuous geographic structure by obtaining average numbers of
common ancestors shared by many populations across time in a relatively non-
parametric fashion.

###  1.1 Definitions: Genetic ancestry and identity by descent

Figure 1:  (A) A hypothetical portion of the pedigree relating two sampled
individuals, which shows six of their genealogical common ancestors, with the
portions of ancestral chromosomes from which the sampled individuals have
inherited shaded grey. The IBD blocks they have inherited from the two genetic
common ancestors are colored red, and the blue arrow denotes the path through
the pedigree along which one of these IBD blocks was inherited. (B) Cartoon of
the spatial locations of ancestors of two individuals – circle size is
proportional to likelihood of genetic contribution, and shared ancestors are
marked in grey. Note that common ancestors are likely located between the two,
and their distribution becomes more diffuse further back in time.

We can only hope to learn from genetic data about those common ancestors from
whom two individuals have both inherited the same genomic region. If a pair of
individuals have both inherited some genomic region from a common ancestor,
that ancestor is called a “genetic common ancestor”, and the genomic region is
shared “identical by descent” (IBD) by the two. Here we define an “IBD block”
to be a contiguous segment of genome inherited (on at least one chromosome)
from a shared common ancestor without intervening recombination (see figure
1A). A more usual definition of IBD restricts to those segments inherited from
some prespecified set of “founder” individuals (e.g. Fisher, 1954; Donnelly,
1983; Chapman and Thompson, 2002), but we allow ancestors to be arbitrarily
far back in time. Under our definition, everyone is IBD everywhere, but mostly
on very short, old segments (Powell et al., 2010). We measure lengths of IBD
segments in units of Morgans (M) or centiMorgans (cM), where 1 Morgan is
defined to be the distance over which an average of one recombination (i.e. a
crossover) occurs per meiosis. Segments of IBD are broken up over time by
recombination, which implies that older shared ancestry tends to result in
shorter shared IBD blocks.

Sufficiently long segments of IBD can be identified as long, contiguous
regions over which the two individuals are identical (or nearly identical) at
a set of Single Nucleotide Polymorphisms (SNPs) which segregate in the
population. Formal, model-based methods to infer IBD are only computationally
feasible for very recent ancestry (e.g. Brown et al., 2012), but recently,
fast heuristic algorithms have been developed that can be applied to thousands
of samples typed on genotyping chips (e.g. Browning and Browning, 2011; Gusev
et al., 2009).

The relationship between numbers of long, shared segments of genome, numbers
of genetic common ancestors, and numbers of genealogical common ancestors can
be difficult to envision. Since everyone has exactly two biological parents,
every individual has exactly $2^{n}$ paths of length $n$ meioses leading back
through their pedigree, each such path ending in a grandn-1parent. However,
due to Mendelian segregation and limited recombination, genetic material will
only be passed down along a small subset of these paths (Donnelly, 1983). As
$n$ grows, these paths proliferate rapidly and so the genealogical paths of
two individuals soon overlap significantly. (These points are illustrated in
in figure 1.) By observing the number of shared genomic blocks, we learn about
the degree to which their genealogies overlap, or the number of common
ancestors from which both individuals have inherited genetic material.

At least one parent of each genetic common ancestor of two individuals is also
a genetic common ancestor, so the number of genetic common ancestors at each
point back in time is strictly increasing. A more relevant quantity is the
rate of appearance of most recent common genetic ancestors. This quantity can
be much more intuitive, and is closely related to the coalescent rate (Hudson,
1990), as we demonstrate later. For this reason, when we say “genetic common
ancestor” or “rate of genetic common ancestry”, we are referring to only the
most recent genetic common ancestors from which the individuals in question
inherited their shared segments of genome.

##  2 Results

We applied the fastIBD method, implemented in BEAGLE v3.3 (Browning and
Browning, 2011), to the European subset of the POPRES dataset (dbgap accession
phs000145.v1.p1, Nelson et al., 2008), which includes language and country-of-
origin data for several thousand Europeans genotyped at 500000 SNPs. Our
simulations showed that we have good power to detect long IBD blocks
(probability of detection 50% for blocks longer than 2cM, rising to 98% for
blocks longer than 4cM), and a low false positive rate (discussed further in
section 4.2 of the methods). We excluded from our analyses individuals who
reported grandparents originating from non-European countries or more than one
distinct country (and refer to the remainder as “Europeans”). After removing
obvious outlier individuals and close relatives, we were left with 2257
individuals who we grouped using reported country of origin and language into
40 populations, listed with sample sizes and average IBD levels in table 1.
For geographic analyses, we located each population at the largest population
city in the appropriate region. Pairs of individuals in this dataset were
found to share a total of 1.9 million segments of IBD, an average of 0.74 per
pair of individuals, or 831 per individual. The mean length of these blocks
was 2.5cM, the median was 2.1cM and the 25th and 75th quantiles are 1.5cM and
2.9cM respectively. The majority of pairs sharing some IBD shared only a
single block of IBD (94%). The total length of IBD blocks an individual shares
with all others ranged between 30% and 250% (average 128%) of the length of
the genome (greater than 100% is possible as individuals may share IBD blocks
with more than one other at the same genomic location).

E group | $n$ | self | other | N group | $n$ | self | other
---|---|---|---|---|---|---|---
Albania | AL | 9 | 14.5 | 1.7 | Denmark | DK | 1 | – | 0.9
Austria | AT | 14 | 1.3 | 0.9 | Finland | FI | 1 | – | 1.2
Bosnia | BO | 9 | 4.1 | 1.6 | Latvia | LV | 1 | – | 1.6
Bulgaria | BG | 1 | – | 1.3 | Norway | NO | 2 | 2.0 | 0.8
Croatia | HR | 9 | 2.8 | 1.6 | Sweden | SE | 10 | 3.4 | 1.0
Czech Republic | CZ | 9 | 2.1 | 1.3 |  |  |  |  |
Greece | EL | 5 | 1.8 | 0.9 | W group | $n$ | self | other
Hungary | HU | 19 | 1.9 | 1.2 | Belgium | BE | 37 | 1.1 | 0.6
Kosovo | KO | 15 | 9.9 | 1.7 | England | EN | 22 | 1.3 | 0.7
Montenegro | ME | 1 | – | 1.8 | France | FR | 86 | 0.7 | 0.5
Macedonia | MA | 4 | 2.5 | 1.4 | Germany | DE | 71 | 1.1 | 0.9
Poland | PL | 22 | 3.8 | 1.5 | Ireland | IE | 60 | 2.6 | 0.6
Romania | RO | 14 | 2.1 | 1.2 | Netherlands | NL | 17 | 1.9 | 0.7
Russia | RU | 6 | 4.3 | 1.4 | Scotland | SC | 5 | 2.2 | 0.7
Slovenia | SI | 2 | 5.0 | 1.3 | Swiss French | CHf | 839 | 1.3 | 0.6
Serbia | RS | 11 | 2.7 | 1.5 | Swiss German | CHd | 103 | 1.6 | 0.6
Slovakia | SK | 1 | – | 0.7 | Switzerland | CH | 17 | 1.1 | 0.5
Ukraine | UA | 1 | – | 1.5 | United Kingdom | UK | 358 | 1.2 | 0.7
Yugoslavia | YU | 10 | 3.4 | 1.5 |  |  |  |  |
|  |  |  |  | I group | $n$ | self | other
TC group | $n$ | self | other | Italy | IT | 213 | 0.6 | 0.5
Cyprus | CY | 3 | 2.7 | 0.4 | Portugal | PT | 115 | 1.9 | 0.5
Turkey | TR | 4 | 2.2 | 0.5 | Spain | ES | 130 | 1.5 | 0.4
Table 1:  Populations, abbreviations, sample sizes ($n$), mean number of IBD
blocks shared by a pair of individuals from that population (“self”), and mean
IBD rate averaged across all other populations (“other”); sorted by regional
groupings described in the text.

The observed genomic density of long IBD blocks (per cM) can be affected by
recent selection (Albrechtsen et al., 2010) and by cis-acting recombination
modifiers. We find that the local density of IBD blocks of all lengths is
relatively constant across the genome, but in certain regions the length
distribution is systematically perturbed (see supplemental figure S1),
including around certain centromeres and the large inversion on chromosome 8
(Giglio et al., 2001), also seen by Albrechtsen et al. (2010). Somewhat
surprisingly, the MHC does not show an unusual pattern of IBD, despite having
shown up in other genomic scans for IBD (Albrechtsen et al., 2010; Gusev et
al., 2012). However, there are a few other regions where differences in IBD
rate are not predicted by differences in SNP density. Notably, there are two
regions, on chromosomes 15 and 16, which are nearly as extreme in their
deviations in IBD as the inversion on chromosome 8, and may also correspond to
large inversions segregating in the sample. These only make up a small portion
of the genome, and do not significantly affect our other analyses (and so are
not removed); we leave further analysis for future work.

###  2.1 Substructure and recent migrants

We should expect significant within-population variability, as modern
countries are relatively recent constructions of diverse assemblages of
languages and heritages. To assess the uniformity of ancestry within
populations, we used a permutation test to measure, for each pair of
populations $x$ and $y$, the uniformity with which relationships with $x$ are
distributed across individuals from $y$. Most comparisons show statistically
significant heterogeneity (supplemental figure S2), which is probably due to
population substructure (as well as correlations introduced by the pedigree).
A notable exception is that nearly all populations showed no significant
heterogeneity of numbers of common ancestors with Italian samples, suggesting
that most common ancestors shared with Italy lived longer ago than the time
that structure within modern-day countries formed.

Figure 2:  Substructure, in (A) Italian, and (B) UK samples. The leftmost
plots of (A) show histograms of the numbers of IBD blocks that each Italian
sample shares with any French-speaking Swiss (top) and anyone from the UK
(bottom), overlaid with the expected distribution (Poisson) if there was no
dependence between blocks. Next is shown a scatterplot of numbers of blocks
shared with French-speaking Swiss and UK samples, for all samples from France,
Italy, Greece, Turkey, and Cyprus. We see that the numbers of recent ancestors
each Italian shares with the French-speaking Swiss and with the United Kingdom
are both bimodal, and that these two are positively correlated, ranging
continuously between values typical for Turkey/Cyprus and for France. Figure
(B) is similar, showing that the substructure within the UK is part of a
continuous trend ranging from Germany to Ireland. The outliers visible in the
scatterplot of figure 2B are easily explained as individuals with immigrant
recent ancestors – the three outlying UK individuals in the lower left share
many more blocks with Italians than all other UK samples, and the individual
labeled “SK” is a clear outlier for the number of blocks shared with the
Slovakian sample.

Two of the more striking examples of substructure are illustrated in figure 2.
Here, we see that variation within countries can be reflective of continuous
variation in ancestry that spans a broader geographic region, crossing
geographic, political, and linguistic boundaries. Figure 2A shows the
distinctly bimodal distribution of numbers of IBD blocks that each Italian
shares with both French-speaking Swiss and the UK, and that these numbers are
strongly correlated. Furthermore, the amount that Italians share with these
two populations varies continuously from values typical for Turkey and Cyprus,
to values typical for France and Switzerland. Interestingly, the Greek samples
(EL) place near the middle of the Italian gradient. It is natural to guess
that there is a north-south gradient of recency of common ancestry along the
length of Italy, and that southern Italy has been historically more closely
connected to the eastern Mediterranean.

In contrast, within samples from the UK and nearby regions we see negative
correlation between numbers of blocks shared with Irish and numbers of blocks
shared with Germans. From our data, we do not know if this substructure is
also geographically arranged within the UK (our sample of which which may
include individuals from Northern Ireland). However, an obvious explanation of
this pattern is that individuals within the UK differ in the number of recent
ancestors shared with Irish, and that individuals with less Irish ancestry
have a larger portion of their recent ancestry shared with Germans. This
suggests that there is variation across the UK – perhaps a geographic gradient
– in terms of the amount of Celtic versus Germanic ancestry.

The first two principal components of the matrix of genotypes, after suitable
manipulations, can reproduce the geographic positions of European populations
(e.g. Menozzi et al., 1978; Novembre et al., 2008; Lao et al., 2008).
Therefore, it is natural to compare the structure we see within populations in
terms of IBD sharing to the positions on the principal components map. (A PCA
map of these populations (produced by EIGENSTRAT, Price et al., 2006) is shown
in supplemental figure S4.) It is not known what the geographic resolution of
the principal components map is, but if relative positions within populations
is meaningful, then comparison of IBD to PCA can stand in for comparison to
geography. Indeed, as seen in supplemental figures S6 and S5, the substructure
of figure 2 correlates well with the position on certain principal components,
further suggesting that the structure is geographically meaningful.
Conversely, since the substructure we see is highly statistically significant,
this demonstrates that the scatter of positions within populations on the
European PCA map is at least in part signal, rather than noise.

###  2.2 Europe-wide patterns of relatedness

Individuals usually share the highest number of IBD blocks with others from
the same population, with some exceptions. For example, individuals in the UK
share more IBD blocks on average, and hence more close genetic ancestors, with
individuals from Ireland than with other individuals from the UK (1.26 versus
1.09 blocks at least 1cM per pair, Mann-Whitney $p<10^{-10}$), and Germans
share similarly more with Polish than with other Germans (1.24 versus 1.05,
$p=5.7\times 10^{-6}$), a pattern which could be due to recent asymmetric
migration from a smaller population into a larger population. In figure 3 we
depict the geography of rates of IBD sharing between populations, i.e. the
average number of IBD blocks shared by a randomly chosen pair of individuals.
Above, maps show the IBD rate relative to certain chosen populations, and
below, all pairwise sharing rates are plotted against the geographic distance
separating the populations. It is evident that geographic proximity is a major
determinant of IBD sharing (and hence recent relatedness), with the rate of
pairwise IBD decreasing relatively smoothly as the geographic separation of
the pair of populations increases. Note that even populations represented by
only a single sample are included, as these showed surprisingly consistent
signal despite the small sample size.

Superimposed on this geographic decay there is striking regional variation in
rates of IBD. To further explore this variation, we divided the populations
into the four groups listed in table 1, using geographic location and
correlations in the pattern of IBD sharing with other populations (shown in
supplemental figure S7). These groupings are defined as: Europe “E”, lying to
the east of Germany and Austria; Europe “N”, lying to the north of Germany and
Poland; Europe “W”, to the west of Germany and Austria and including these;
the Iberian and Italian peninsulas “I”; and Turkey/Cyprus “TC”. Although the
general pattern of regional IBD variation is strong, none of these groups have
sharp boundaries – for instance, Germany, Austria, and Slovakia are
intermediate between E and W. Furthermore, we suspect that the Italian and
Iberian peninsulas likely do not group together because of higher shared
ancestry with each other, but rather because of similarly low rates of IBD
with other European populations. The overall mean IBD rates between these
regions are shown in table 2, and comparisons between different groupings are
colored differently in figure 3G–I, showing that rates of IBD sharing between
E populations and between N populations average a factor of about three higher
than other comparisons at similar distances. Such a large difference in the
rates of IBD sharing between regions, cannot be explained by plausible
differences in false positive rates or power between populations, since this
pattern holds even at the longest length scales, where block identification is
nearly perfect.

To better understand IBD within these groupings, we show in figures 3G–I how
average numbers of IBD blocks shared, in three different length categories,
depend on the geographic distance separating the two populations. Even without
taking into account regional variation, mean numbers of shared IBD blocks
decay exponentially with distance, and further structure is revealed by
breaking out populations by the regional groupings described above. The
exponential decays shown for each pair of groupings emphasize how the decay of
IBD with distance becomes more rapid for longer blocks. This is expected under
models where migration is mostly local, since as one looks further back in
time, the distribution of each individual’s ancestors is less concentrated
around the individual’s location (recall figure 1B). Therefore, the expected
number of ancestors shared by a pair of individuals decreases as the
geographic distance between the pair increases; and this decrease is faster
for more recent ancestry.

This wider spread of older blocks can also explain why the decay of IBD with
distance varies significantly by region even if dispersal rates have been
relatively constant. For instance, the gradual decay of sharing with the
Iberian and Italian peninsulas could occur because these blocks are inherited
from much longer ago than blocks of similar lengths shared by individuals in
other populations.

Conversely, there is a high level of sharing for “E–E” relationships over a
broad range of distances. This is especially true for our shortest (oldest)
blocks: individuals in our E grouping share on average more short blocks with
individuals in distant E populations than do pairs of individuals in the same
W population. We argue below that this is because modern individuals in these
locations have a larger proportion of their ancestors in a relatively small
population that subsequently expanded.

Figure 3:  In all figures, colors give categories based on the regional groupings of table 1. (A–F) The area of the circle located on a particular population is proportional to the mean number of IBD blocks of length at least 1cM shared between random individuals chosen from that population and the population named in the label (also marked with a star). Both regional variation of overall IBD rates and gradual geographic decay are apparent. (G–I) Mean number of IBD blocks of lengths 1–3cM (oldest), 3–5cM, and $>$5cM (youngest), respectively, shared by a pair of individuals across all pairs of populations; the area of the point is proportional to sample size (number of distinct pairs), capped at a reasonable value; and lines show an exponential decay fit to each category (using a Poisson GLM weighted by sample size). Comparisons with no shared IBD are used in the fit but not shown in the figure (due to the log scale). “E–E”, “N–N”, and “W–W” denote any two populations both in the E, N, or W grouping, respectively; “TC-any” denotes any population paired with Turkey or Cyprus; “I-(I,E,N,W)” denotes Italy, Spain, or Portugal paired with any population except Turkey or Cyprus; and “between E,N,W” denotes the remaining pairs (when both populations are in E, N, or W, but the two are in different groups). The exponential fit for the N–N points is not shown due to the very small sample size. See supplemental figure S8 for an SVG version of these plots where it is possible to identify individual points.  IBD rate | E | I | N | TC | W
---|---|---|---|---|---
E | 2.57 | 0.44 | 0.99 | 0.62 | 0.53
I | 0.44 | 0.80 | 0.43 | 0.41 | 0.45
N | 0.99 | 0.43 | 2.62 | 0.33 | 0.86
TC | 0.62 | 0.41 | 0.33 | 1.43 | 0.25
W | 0.53 | 0.45 | 0.86 | 0.25 | 0.93
Table 2:  Rates of IBD within and between each geographic grouping given in
table 1.

Having seen the continent-wide patterns of IBD in figure 3, it is natural to
wonder if similar information is contained in single-site summaries of
relatedness, such as mean Identity by State (IBS) values across European
populations. The mean IBS between populations $x$ and $y$ is defined as the
probability that two randomly chosen alleles from $x$ and $y$ are identical
(“By State”), averaging over SNPs and individuals. In the analogous plot of
IBS against geographic distance (supplemental figure S9), some of the patterns
seen in figure 3 are present, and some are not. For instance, there is a
continuous decay with geographic distance (linear, not exponential), and
comparisons to the southern “I” group and to Cyprus/Turkey are even more well-
separated below the others. On the other hand, the “E-E” comparisons do not
show higher IBS than the bulk of the remaining comparisons.

###  2.3 Ages and numbers of common ancestors

Each block of genome shared IBD by a pair of individuals represents genetic
material inherited from one of their genetic common ancestors. Since the
distribution of lengths of IBD blocks differs depending on the age of the
ancestors – e.g. older blocks tend to be shorter – it is possible to use the
distribution of lengths of IBD blocks to infer numbers of most recent pairwise
genetic common ancestors back through time averaged across pairs of
individuals. For this inference, we restricted to blocks longer than 2cM,
where we had good power to detect true IBD blocks. We obtain dates in units of
generations in the past, and for ease of discussion convert these to years ago
(ya) by taking the mean human generation time to be 30 years (Fenner, 2005).

#### Nature of the results on age inference

There are two major difficulties to overcome, however. First, detection is
noisy: we do not detect all IBD segments (especially shorter ones), and some
of our IBD segments are false positives. This problem can be overcome by
careful estimation and modeling of error, described in section 4.2. The second
problem is more serious and unavoidable: as described in section 4.7, the
inference problem is extremely “ill conditioned” (in the sense of Petrov and
Sizikov, 2005), meaning in this case that there are many possible histories of
shared ancestry that fit the data nearly equally well. For this reason, there
is a fairly large, unavoidable limit to the temporal resolution, but we still
obtain a good deal of useful information.

We deal with this uncertainty by describing the set of histories (i.e.
historical numbers of common genetic ancestors) that are consistent with the
data, summarized in two ways. First, it is useful to look at individual
consistent histories, which gives a sense of recurrent patterns and possible
historical signals. Figure 4 shows for several populations both the best-
fitting history (in black) and the smoothest history that still fits the data
(in red). We can make general statements if they hold across all (or most)
consistent histories. Second, we can summarize the entire set of consistent
histories by finding confidence intervals (bounds) for the total number of
common ancestors aggregated in certain time periods. These are shown in figure
5, giving estimates (colored bands) and bounds (vertical lines) for the total
numbers of genetic common ancestors in each of three time periods, roughly
0–500ya, 500–1500ya, and 1500–2500ya (“ya” denotes “years ago”). Supplemental
figures S12 (and S13) is a version of figure 5 with more populations (in
coalescent units, respectively), and plots analogous to figure 4 for all these
histories are shown in supplemental figure S16. For a precise description of
the problem and our methods, see section 4.7. We validated the method through
simulation (details in supplemental document), and found that it performed
well to the temporal resolution discussed here. We note that in simulations
where the population size changes smoothly, the maximum likelihood solution is
often overly peaky, whereas the smoothed solution can smear out the signal of
rapid change in population size. In light of that we encourage the reader to
view truth as lying somewhere between these two solutions, and to not
overinterpret specific peaks in the maximum likelihood, which may occur due to
numerical properties of the inference. That said, there are a number of sharp
peaks in common ancestry shared across many population comparisons older than
2000 years ago, which may potentially indicate demographic events in a shared
ancestral population. A more thorough investigation of these older shared
signals would potentially need a more model-based approach, so we restrict
ourselves here to talking about the broad differences between the distribution
of common shared ancestors between regions.

Figure 4:  Estimated average number of most recent genetic common ancestors
per generation back through time, shared by (A) pairs of individuals from “the
Balkans” (former Yugoslavia, Bulgaria, Romania, Croatia, Bosnia, Montenegro,
Macedonia, Serbia, and Slovenia, excluding Albanian speakers); and, shared by
one individual from the Balkans with one individual from (B) Albanian speaking
populations; (C) Italy; or (D) France. The black distribution is the maximum
likelihood fit; shown in red is smoothest solution that still fits the data,
as described in section 4.7. (E) shows the observed IBD length distribution
for pairs of individuals from the Balkans (red curve), along with the
distribution predicted by the smooth (red) distribution in (A), as a stacked
area plot partitioned by time period in which the common ancestor lived. The
partitions with significant contribution are labeled on the left vertical axis
(in generations ago), and the legend in (J) gives the same partitions, in
years ago; the vertical scale is given on the right vertical axis. The second
column of figures (F–J) is similar, except that comparisons are relative to
samples from the UK.

The time periods we use for these bounds are quite large, but this is
unavoidable, because of a trade off between temporal resolution and
uncertainty in numbers of common ancestors. Also note that the lower bounds on
numbers of common ancestors during each time interval are often close to zero.
This is because one can (roughly speaking) obtain a history with equally good
fit by moving ancestors from that time interval into the neighboring ones,
resulting in peaks on either side of the selected time interval (see figure
S14), even though these do not generally reflect realistic histories. The
reader should also bear in mind that we do not depict the dependence of
uncertainty between intervals.

Figure 5:  Estimated average total numbers of genetic common ancestors shared
per pair of individuals in various pairs of populations, in roughly the time
periods 0–500ya, 500–1500ya, 1500–2500ya, and 2500–4300ya. We have combined
some populations to obtain larger sample sizes: “S-C” denotes Serbo-Croatian
speakers in former Yugoslavia, “PL” denotes Poland, “R-B” denotes Romania and
Bulgaria, “DE” denotes Germany, “UK” denotes the United Kingdom, “IT” denotes
Italy, and “Iber” denotes Spain and Portugal. For instance, the green bars in
the leftmost panels tell us that Serbo-Croatian speakers and Germans most
likely share 0–0.25 most recent genetic common ancestor from the last 500
years, 3–12 from the period 500–1500 years ago, 120–150 from 1500–2500 ya, and
170–250 from 2500–4400 ya. Although the lower bounds appear to extend to zero,
they are significantly above zero in nearly all cases except for the most
recent period 0–540ya.

#### Results of age inference

In figure 4 we show how the age and number of shared pairwise genetic common
ancestors changes as we move away from the Balkans (left column) and the UK
(right column), along with two examples of how the observed block length
distribution is composed of ancestry from different depths. (The average
number of shared pairwise genetic common ancestors from generation $n$ is the
probability that the most recent common ancestor of a pair at a single site
lived in generation $n$ (i.e. the coalescent rate) multiplied by the expected
number of segments that recombination has broken a pair of individuals’
genomes into that many generations back, as shown in section 4.8.) More plots
of this form are shown in supplemental figure S16, and coalescent rates
between pairs of populations are shown in the (equivalent) supplemental figure
S15.

Most detectable recent common ancestors lived between 1500 and 2500 years ago,
and only a small proportion of blocks longer than 2cM are inherited from
longer ago than 4000 years. Obviously, there are a vast number of genetic
common ancestors older than this, but the blocks inherited from such common
ancestors are sufficiently unlikely to be longer than 2cM that we do not
detect many. For the most part, blocks longer than 4cM come from 500–1500
years ago, and blocks longer than 10cM from the last 500 years.

In most cases, only pairs within the same population are likely to share
genetic common ancestors within the last 500 years. Exceptions are generally
neighboring populations (e.g. UK and Ireland). During the period 500–1500ya,
individuals typically share tens to hundreds of genetic common ancestors with
others in the same or nearby populations, although some distant populations
have very low rates. Longer ago than 1500ya, pairs of individuals from any
part of Europe share hundreds of genetic ancestors in common, and some share
significantly more.

#### Regional variation: interesting cases

We now examine some of the more striking patterns we see in more detail.

There is relatively little common ancestry shared between the Italian
peninsula and other locations, and what there is seems to derive mostly from
longer ago than 2500ya. An exception is that Italy and the neighboring Balkan
populations share small but significant numbers of common ancestors in the
last 1500 years, as seen in supplemental figures S16 or S17. The rate of
genetic common ancestry between pairs of Italian individuals seems to have
been fairly constant for the past 2500 years, which combined with significant
structure within Italy suggests a constant exchange of migrants between
coherent subpopulations.

Patterns for the Iberian peninsula are similar, with both Spain and Portugal
showing very few common ancestors with other populations over the last 2500
years. However, the rate of IBD sharing within the peninsula is much higher
than within Italy – during the last 1500 years the Iberian peninsula shares
fewer than 2 genetic common ancestors with other populations, compared to
roughly 30 per pair within the peninsula; Italians share on average only about
8 with each other during this period.

The higher rates of IBD between populations in the “E” grouping shown in
figure 3 seem to derive mostly from ancestors living 1500–2500ya, but also
show increased numbers from 500–1500ya, as shown in figure 5 and supplemental
figures S17. For comparison, the IBD rate is high enough that even
geographically distant individuals in these eastern populations share about as
many common ancestors as do two Irish or two French-speaking Swiss.

By far the highest rates of IBD within any populations is found between
Albanian speakers – around 90 ancestors from 0–500ya, and around 600 ancestors
from 500–1500ya (so high that we left them out of figure 5; see supplemental
figure S12). Beyond 1500ya, the rates of IBD drop to levels typical for other
populations in the eastern grouping.

There are clear differences in the number and timing of genetic common
ancestors shared by individuals from different parts of Europe, These
differences reflect the impact of major historical and demographic events,
superimposed against a background of local migration and generally high
genealogical relatedness across Europe. We now turn to discuss possible causes
and implications of these results.

##  3 Discussion

Genetic common ancestry within the last 2500 years across Europe has been
shaped by diverse demographic and historical events. There are both
continental trends, such as a decrease of shared ancestry with distance,
regional patterns, such as higher IBD in eastern and northern populations, and
diverse outlying signals. We have furthermore quantified numbers of genetic
common ancestors that populations share with each other back through time,
albeit with a (unavoidably) coarse temporal resolution. These numbers are
intriguing not only because of the differences between populations, which
reflect historical events, but the high degree of implied genealogical
commonality between even geographically distant populations.

#### Ubiquity of common ancestry

We have shown that typical pairs of individuals drawn from across Europe have
a good chance of sharing long stretches of identity by descent, even when they
are separated by thousands of kilometers. We can furthermore conclude that
pairs of individuals across Europe are reasonably likely to share common
genetic ancestors within the last 1000 years, and are certain to share many
within the last 2500 years. From our numerical results, the average number of
genetic common ancestors from the last 1000 years shared by individuals living
at least 2000km apart is about 1/32 (and at least 1/80); between 1000–2000ya
they share about one; and between 2000–3000ya they share above ten. Since the
chance is small that any genetic material has been transmitted along a
particular genealogical path from ancestor to descendent more than 8
generations deep (Donnelly, 1983) – about .008 at 240ya, and $2.5\times
10^{-7}$ at 480ya – this implies, conservatively, thousands of shared
genealogical ancestors in only the last 1000 years even between pairs of
individuals separated by large geographic distances. At first sight this
result seems counterintuitive. However, as 1000 years is about 33 generations,
and $2^{33}\approx 10^{10}$ is far larger than the size of the European
population, so long as populations have mixed sufficiently, by 1000 years ago
everyone (who left descendants) would be an ancestor of every present day
European. Our results are therefore one of the first genomic demonstrations of
the counter-intuitive but necessary fact that all Europeans are genealogically
related over very short time periods, and lends substantial support to models
predicting close and ubiquitous common ancestry of all modern humans (Rohde et
al., 2004).

The fact that most people alive today in Europe share nearly the same set of
(European, and possibly world-wide) ancestors from only 1000 years ago seems
to contradict the signals of long term, albeit subtle, population genetic
structure within Europe (e.g. Novembre et al., 2008; Lao et al., 2008). These
two facts can be reconciled by the fact that even though the distribution of
ancestors (as cartooned in figure 1B) has spread to cover the continent, there
remain differences in degree of relatedness of modern individuals to these
ancestral individuals. For example, someone in Spain may be related to an
ancestor in the Iberian peninsula through perhaps 1000 different routes back
through the pedigree, but to an ancestor in the Baltic region by only 10
different routes, so that the probability that this Spanish individual
inherited genetic material from the Iberian ancestor is roughly 100 times
higher. This allows the amount of genetic material shared by pairs of extant
individuals to vary even if the set of ancestors is constant.

#### Relation to single-site summaries

Other work has studied fine-scale differentiation between populations within
Europe based on statistics such as $F_{ST}$, IBS (e.g. Lao et al., 2008;
O’Dushlaine et al., 2010), or PCA (Novembre et al., 2008), that summarize in
various ways single-marker correlations, averaged across loci. Like rates of
IBD, these measures of differentiation can be thought of as weighted averages
of past coalescent rates (Malécot, 1969; Slatkin, 1991; Rousset, 2002; McVean,
2009), but take much of their information from much more distant times (tens
thousands of generations). As expected, we have seen both strong consistency
between these measures and IBD (e.g. the decay with geographic distance), as
well as distinct patterns (e.g. higher sharing in eastern Europe). These
results highlight the fact that long segments of IBD contain information about
much more recent events than do single-site summaries, information that can be
leveraged to learn about the timing of these events.

#### Limitations of Sampling

A concern about our results is that the European individuals in the POPRES
dataset were all sampled in either Lausanne or London. This might bias our
results, for instance, if an immigrant community originated mostly from a
particular small portion of their home population, thereby sharing a
particularly high number of recent common ancestors with each other. We see
remarkably little evidence that this is the case: there is a high degree of
consistency in numbers of IBD blocks shared across samples from each
population, and between neighboring populations. For instance, we could argue
that the high degree of shared common ancestry among Albanian speakers was
because most of these sampled originated from a small area rather than
uniformly across Albania and Kosovo. However, this would not explain the high
rate of IBD between Albanian speakers and neighboring populations. Even
populations from which we only have one or two samples, which we at first
assumed would be unusably noisy, provide generally reliable, consistent
patterns, as evidenced by e.g. supplemental figure S3.

Conversely, it might be a concern that individuals sampled in Lausanne or
London are more likely to have recent ancestors more widely dispersed than is
typical for their population of origin. This is a possibility we cannot
discard, and if true, would mean there is more structure within Europe than
what we detect. However, by the incredibly rapid spread of ancestry, this is
unlikely to have an effect over more than a few generations and so does not
pose a serious concern about our results about the ubiquitous levels of common
ancestry. Fine-scale geographic sampling of Europe as a whole is needed to
address these issues, and these efforts are underway in a number of
populations (e.g. Price et al., 2009; Jakkula et al., 2008; Tyler-Smith and
Xue, 2012; Winney et al., 2011).

Finally, we have necessarily have taken a narrow view of European ancestry as
we have restricted our sample to individuals who are not outliers with respect
to genetic ancestry, and when possible to those having all four grandparents
drawn from the same county. Clearly the ancestry of Europeans is far more
diverse than those represented here, but such steps seemed necessary to make
best initial use of this dataset.

#### Ages of particular common ancestors

We have shown that the problem of inferring the average distribution of
genetic common ancestors back through time has a large degree of fundamental
uncertainty. The data effectively leave a large number of degrees of freedom
unspecified, so one must either describe the set of possible histories, as we
do, and/or use prior information to restrict these degrees of freedom.

A related but far more intractable problem is to make a good guess of how long
ago a certain shared genetic common ancestor lived, as personal genome
services would like to do, for instance: if you and I share a 10cM block of
genome IBD, when did our most recent common ancestor likely live? Since the
mean length of an IBD block inherited from 5 generations ago is 10cM, we might
expect the average age of the ancestor of a 10cM block to be from around 5
generations. However, a direct calculation from our results says that the
typical age of a 10cM block shared by two individuals from the UK is between
32 and 52 generations (depending on the inferred distribution used). This
discrepancy results from the fact that you are a priori much more likely to
share a common genetic ancestor further in the past, and this acts to skew our
answers away from the naive expectation – even though it is unlikely that a
10cM block is inherited from a particular shared ancestor from 40 generations
ago, there are a great number of such older shared ancestors. This also means
that estimated ages must depend drastically on the populations’ shared
histories: for instance, the age of such a block shared by someone from the UK
with someone from Italy is even older, usually from around 60 generations ago.
This may not apply to ancestors from the past very few (perhaps less than
eight) generations, from whom we expect to inherit multiple long blocks – in
this case we can hope to infer a specific genealogical relationship with
reasonable certainty (e.g. Huff et al., 2011; Henn et al., 2012b), although
even then care must be taken to exclude the possibility that these multiple
blocks have not been inherited from distinct common ancestors.

Although the sharing of a long genomic segment can be an intriguing sign of
some recent shared ancestry, the ubiquity of shared genealogical ancestry only
tens of generations ago across Europe (and likely the world, Rohde et al.,
2004) makes such sharing unsurprising, and assignment to particular
genealogical relationships impossible. What is informative about these chance
sharing events from distant ancestors is that they provide a fine-scale view
of an individual’s distribution of ancestors (e.g. figure 3), and that in
aggregate they can provide an unprecedented view into even small-scale human
demographic history.

#### Where do your $n^{\mathrm{th}}$ cousins live?

Our results also offer a way to understand the geographic location of
individuals of a given degree of relatedness. The values of figure 5 (and S12)
can be interpreted as the distribution of distant cousins for any reference
population – for instance, the set of bars for Poland (“PL”) in the top row
shows that a randomly chosen distant cousin of a Polish individual with the
common ancestor living in the past 500 years most likely lives in Poland but
has reasonable chance of living in the Balkan peninsula or Germany. Here
“randomly chosen” means chosen randomly proportional to the paths through the
pedigree – concretely, take a random walk back through the pedigree to an
ancestor in the appropriate time period, and then take a random walk back
down. If one starts in Poland, then the chance of arriving in, say, Romania is
proportional to the average number of (genetic) common ancestors shared by a
pair from Poland and Germany, which is exactly the number estimated in figure
5.

### The signal of history

As we have shown, patterns of IBD provide ample but noisy geographic and
temporal signals, which can then be connected to historical events. Rigorously
making such connections is difficult, due to the complex recent history of
Europe, controversy about the demographic significance of many events, and
uncertainties in inferring the ages of common ancestors. Nonetheless, our
results can be plausibly connected to several historical and demographic
events.

#### The migration period

One of the striking patterns we see is the relatively high level of sharing of
IBD between pairs of individuals across eastern Europe, as high or higher than
that observed within other, much smaller populations. This is consistent with
these individuals having a comparatively large proportion of ancestry drawn
from a relatively small population that expanded over a large geographic area.
The “smooth” estimates of figure 4 (and more generally figures 5, and S17),
suggest that this increase in ancestry stems from around 1000–2000 years ago,
since during this time pairs of eastern individuals are expected to share a
substantial number of common ancestors, while this is only true of pairs of
non-eastern individuals if they are from the same population. For example,
even individuals from widely separated eastern populations share about the
same amount of IBD as do two Irish individuals (see supplemental figure S3),
suggesting that this ancestral population may have been relatively small.

This evidence is consistent with the idea that these populations derive a
substantial proportion of their ancestry from various groups that expanded
during the “migration period” from the fourth through ninth centuries (Davies,
2010). This period begins with the Huns moving into eastern Europe towards the
end of the fourth century, establishing an empire including modern-day Hungary
and Romania; and continues in the fifth century as various Germanic groups
moved into and ruled much of the western Roman empire. This was followed by
the expansion of the Slavic populations into regions of low population density
beginning in the sixth century, reaching their maximum by the 10th century
(Barford, 2001). The eastern populations with high rates of IBD is highly
coincident with the modern distribution of Slavic languages, so it is natural
to speculate that much of the higher rates were due to this expansion. The
inclusion of (non-Slavic speaking) Hungary and Romania in the group of eastern
populations sharing high IBD could indicate the effect of other groups (e.g.
the Huns) on ancestry in these regions, or because some of the same group of
people who elsewhere are known as Slavs adopted different local cultures in
those regions. Greece and Albania are also part of this putative signal of
expansion, which could be because the Slavs settled in part of these areas
(with unknown demographic effect), or because of subsequent population
exchange. However, additional work and methods would be needed to verify this
hypothesis.

The highest levels of IBD sharing are found in the Albanian-speaking
individuals (from Albania and Kosovo), an increase in common ancestry deriving
from the last 1500 years. This suggests that a reasonable proportion of the
ancestors of modern-day Albanian speakers (at least those represented in
POPRES) are drawn from a relatively small, cohesive population that has
persisted for at least the last 1500 years. These individuals share similar
but slightly higher numbers of common ancestors with nearby populations than
do individuals in other parts of Europe (see figure S3), implying that these
Albanian speakers have not been a particularly isolated population so much as
a small one. Furthermore, our Greek and Macedonian samples share much higher
numbers of common ancestors with Albanian speakers than with other neighbors,
possibly a result of historical migrations, or else perhaps smaller effects of
the Slavic expansion in these populations. It is also interesting to note that
the sampled Italians share nearly as much IBD with Albanian speakers as with
each other. The Albanian language is a Indo-European language without other
close relatives (Hamp, 1966) that persisted through periods when neighboring
languages were strongly influenced by Latin or Greek, suggesting an intriguing
link between linguistic and genealogical history in this case.

#### Italy, Iberia, and France

On the other hand, we find that France and the Italian and Iberian peninsulas
have the lowest rates of genetic common ancestry in the last 1500 years (other
than Turkey and Cyprus), and are the regions of continental Europe thought to
have been least affected by the Slavic and Hunnic migrations. These regions
were, however, moved into by Germanic tribes (e.g. the Goths, Ostrogoths, and
Vandals), which suggests that perhaps the Germanic migrations/invasions of
these regions entailed a smaller degree of population replacement, than the
Slavic and/or Hunnic, or perhaps that the Germanic groups were less
genealogically cohesive. This is consistent with the argument that the Slavs
moved into relatively depopulated areas, while Gothic “migrations” may have
been takeovers by small groups of extant populations (Halsall, 2005;
Kobyliński, 2005).

In addition to the very few genetic common ancestors that Italians share both
with each other and with other Europeans, we have seen significant modern
substructure within Italy (i.e. figure 2) that predates most of this common
ancestry, and estimate that most of the common ancestry shared between Italy
and other populations is older than about 2300 years (supplemental figure
S16). Also recall that most populations show no substructure with regards to
the number of blocks shared with Italians, implying that the common ancestors
other populations share with Italy predate divisions within these other
populations. This suggests significant old substructure and large population
sizes within Italy, strong enough that different groups within Italy share as
little recent common ancestry as other distinct, modern-day countries,
substructure that was not homogenized during the migration period. These
patterns could also reflect in part geographic isolation within Italy as well
as a long history of settlement of Italy from diverse sources.

In contrast to Italy, the rate of sharing of IBD within the Iberian peninsula
is similar to that within other populations in Europe. There is furthermore
much less evidence of substructure within our Iberian samples than within the
Italians, as shown in supplemental figure S2. This suggests that the reduced
rate of shared ancestry is due to geographic isolation (by distance and/or the
Pyrenees) rather than long-term stable substructure within the peninsula.

#### Future directions

Our results show that patterns of recent identity by descent both provide
evidence of ubiquitous shared common ancestry and hold the potential to shed
considerable light on the complex history of Europe. However, these inferences
also quickly run up against a fundamental limit to our ability to infer
pairwise rates of recent common genetic ancestry. In order to make a fuller
model of European history, we will need to make use of diverse sources of
genomic information from large samples, including IBD segments and rare
variants (Nelson et al., 2012; Tennessen et al., 2012), and develop methods
that can more fully utilize this information across more than pairs of
populations. Another profound difficulty is that Europe – and indeed any large
continental region – has such complex layers of history, through which
ancestry has mixed so greatly, that attempts to connect genetic signals in
extant individuals to particular historical events requires the corroboration
of other sources of information from many disciplines. For example, the
ability to isolate ancient autosomal DNA from individuals who lived during
these time periods (as do Skoglund et al., 2012; Keller et al., 2012) will
help to overcome some of these these profound difficulties. More generally,
the quickly falling cost of sequencing, along with the development of new
methods, will shed light on the recent demographic and genealogical history of
populations of recombining organisms, human and otherwise.

##  4 Materials and Methods

### Description of data and data cleaning

We used the two European subsets of the POPRES dataset – the CoLaus subset,
collected in Lausanne, Switzerland, and the LOLIPOP subset, collected in
London, England; the dataset is described in Nelson et al. (2008). Those
collected in Lausanne reported parental and grandparental country of origin;
those collected in London did not. We followed Novembre et al. (2008) in
assigning each sample to the common grandparental country of origin when
available, and discarding samples whose parents or grandparents were reported
as originating in different countries. We took further steps to restrict to
individuals whose grandparents came from the same geographic region, first
performing principal components analysis on the data using SMARTPCA (Patterson
et al., 2006), and excluding 41 individuals who clustered with populations
outside Europe (the majority of such were already excluded by self-reported
non-European grandparents). These individuals certainly represent an important
part of the recent genetic ancestry of Europe, but are excluded because we aim
to study events stemming from older patterns of gene flow, and because we do
not model the whole-genome dependencies in recently admixed genomes. We then
used PLINK’s inference of the fraction of single-marker IBD (Z0, Z1, and Z2,
Purcell et al., 2007) to identify very close relatives, finding 25 pairs that
are first cousins or closer (including duplicated samples), and excluded one
individual from each pair. We grouped samples into populations mostly by
reported country, but also used reported language in a few cases. Because of
the large Swiss samples, we split this group into three by language: French-
speaking (CHf), German-speaking (CHd), or other (CH). Many samples reported
grandparents from Yugoslavia; when possible we assigned these to a modern-day
country by language, and when this was ambiguous or missing we assigned these
to “Yugoslavia”. Most samples from the United Kingdom reported this as their
country of origin; however, the few that reported “England” or “Scotland” were
assigned this label. This left us with 2257 individuals from 40 populations;
for sample sizes see table 1. Supplemental table S2 further breaks this down,
and unambiguously gives the composition of each population. Physical distances
were converted to genetic distances using the hg36 map, and the average human
generation time was taken to be 30 years (Fenner, 2005).

All figures were produced in R R Development Core Team (2012), with color
palettes from packages colorspace Zeileis et al. (2009) and RColorBrewer Plate
(2011). Code implementing all methods described below is distributed along
with IBD block data sufficient to reproduce the historical analyses through
http://www.github.com/petrelharp/euroibd and in the Dryad digital repository
Ralph and Coop (2013).

###  4.1 Calling IBD blocks

To find blocks of IBD, we used fastIBD (implemented in BEAGLE, Browning and
Browning, 2011), which records putative genomic segments shared IBD by pairs
of individuals, along with a score indicating the strength of support. As
suggested by the authors, in all cases we ran the algorithm 10 times with
different random seeds, and postprocessed the results to obtain IBD blocks.
Based on our power simulations described below, we modified the postprocessing
procedure recommended by Browning and Browning (2011) to deal with spurious
gaps or breaks introduced into long blocks of IBD by low marker density or
switch error, as follows: We called IBD segments by first removing any
segments not overlapping a segment seen in at least one other run (as
suggested by Browning and Browning (2011), except with no score cutoff); then
merging any two segments separated by a gap shorter than at least one of the
segments and no more than 5cM long; and finally discarding any merged segments
that did not contain a subsegment with score below $10^{-9}$. As shown in
figure 6, this resulted in a false positive rate of between 8–15% across
length categories, and a power of at least 70% above 1cM, reaching 95% by 4cM.
After post-processing, we were left with 1.9 million IBD blocks, 1 million of
which were at least 2cM long (at which length we estimate 85% power and a 10%
false positive rate).

Figure 6:  (A) Bias in inferred length with lines $x=y$ (dotted) and a loess
fit (solid). Each point is a segment of true IBD (copied between individuals),
showing its true length and inferred length after postprocessing. Color shows
the number of distinct, nonoverlapping segments found by BEAGLE, and the
length of the vertical line gives the total length of gaps between such
segments that BEAGLE falsely inferred was not IBD (these gaps are corrected by
our postprocessing). (B) Estimated false positive rate as a function of
length. Observed rates of IBD blocks, per pair and per cM, are also displayed
for the purpose of comparison. “Nearby” and “Distant” means IBD between pairs
of populations closer and farther away than 1000km, respectively. (C) Below,
the estimated power as a function of length (black line), together with the
parametric fit $c(x)$ of equation (1) (red dotted curve).

###  4.2 Power and false positive simulations

All methods to identify haplotypic IBD rely on identifying long regions of
near identical haplotypes between pairs of individuals (referred to as
identical by state, IBS). However, long IBS haplotypes could potentially also
result from the concatenation of multiple shorter blocks of true IBD. While
such runs can contain important information about deeper population history
(e.g. Li and Durbin, 2011; Harris and Nielsen, 2012), we view them as a false
positives as they do not represent single haplotypes shared without
intervening recombination. The chance of such a false positive IBD segment
decreases as the genetic length of shared haplotype increases. However, the
density of informative markers also plays a role, because such markers are
necessary to infer regions of IBS.

#### Power

If we are to have a reasonable false positive rate, we must accept imperfect
power. Power will also vary with the density and informativeness of markers
and length of segment considered. For example, it is intuitive that segments
of genome containing many rare alleles are easier identify as IBD. Conversely,
rare immigrant segments from a population with different allele frequencies
may, if they are shared by multiple individuals within the population, cause
higher false positive rates. For these reasons, when estimating statistical
power and false positive rate, it is important to use a dataset as similar to
the one under consideration as possible. Therefore, to determine appropriate
postprocessing criteria and to estimate our statistical power, we constructed
a dataset similar to the POPRES with known shared IBD segments as follows: we
copied haploid segments randomly between 60 trio-phased individuals of
European descent (using only one from each trio) from the HapMap dataset
(haplotypes from release #21, 17/07/06 International HapMap Consortium et al.,
2007), reoriented alleles to match the strand orientation of POPRES,
substituted these for 60 individuals from Switzerland in the POPRES data, and
ran BEAGLE on the result as before. These segments were copied between single
chromosomes of randomly chosen individuals, for random lengths 0.5–20cM, with
gaps of at least 2cM between adjacent segments and without copying between the
same two individuals twice in a row. When copying, we furthermore introduced
genotyping error by flipping alleles independently with probability .002 and
marking the allele missing with probability .023 (error rates were determined
from duplicated individuals in the sample as given by Nelson et al. (2008)).
An important feature of the inferred data was that BEAGLE often reported true
segments longer than about 5cM as two or more shorter segments separated by a
short gap, which led us to merge blocks as described above.

#### Length bias

We also need a reasonably accurate assessment of our bias and false positive
rates for our inference of numbers of genetic ancestors from the IBD length
spectrum. Although the estimated IBD lengths were approximately unbiased, we
fit a parametric model to the relationship between true and inferred lengths
after removing inferred blocks less than 1cM long. A true IBD block of length
$x$ is missed entirely with probability $1-c(x)$, and is otherwise inferred to
have length $x+\epsilon$; with probability $\gamma(x)$ the error $\epsilon$ is
positive; otherwise it is negative and conditioned to be less than $x$. In
either case, $\epsilon$ is exponentially distributed; if $\epsilon>0$ its mean
is $1/\lambda_{+}(x)$, while if $\epsilon<0$ its (unconditional) mean is
$1/\lambda_{-}(x)$. The parametric forms were chosen by examination of the
data; these are, with final parameter values:

$\displaystyle\begin{split}c(x)&=1-1/\left(1+.077x^{2}\exp(.54x)\right)\\\
\gamma(x)&=.34\left(1-(1+.51(x-1)^{+}\exp(.68(x-1)^{+}))^{-1}\right)\\\
\lambda_{+}(x)&=1.40\\\ \lambda_{-}(x)&=\min(.40+1/(.18x),12)\end{split}$ (1)

where $z^{+}=\max(z,0)$. The parameters were found by maximum likelihood,
using constrained optimization as implemented in the R package optim (R
Development Core Team, 2012) separately on three independent pieces: the
parameters in $c(x)$ and $\gamma(x)$; the parameters in $\lambda_{-}$; and
finally the parameters in $\lambda_{+}$; the fit is shown in supplemental
figure S10.

#### False positive rate

To estimate the false positive rate, we randomly shuffled segments of diploid
genome between individuals from the same population (only those 12 populations
with at least 19 samples) so that any run of IBD longer than about 0.5cM would
be broken up among many individuals. Specifically, as we read along the genome
we output diploid genotypes in random order; we shuffled this order by
exchanging the identity of each output individual with another at independent
increments chosen uniformly between 0.1 and 0.2cM. This ensured that no output
individual had a continuous run of length longer than 0.2cM copied from a
single input individual, while also preserving linkage on scales shorter than
0.1cM. The results are shown in figure 6B; from these we estimate that the
mean density of false positives $x$ cM long per pair and per cM is
approximately

$f(x)=\exp(-13-2x+4.3\sqrt{x}),$ (2)

a parametric form again chosen by examination of the data and fit by maximum
likelihood.

We found that overall, the false positive rate was around $1/10^{\mathrm{th}}$
of the observed rate, except for very long blocks (longer than 5cM or so,
where it was close to zero), and for very short blocks (less than 1cM, where
it approached 0.4). As fastIBD depends on estimating underlying haplotype
frequencies, it is expected to have a higher false positive rate in
populations that are more differentiated from the rest of the sample. There
was significant variation in false positive rate between different
populations, with Spain, Portugal, and Italy showing significantly higher
false positive rates than the other populations we examined – see supplemental
figure S11 – however, the variation was significant only for blocks shorter
than 2cM across all population pairs, with the exception of pairs of
Portuguese individuals, where the upwards bias may be significant as high as
4cM.

#### Differential sample sizes

Finally, one concern is that as fastIBD calls IBD based on a model of
haplotype frequencies in the sample it may be unduly affected by the large-
scale sample size variation across the POPRES sample. In particular, the
French-speaking Swiss sample is very large, which could lead to systematic
bias in calling IBD in populations closely to the Swiss samples. To
investigate this, we randomly discarded 745 French-speaking Swiss (all but 100
of these), and a random sampling of the remaining populations (removing 812 in
total, leaving 1445). We then ran BEAGLE on chromosome 1 of these individuals,
postprocessing in the same way as for the full sample. Reassuringly, there was
high concordance between the two – we found that 98% (95%) of the blocks
longer than 2cM found in the analysis with the full dataset (respectively,
with the subset) were found in both analyses. Overall, more blocks were found
by the analysis with the smaller dataset; however, by adjusting the score
cutoff by a fixed amount this difference could be removed, leaving nearly
identical length distributions between the two analyses. This is a known
attribute of the fastIBD algorithm, and can alternatively be avoided by
adjusting the model complexity .

We then tested the extent to which the effect of sample size varied by
population, for IBD blocks in several length categories (binning block lengths
at 1, 2, 4, and 10cM). Suppose that $F_{xy}$ is the number of IBD blocks found
between populations $x$ and $y$ in the analysis of the full dataset, and
$S_{xy}$ is the number found in the analysis of the smaller dataset (counted
between the same individuals each time). We then assume that $F_{xy}$ and
$S_{xy}$ are Poisson with mean $\lambda^{F}_{xy}$ and $\lambda^{S}_{xy}$,
respectively, so that conditioned on $N_{xy}=F_{xy}+S_{xy}$ (the total number
of blocks), $S_{xy}$ is binomial with parameters $N_{xy}$ and
$p_{xy}=\lambda^{S}_{xy}/(\lambda^{S}_{xy}+\lambda^{F}_{xy})$. We are looking
for deviations from the null model under which the effect of smaller sample
size affects all population pairs equally, so that
$\lambda^{S}_{xy}=C\;\lambda^{F}_{xy}$ for some constant $C$. We therefore fit
a binomial GLM (McCullagh and Nelder, 1989) with a logit link, with terms
corresponding to each population – in other words,

$\displaystyle
p_{xy}=\left(1+\exp\left(-\alpha_{0}-\alpha_{x}-\alpha_{y}\right)\right)^{-1}.$

We found statistically significant variation by population (i.e. several
nonzero $\alpha_{x}$), but all effect sizes were in the range of 0–4%;
estimated parameters are listed in supplemental table S1. Notably, the
coefficient corresponding to the French-speaking Swiss (the population with
the largest change in sample size) was fairly small. We also fit the model not
assuming additivity when $x=y$, i.e. adding coefficients $\alpha_{xx}$ to the
formula for $p_{xx}$, but these were not significant. These results suggest
that sample size variation across the POPRES data has only minor effects on
the distribution of IBD blocks shared across populations.

###  4.3 IBD rates along the genome

To look for regions of unusual levels of IBD and to examine our assumption of
uniformity, we compared the density of IBD tracts of different lengths along
the genome,

in supplemental figure S1. To do this, we first divided blocks up into
nonoverlapping bins based on length, with cutpoints at 1, 2.5, 4, 6, 8, and
10cM. We then computed at each SNP the number of IBD blocks in each length bin
that covered that site. To control for the effect of nearby SNP density on the
ability to detect IBD, we then computed the residuals of a linear regression
predicting number of overlapping IBD blocks using the density of SNPs within
3cM. To compare between bins, we then normalized these residuals, subtracting
the mean and dividing by the standard deviation; these “z-scores” for each SNP
are shown in figure S1.

###  4.4 Correlations in IBD rates across populations

We noted repeated patterns of IBD sharing across multiple populations (seen in
supplemental figure S3), in which certain sets of populations tended to show
similar patterns of sharing. To quantify this, we computed correlations
between mean numbers of IBD blocks; in supplemental figure S7 we show
correlations in numbers blocks of various lengths. Specifically, if $I(x,y)$
is the mean number of IBD blocks of the given length shared by an individual
from population $x$ with a (different) individual from population $y$, there
are $n$ populations, and $\bar{I}(x)=(1/(n-1))\sum_{y\neq x}I(x,y)$, then
figure S7 shows for each $x$ and $y$,

$\frac{1}{n-2}\sum_{z\notin\\{x,y\\}}(I(x,z)-\bar{I}(x))(I(y,z)-\bar{I}(y)),$
(3)

the (Pearson) correlation between $I(x,z)$ and $I(y,z)$ ranging across
$z\notin\\{x,y\\}$. Other choices of block lengths are similar, although
shorter blocks show higher overall correlations (due in part to false
positives) and longer blocks show lower overall correlations (as rates are
noisier, and sharing is more restricted to nearby populations). The geographic
groupings of table 1 were then chosen by visual inspection.

###  4.5 Substructure

We assessed the overall degree of substructure within each population, by
measuring, for each $x$ and $y$, the degree of inhomogeneity across
individuals of population $x$ for shared ancestry with population $y$. We
measured inhomogeneity by the standard deviation in number of blocks shared
with population $y$, across individuals of population $x$. We assessed the
significance by a permutation test, randomly reassigning each block shared
between $x$ and $y$ to a individual chosen uniformly from population $x$, and
recomputing the standard deviation, 1000 times. (If there are $k$ blocks
shared between $x$ and $y$ and $m$ individuals in population $x$, this is
equivalent to putting $k$ balls in $m$ boxes, tallying how many balls are in
each box, and computing the sample standard deviation of the resulting list of
numbers.) Note that some degree of inhomogeneity of shared ancestry is
expected even within randomly mating populations, due to randomness of the
relationship between individuals in the pedigree. These effects are likely to
be small if the relationships are suitably deep, but this is still an area of
active research (Henn et al., 2012b; Carmi et al., 2012). The resulting
$p$-values are shown in supplemental figure S2. We did not analyze these in
detail, particularly as we had limited power to detect substructure in
populations with few samples, but note that a large proportion (47%) of the
population pairs showed greater inhomogeneity than in all 1000 permuted
samples (i.e. $p<.001$). Some comparisons even with many samples in both
populations (where we have considerable power to detect even subtle
inhomogeneity) showed no structure whatsoever – in particular, the
distribution of numbers of Italian IBD blocks shared by Swiss individuals is
not distinguishable from Poisson, indicating a high degree of homogeneity of
Italian ancestry across Switzerland.

###  4.6 Single-site summaries

To assess the single marker measures of relatedness across the POPRES sample
we calculated pairwise identity by state, the probability that two alleles
sampled at random from a pair of individuals are identical, averaged across
SNPs. This was calculated for all pairs of individuals using the “\--genome”
option in PLINK v1.07 (Purcell et al., 2007,
http://pngu.mgh.harvard.edu/purcell/plink), and is shown in Supplementary
Figure S9 with points colored as in Figure 3.

We also calculated principal components of the POPRES genotype data using the
EIGENSOFT package v3.0 (Patterson et al., 2006), which were used in
identifying outlying individuals and in producing figures S4, S5, and S6.

###  4.7 Inferring ages of common ancestors

Here, our aim is to use the distribution of IBD block lengths to infer how
long ago the genetic common ancestors were alive from which these IBD blocks
were inherited. A pair of individuals who share a block of IBD of genetic
length at least $x$ have each inherited contiguous regions of genome from a
single common ancestor $n$ generations ago that overlap for length at least
$x$. If we start with the population pedigree, those ancestors from which the
two individuals might have inherited IBD blocks are those that can be
connected to both by paths through the pedigree. The distribution of possible
IBD blocks is determined by the number of links (i.e. the number of meioses)
occurring along the two paths.

Throughout the article we informally often refer to ancestors living a certain
“number of generations in the past” as if humans were semelparous with a fixed
lifetime. Keeping with this, it is natural to write the number of IBD blocks
shared by a pair of individuals as the sum over past generations of the number
of IBD blocks inherited from that generation. In other words, if $N(x)$ is the
number of IBD blocks of genetic length at least $x$ shared by two individual
chromosomes, and $N_{n}(x)$ is the number of such IBD blocks inherited by the
two along paths through the pedigree having a total of $n$ meioses, then
$N(x)=\sum_{n}N_{n}(x)$. Therefore, averaging over possible choices of pairs
of individuals, the mean number of shared IBD blocks can be similarly
partitioned as

$\mathbb{E}[N(x)]=\sum_{n\geq 1}\mathbb{E}[N_{n}(x)].$ (4)

In each successive generation in the past each chromosome is broken up into
successively more pieces, each of which has been inherited along a different
path through the pedigree, and any two such pieces of the two individual
chromosomes that overlap and are inherited from the same ancestral chromosome
contribute one block of IBD. Therefore, the mean number of IBD blocks coming
from $n/2$ generations ago is the mean number of possible blocks multiplied by
the probability that a particular block is actually inherited by both
individuals from the same genealogical ancestor in generation $n/2$. Allowing
for overlapping generations, the first part we denote by $K(n,x)$, the mean
number of pieces of length at least $x$ obtained by cutting the chromosome at
the recombination sites of $n$ meioses, and the second part we denote by
$\mu(n)$, the probability that the two chromosomes have inherited at a
particular site along a path of total length $n$ meioses (e.g. their common
ancestor at that site lived $n/2$ generations ago). Multiplying these and
summing over possible paths, we have that

$\mathbb{E}[N(x)]=\sum_{n\geq 1}\mu(n)K(n,x),$ (5)

i.e. the mean rate of IBD is a linear function of the distribution of the time
back to the most recent common ancestor averaged across sites. The
distribution $\mu(n)$ is more precisely known as the coalescent time
distribution (Kingman, 1982; Wakeley, 2005), in its obvious adaptation to
population pedigrees. As a first application, note that the distribution of
ages of IBD blocks above a given length $x$ depends strongly on the
demographic history – a fraction $\mu(n)K(n,x)/\sum_{m}\mu(m)K(m,x)$ of these
are from paths $n$ meioses long.

Furthermore, it is easy to calculate that for a chromosome of genetic length
$G$,

$K(n,x)=\left(n(G-x)+1\right)\exp(-xn),$ (6)

assuming homogeneous Poisson recombination on the genetic map (as well as
constancy of the map and ignoring the effect of interference, which is a
reasonable for the range of $n$ we consider). The mean number of IBD blocks of
length at least $x$ shared by a pair of individuals across the entire genome
is then obtained by summing (5) across all chromosomes, and multiplying by
four (for the four possible chromosome pairs).

Equations (5) and (6) give the relationship between lengths of shared IBD
blocks and how long ago the ancestor lived from whom these blocks are
inherited. Our goal is to invert this relationship to learn about $\mu(n)$,
and hence the ages of the common ancestors underlying our observed
distribution of IBD block lengths. To do this, we first need to account for
sampling noise and estimation error. Suppose we are looking at IBD blocks
shared between any of a set of $n_{p}$ pairs of individuals, and assume that
$N(y)$, the number of observed IBD blocks shared between any of those pairs of
length at least $y$, is Poisson distributed with mean $n_{p}M(y)$, where

$\displaystyle M(y)$ $\displaystyle=\int_{y}^{G}f(z)+\sum_{n\geq
1}\mu(n)\left(\int_{0}^{G}c(x)R(x,z)dK(n,x)\right)dz,\quad\mbox{with}$ (7)
$\displaystyle R(x,y)$
$\displaystyle=\begin{cases}\gamma(x)\lambda_{+}(x)\exp(-\lambda_{+}(x)(y-x))\quad&\mbox{for}\;y>x\\\
(1-\gamma(x))\lambda_{-}\exp(-\lambda_{-}(x)(x-y))/(1-\exp(-\lambda_{-}(x)x))\quad&\mbox{for}\;y<x.\end{cases}$
(8)

Here the false positive rate $f(z)$, power $c(x)$ and the components of the
error kernel $R(x,y)$ are estimated as above, with parametric forms given in
equations (2) and (1). The Poisson assumption has been examined elsewhere
(e.g. Fisher, 1954; Huff et al., 2011), and is reasonable because there is a
very small chance of having inherited a block from each pair of shared
genealogical ancestors; there a great number of these, and if these events are
sufficiently independent, the Poisson distribution will be a good
approximation (see e.g. Grimmett and Stirzaker, 2001). If this holds for each
pair of individuals, the total number of IBD blocks is also Poisson
distributed, with $M$ given by the mean of this number across all constituent
pairs. (Note that this does not assume that each pair of individuals has the
same mean number, so does not assume that our set of pairs are a homogeneous
population.)

We have therefore a likelihood model for the data, with demographic history
(parametrized by $\mu=\\{\mu(n):n\geq 1\\}$) as free parameters.
Unfortunately, the problem of inferring $\mu$ is ill-conditioned (unsuprising
due to its similarity of the kernel (6) to the Laplace transform, see Epstein
and Schotland, 2008), which in this context means that the likelihood surface
is flat in certain directions (“ridged”): for each IBD block distribution
$N(x)$ there is a large set of coalescent time distributions $\mu(n)$ that fit
the data equally well. A common problem in such problems is that the
unconstrained maximum likelihood solution is wildly oscillatory; in our case,
the unconstrained solution is not so obviously wrong, since we are helped
considerably by the knowledge that $\mu\geq 0$. For reviews of approaches to
such ill-conditioned inverse problems, see e.g. Petrov and Sizikov (2005) or
Stuart (2010); the problem is also known as “data unfolding” in particle
physics (Cowan, 1998). If one is concerned with finding a point estimate of
$\mu$, most approaches add an additional penalty to the likelihood, which is
known as “regularization” (Tikhonov and Arsenin, 1977) or “ridge regression”
(Hoerl and Kennard, 1970).

However, our goal is parametric inference, and so we must describe the limits
of the “ridge” in the likelihood surface in various directions, (which can be
seen as maximum a posteriori estimates under priors of various strengths).

To do this, we first discretize the data, so that $N_{i}$ is the number of IBD
blocks shared by any of a total of $n_{p}$ distinct pairs of individuals with
inferred genetic lengths falling between $x_{i-1}$ and $x_{i}$. We restrict to
blocks having a minimum length of 2cM long, so that $x_{0}=2$. To find a
discretization so that each $N_{i}$ has roughly equal variance, we choose
$x_{i}$ by first dividing the range of block lengths into 100 bins with equal
numbers of blocks falling in each; discard any bins longer than 1cM; and
divide the remainder of the range up into 1cM chunks. To further reduce
computational time, we also discretize time, effectively requiring $\mu_{n}$
to be constant on each interval $n_{j}\leq n<n_{j+1}$, with
$n_{j+1}-n_{j}=\lfloor{j/10}\rfloor$, for $1\leq j\leq 360$ – so the
resolution is finest for recent times, and the maximum time depth considered
is 6660 meioses, or 99900 years ago. (The discretization and upper bound on
time depth were found to not affect our results.) We then compute by numerical
integration (using the function integrate in R) the matrix $L$ discretizing
the kernel given in (7), so that
$L_{in}=\int_{x_{i-1}}^{x_{i}}\int_{0}^{G}c(x)R(x,z)dK(n,x)dz$ is the kernel
that applied to $\mu$ gives the mean number of true IBD blocks per pair
observed with lengths between $x_{i-1}$ and $x_{i}$, and
$f_{i}=\int_{x_{i-1}}^{x_{i}}f(z)dz$ is the mean number of false positives per
pair with lengths in the same interval. We then sum across chromosomes, as
before. The likelihood of the data is thus

$\exp\left(-n_{p}\sum_{i,n}L_{in}\mu_{n}+f_{i}\right)\prod_{i}\frac{1}{N_{i}!}\left(n_{p}\sum_{n}L_{in}\mu_{n}+f_{i}\right)^{N_{i}}.$
(9)

To the (negative) log likelihood we add a penalization $\gamma$, after
rescaling by the number of pairs $n_{p}$ (which does not affect the result but
makes penalization strengths comparable between pairs of populations), and use
numerical optimization (the L-BFGS-B method in optim, R Development Core Team,
2012) to minimize the resulting functional (which omits terms independent of
$\mu$)

$\mathcal{L}(\mu;\gamma,N)=\sum_{i,n}L_{in}\mu_{n}-\sum_{i}\frac{N_{i}}{n_{p}}\log\left(\sum_{n}L_{in}\mu_{n}+f_{i}\right)+\frac{\gamma(\mu)}{n_{p}}.$
(10)

Often we will fix the functional form of the penalization and vary its
strength, so that $\gamma(\mu)=\gamma_{0}z(\mu)$, in which case we will write
$\mathcal{L}(\mu;\gamma_{0},N)$ for $\mathcal{L}(\mu;\gamma_{0}\,z(\mu),N)$.

For instance, the leftmost panels in figure 4 show the minimizing solutions
$\mu$ for $\gamma(\mu)=0$ (no penalization) and for
$\gamma(\mu)=\gamma_{0}\sum_{n}(\mu_{n+1}-\mu_{n})^{2}$ (“roughness”
penalization). Because our aim is to describe extremal reasonable estimates
$\mu$, in this and in other cases, we have chosen the strength of penalization
$\gamma_{0}$ to be “as large as is reasonable”, choosing the largest
$\gamma_{0}$ such that the minimizing $\mu$ has log likelihood differing by no
more than 2 units from the unconstrained optimum. This choice of cutoff can be
justified as in Edwards (1984), gave quite similar answers to other methods,
and performed well on simulated population histories (see supplemental
document).

This can be thought of as taking the strongest prior that still gives us
“reasonable” maximum a posteriori answers. Note that the optimization is over
nonnegative distributions $\mu$ also satisfying $\sum_{n}\mu(n)\leq 1$
(although the latter condition does not enter in practice).

We would also like to determine bounds on total numbers of shared genetic
ancestors who lived during particular time intervals, by determining e.g. the
minimum and maximum numbers of such ancestors that are consistent with the
data. Such bounds are shown in figure 5. To obtain a lower bound for the time
period between $n_{1}$ and $n_{2}$ generations, we penalized the total amount
of shared ancestry during this interval, using the penalizations
$\gamma_{-}(\mu)=\gamma_{0}^{-}\left(\sum_{n=n_{1}}^{n_{2}}\mu(n)\right)^{2}$,
and choosing $\gamma_{0}^{-}$ to give a drop of 2 log likelihood units, as
described above. The lower bound is then the total amount of coalescence
$\sum_{n=n_{1}}^{n_{2}}\mu_{-}(n)$ for $\mu_{-}$ minimizing
$\mathcal{L}(\cdot;\gamma_{-},N)$. The upper bound is found by penalizing
total shared ancestry outside this interval, i.e. by applying the penalization
$\gamma_{+}(\mu)=\gamma_{0}^{+}\left(\sum_{n<n_{1}}\mu(n)+\sum_{n>n_{2}}\mu(n)\right)^{2}$.
It is almost always the case that lower bounds are zero, since there is
sufficient wiggle room in the likelihood surface to explain the observed block
length distribution using peaks just below $n_{1}$ and above $n_{2}$. Examples
are shown in supplemental figure S14. On the other hand, upper bounds seem
fairly reliable.

In the above we have assumed that the minimizer of $\mathcal{L}$ is unique,
thus glossing over e.g. finding appropriate starting points for the
optimization. In practice, we obtained good starting points by solving the
natural approximating least-squares problem, using quadprog (Turlach and
Weingessel, 2011) in R. We then evaluated uniqueness of the minimizer by using
different starting points, and found that if necessary, adding only a very
small penalization term was enough to ensure convergence to a unique solution.

#### Testing the method

To test this method, we implemented a whole-genome coalescent IBD simulator,
and applied our inference methods to the results under various demography
scenarios. We also used these simulations to evaluate the sensitivity of our
method to misestimation of power or false positive rates. The simulations, and
the results, are described in Supplemental Document 1; in all cases, the
simulations showed that the method performed well to the level of uncertainty
discussed throughout the text and confirmed our understanding of the method
described above. We also found that misestimation of false positive rate only
affects estimated numbers of common ancestors by a comparable amount, and that
misestimation of blocks less than 4cM long mostly affects estimates older than
about 2000 years. Therefore, if our false positive rates above 2cM are off by
10% (the range that seems reasonable), which would change our estimated
numbers of blocks by about 1%, this would only change our estimated numbers of
shared ancestors by a few percent.

#### Extending to shorter blocks

We only used blocks longer than 2cM to infer ages of common ancestors, in part
because the model we use does not seem to fit the data below this threshold.
Attempts to apply the methods to all blocks longer than 1cM reveals that there
is no history of rates of common ancestry that, under this model, produces a
block length distribution reasonably close to the one observed – small, but
significant deviations occur below about 2cM. This occurs probably in part
because our estimate of false positive rate is expected to be less accurate at
these short lengths. Furthermore, our model does not explicitly model the
overlap of multiple short IBD segments to create on long segment deriving from
different ancestors, which could start to have a significant effect at short
lengths. (The effect on long blocks we model as error in length estimation.)
This could be incorporated into a model (in a way analogous to Li and Durbin,
2011), but consideration of when several contiguous blocks of IBD might have
few enough differences to be detected as a long IBD block quickly runs into
the need for a model of IBD detection, which we here treat as a black box. Use
of these shorter blocks, which would allow inference of older ancestry, will
need different methods, and probably sequencing rather than genotyping data.

###  4.8 Numbers of common ancestors

Estimated numbers of genetic common ancestors can be found by simply solving
for $N(0)$ using an estimate of $\mu(n)$ in equations (5) and (6) (still
restricting to genetic ancestors on the autosomes). These tell us that given
the distribution $\mu(n)$, the mean number of genetic common ancestors coming
from generation $n/2$ – i.e. the mean number of IBD blocks of any length
inherited from such common ancestors – is
$N(0)=\mu(n)\sum_{k=1}^{22}\left(nG_{k}+1\right)$, where $G_{k}$ is the total
sex-averaged genetic length of the $k^{\mathrm{th}}$ human chromosome. Since
the total sex-averaged map length of the human autosomes is about 32 Morgans,
this is about $\mu(n)(32n+22)$. This procedure has been used in figures 4 and
5.

Converting shared IBD blocks to numbers of shared genealogical common
ancestors is more problematic. Suppose that modern-day individuals $a$ and $b$
both have $c$ as a grandn-1parent. Using equation (6) at $x=0$, we know that
the mean number of blocks that $a$ and $b$ both inherit from $c$ is $r(2n)$,
with $r(n):=2^{-n}(32n+22)$, since each block has chance $2^{-2n}$ of being
inherited across $2n$ meioses. First treat the endpoints of each distinct path
of length $n$ back through the pedigree as a grandn-1parent, so that everyone
has exactly $2^{n}$ grandn-1parents, and some ancestors will be
grandn-1parents many times over. Then if $a$ and $b$ share $m$ genetic
grandn-1parents, a moment estimator for the number of genealogical
grandn-1parents is $m/r(n)$. However, the geometric growth of $r(n)$ means
that small uncertainties in $n$ have large effects on the estimated numbers of
genealogical common ancestors – and we have large uncertainties in $n$.

Despite these difficulties, we can still get some order-of-magnitude
estimates. For instance, we estimate that someone from Hungary shares on
average about 5 genetic common ancestors with someone from the UK between 18
and 50 generations ago. Since $1/r(36)=5.8\times 10^{7}$, we would
conservatively estimate that for every genetic common ancestor there are tens
of millions of genealogical common ancestors. Most of these ancestors must be
genealogical common ancestors many times over, but these must still represent
at least thousands of distinct individuals.

## Acknowledgements

Thanks to Razib Khan, Sharon Browning, and Don Conrad for several useful
discussions, and to Jeremy Berg, Ewan Birney, Yaniv Brandvain, Joe Pickrell,
Jonathan Pritchard, Alisa Sedghifar, and Joel Smith for useful comments on
earlier drafts. We also thank the four anonymous reviewers, as well as Amy
Williams (at Haldane’s sieve), for their helpful suggestions.

## References

  * Albrechtsen et al. (2010) A. Albrechtsen, I. Moltke, and R. Nielsen.  Natural selection and the distribution of identity-by-descent in the human genome.  _Genetics_ , 186(1):295–308, Sept. 2010.  doi: 10.1534/genetics.110.113977.  URL http://www.ncbi.nlm.nih.gov/pmc/articles/PMC2940294.
  * Auton et al. (2009) A. Auton, K. Bryc, A. R. Boyko, K. E. Lohmueller, J. Novembre, A. Reynolds, A. Indap, M. H. Wright, J. D. Degenhardt, R. N. Gutenkunst, K. S. King, M. R. Nelson, and C. D. Bustamante.  Global distribution of genomic diversity underscores rich complex history of continental human populations.  _Genome Res_ , 19(5):795–803, May 2009.  doi: 10.1101/gr.088898.108.  URL http://www.ncbi.nlm.nih.gov/pubmed/19218534.
  * Barford (2001) P. Barford.  _The early Slavs: culture and society in early medieval Eastern Europe_.  Cornell Univ Press, 2001.
  * Brown et al. (2012) M. D. Brown, C. G. Glazner, C. Zheng, and E. A. Thompson.  Inferring coancestry in population samples in the presence of linkage disequilibrium.  _Genetics_ , 2012.  doi: 10.1534/genetics.111.137570.  URL http://www.genetics.org/content/early/2012/01/23/genetics.111.137570.abstract.
  * Browning and Browning (2011) B. L. Browning and S. R. Browning.  A fast, powerful method for detecting identity by descent.  _American Journal of Human Genetics_ , 88(2):173–182, Feb. 2011.  ISSN 00029297.  URL http://linkinghub.elsevier.com/retrieve/pii/S0002929711000115.
  * Cann et al. (1987) R. L. Cann, M. Stoneking, and A. C. Wilson.  Mitochondrial DNA and human evolution.  _Nature_ , 325(6099):31–36, Jan. 1987.  doi: 10.1038/325031a0.  URL http://www.ncbi.nlm.nih.gov/pubmed/3025745.
  * Carmi et al. (2012) S. Carmi, P. F. Palamara, V. Vacic, T. Lencz, A. Darvasi, and I. Pe’er.  The variance of identity-by-descent sharing in the Wright-Fisher model.  _Genetics_ , Dec. 2012.  doi: 10.1534/genetics.112.147215.  URL http://arxiv.org/abs/1206.4745.
  * Chang (1999) J. Chang.  Recent common ancestors of all present-day individuals.  _Advances in Applied Probability_ , 31:1002–1026, 1999\.  URL http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.aap/1029955257.
  * Chapman and Thompson (2002) N. H. Chapman and E. A. Thompson.  The effect of population history on the lengths of ancestral chromosome segments.  _Genetics_ , 162(1):449–458, Sept. 2002.  URL http://www.ncbi.nlm.nih.gov/pmc/articles/PMC1462250/.
  * Cowan (1998) G. Cowan.  _Statistical data analysis_.  Oxford University Press, USA, 1998.
  * Davies (2010) N. Davies.  _Europe: A History_.  Random House, 2010.  ISBN 9781407091792.
  * Donnelly (1983) K. P. Donnelly.  The probability that related individuals share some section of genome identical by descent.  _Theor Popul Biol_ , 23(1):34–63, Feb. 1983.  URL http://www.ncbi.nlm.nih.gov/pubmed/6857549.
  * Edwards (1984) A. Edwards.  _Likelihood_.  Cambridge Science Classics. Cambridge University Press, 1984.  ISBN 9780521318716.
  * Epstein and Schotland (2008) C. L. Epstein and J. Schotland.  The bad truth about Laplace’s transform.  _SIAM Review_ , 50(3):504–520, 2008.  ISSN 0036-1445.  doi: 10.1137/060657273.  URL http://dx.doi.org/10.1137/060657273.
  * Fenner (2005) J. N. Fenner.  Cross-cultural estimation of the human generation interval for use in genetics-based population divergence studies.  _American Journal of Physical Anthropology_ , 128(2):415–423, 2005.  ISSN 1096-8644.  doi: 10.1002/ajpa.20188.  URL http://dx.doi.org/10.1002/ajpa.20188.
  * Fisher (1954) R. A. Fisher.  A fuller theory of ‘Junctions’ in inbreeding.  _Heredity_ , 8(2):187–197, Aug. 1954.  ISSN 0018067X.  URL http://dx.doi.org/10.1038/hdy.1954.17.
  * Giglio et al. (2001) S. Giglio, K. W. Broman, N. Matsumoto, V. Calvari, G. Gimelli, T. Neumann, H. Ohashi, L. Voullaire, D. Larizza, R. Giorda, J. L. Weber, D. H. Ledbetter, and O. Zuffardi.  Olfactory receptor-gene clusters, genomic-inversion polymorphisms, and common chromosome rearrangements.  _Am J Hum Genet_ , 68(4):874–883, Apr. 2001.  doi: 10.1086/319506.  URL http://www.ncbi.nlm.nih.gov/pubmed/11231899.
  * Gillett (2006) A. Gillett.  Ethnogenesis: A contested model of early medieval Europe.  _History Compass_ , 4(2):241–260, 2006.  ISSN 1478-0542.  doi: 10.1111/j.1478-0542.2006.00311.x.  URL http://dx.doi.org/10.1111/j.1478-0542.2006.00311.x.
  * Gravel (2012) S. Gravel.  Population genetics models of local ancestry.  _Genetics_ , 191(2):607–619, June 2012.  doi: 10.1534/genetics.112.139808.  URL http://www.ncbi.nlm.nih.gov/pubmed/22491189.
  * Griffiths and Marjoram (1997) R. C. Griffiths and P. Marjoram.  An ancestral recombination graph.  In _Progress in population genetics and human evolution (Minneapolis, MN, 1994)_ , volume 87 of _IMA Vol. Math. Appl._ , pages 257–270. Springer, New York, 1997.  URL http://www.math.canterbury.ac.nz/~r.sainudiin/recomb/ima.pdf.
  * Grimmett and Stirzaker (2001) G. Grimmett and D. Stirzaker.  _Probability and random processes_.  Oxford University Press, 2001.
  * Gusev et al. (2009) Gusev, J. K. Lowe, M. Stoffel, M. J. Daly, D. Altshuler, J. L. Breslow, J. M. Friedman, and I. Pe’er.  Whole population, genome-wide mapping of hidden relatedness.  _Genome Res_ , 19(2):318–326, Feb. 2009.  doi: 10.1101/gr.081398.108.  URL http://www.ncbi.nlm.nih.gov/pmc/articles/PMC2652213.
  * Gusev et al. (2012) A. Gusev, P. F. Palamara, G. Aponte, Z. Zhuang, A. Darvasi, P. Gregersen, and I. Pe’er.  The architecture of long-range haplotypes shared within and across populations.  _Molecular Biology and Evolution_ , 29(2):473–486, 2012.  doi: 10.1093/molbev/msr133.  URL http://mbe.oxfordjournals.org/content/29/2/473.abstract.
  * Halsall (2005) G. Halsall.  The Barbarian invasions.  In P. Fouracre, editor, _The New Cambridge Medieval History_ , number v. 1 in The New Cambridge Medieval History, chapter 2, pages 38–55. Cambridge University Press, 2005.  ISBN 9780521362917.
  * Hamp (1966) E. Hamp.  The position of Albanian.  _Ancient Indo-European Dialects_ , pages 97–121, 1966.  URL http://groznijat.tripod.com/balkan/ehamp.html.
  * Harris and Nielsen (2012) K. Harris and R. Nielsen.  Inferring demographic history from a spectrum of shared haplotype lengths, 2012.
  * Henn et al. (2012a) B. M. Henn, L. R. Botigué, S. Gravel, W. Wang, A. Brisbin, J. K. Byrnes, K. Fadhlaoui-Zid, P. A. Zalloua, A. Moreno-Estrada, J. Bertranpetit, C. D. Bustamante, and D. Comas.  Genomic ancestry of North Africans supports back-to-Africa migrations.  _PLoS Genet_ , 8(1), Jan. 2012a.  doi: 10.1371/journal.pgen.1002397.  URL http://www.ncbi.nlm.nih.gov/pubmed/22253600.
  * Henn et al. (2012b) B. M. Henn, L. Hon, J. M. Macpherson, N. Eriksson, S. Saxonov, I. Pe’er, and J. L. Mountain.  Cryptic distant relatives are common in both isolated and cosmopolitan genetic samples.  _PLoS ONE_ , 7(4):e34267, 04 2012b.  doi: 10.1371/journal.pone.0034267.
  * Hoerl and Kennard (1970) A. E. Hoerl and R. W. Kennard.  Ridge regression: Biased estimation for nonorthogonal problems.  _Technometrics_ , 12(1):pp. 55–67, 1970.  ISSN 00401706.  URL http://www.jstor.org/stable/1267351.
  * Hudson (1990) R. Hudson.  Gene genealogies and the coalescent process.  _Oxford Surveys in Evolutionary Biology_ , 7(1):44, 1990.  URL http://web.eve.ucdavis.edu/pbg298/pdfs/Hudson_OxfordSurveysEvolBiol_1991.pdf.
  * Huff et al. (2011) C. D. Huff, D. J. Witherspoon, T. S. Simonson, J. Xing, W. S. Watkins, Y. Zhang, T. M. Tuohy, D. W. Neklason, R. W. Burt, S. L. Guthery, S. R. Woodward, and L. B. Jorde.  Maximum-likelihood estimation of recent shared ancestry (ERSA).  _Genome Res._ , 21:768–774, May 2011.  URL http://www.ncbi.nlm.nih.gov/pubmed/21324875.
  * International HapMap Consortium et al. (2007) International HapMap Consortium, K. A. Frazer, D. G. Ballinger, D. R. Cox, D. A. Hinds, L. L. Stuve, R. A. Gibbs, J. W. Belmont, A. Boudreau, P. Hardenbol, S. M. Leal, S. Pasternak, D. A. Wheeler, T. D. Willis, F. Yu, H. Yang, C. Zeng, Y. Gao, H. Hu, W. Hu, C. Li, W. Lin, S. Liu, H. Pan, X. Tang, J. Wang, W. Wang, J. Yu, B. Zhang, Q. Zhang, H. Zhao, H. Zhao, J. Zhou, S. B. Gabriel, R. Barry, B. Blumenstiel, A. Camargo, M. Defelice, M. Faggart, M. Goyette, S. Gupta, J. Moore, H. Nguyen, R. C. Onofrio, M. Parkin, J. Roy, E. Stahl, E. Winchester, L. Ziaugra, D. Altshuler, Y. Shen, Z. Yao, W. Huang, X. Chu, Y. He, L. Jin, Y. Liu, Y. Shen, W. Sun, H. Wang, Y. Wang, Y. Wang, X. Xiong, L. Xu, M. M. Waye, S. K. Tsui, H. Xue, J. T. Wong, L. M. Galver, J. B. Fan, K. Gunderson, S. S. Murray, A. R. Oliphant, M. S. Chee, A. Montpetit, F. Chagnon, V. Ferretti, M. Leboeuf, J. F. Olivier, M. S. Phillips, S. Roumy, C. Sallée, A. Verner, T. J. Hudson, P. Y. Kwok, D. Cai, D. C. Koboldt, R. D. Miller, L. Pawlikowska, P. Taillon-Miller, M. Xiao, L. C. Tsui, W. Mak, Y. Q. Song, P. K. Tam, Y. Nakamura, T. Kawaguchi, T. Kitamoto, T. Morizono, A. Nagashima, Y. Ohnishi, A. Sekine, T. Tanaka, T. Tsunoda, P. Deloukas, C. P. Bird, M. Delgado, E. T. Dermitzakis, R. Gwilliam, S. Hunt, J. Morrison, D. Powell, B. E. Stranger, P. Whittaker, D. R. Bentley, M. J. Daly, P. I. de Bakker, J. Barrett, Y. R. Chretien, J. Maller, S. McCarroll, N. Patterson, I. Pe’er, A. Price, S. Purcell, D. J. Richter, P. Sabeti, R. Saxena, S. F. Schaffner, P. C. Sham, P. Varilly, D. Altshuler, L. D. Stein, L. Krishnan, A. V. Smith, M. K. Tello-Ruiz, G. A. Thorisson, A. Chakravarti, P. E. Chen, D. J. Cutler, C. S. Kashuk, S. Lin, G. R. Abecasis, W. Guan, Y. Li, H. M. Munro, Z. S. Qin, D. J. Thomas, G. McVean, A. Auton, L. Bottolo, N. Cardin, S. Eyheramendy, C. Freeman, J. Marchini, S. Myers, C. Spencer, M. Stephens, P. Donnelly, L. R. Cardon, G. Clarke, D. M. Evans, A. P. Morris, B. S. Weir, T. Tsunoda, J. C. Mullikin, S. T. Sherry, M. Feolo, A. Skol, H. Zhang, C. Zeng, H. Zhao, I. Matsuda, Y. Fukushima, D. R. Macer, E. Suda, C. N. Rotimi, C. A. Adebamowo, I. Ajayi, T. Aniagwu, P. A. Marshall, C. Nkwodimmah, C. D. Royal, M. F. Leppert, M. Dixon, A. Peiffer, R. Qiu, A. Kent, K. Kato, N. Niikawa, I. F. Adewole, B. M. Knoppers, M. W. Foster, E. W. Clayton, J. Watkin, R. A. Gibbs, J. W. Belmont, D. Muzny, L. Nazareth, E. Sodergren, G. M. Weinstock, D. A. Wheeler, I. Yakub, S. B. Gabriel, R. C. Onofrio, D. J. Richter, L. Ziaugra, B. W. Birren, M. J. Daly, D. Altshuler, R. K. Wilson, L. L. Fulton, J. Rogers, J. Burton, N. P. Carter, C. M. Clee, M. Griffiths, M. C. Jones, K. McLay, R. W. Plumb, M. T. Ross, S. K. Sims, D. L. Willey, Z. Chen, H. Han, L. Kang, M. Godbout, J. C. Wallenburg, P. L’Archevêque, G. Bellemare, K. Saeki, H. Wang, D. An, H. Fu, Q. Li, Z. Wang, R. Wang, A. L. Holden, L. D. Brooks, J. E. McEwen, M. S. Guyer, V. O. Wang, J. L. Peterson, M. Shi, J. Spiegel, L. M. Sung, L. F. Zacharia, F. S. Collins, K. Kennedy, R. Jamieson, and J. Stewart.  A second generation human haplotype map of over 3.1 million SNPs.  _Nature_ , 449(7164):851–861, Oct. 2007.  doi: 10.1038/nature06258.  URL http://www.ncbi.nlm.nih.gov/pubmed/17943122.
  * Jakkula et al. (2008) E. Jakkula, K. Rehnström, T. Varilo, O. P. Pietiläinen, T. Paunio, N. L. Pedersen, U. deFaire, M. R. Järvelin, J. Saharinen, N. Freimer, S. Ripatti, S. Purcell, A. Collins, M. J. Daly, A. Palotie, and L. Peltonen.  The genome-wide patterns of variation expose significant substructure in a founder population.  _Am J Hum Genet_ , 83(6):787–794, Dec. 2008.  doi: 10.1016/j.ajhg.2008.11.005.  URL http://www.ncbi.nlm.nih.gov/pubmed/19061986.
  * Keller et al. (2012) A. Keller, A. Graefen, M. Ball, M. Matzas, V. Boisguerin, F. Maixner, P. Leidinger, C. Backes, R. Khairat, M. Forster, B. Stade, A. Franke, J. Mayer, J. Spangler, S. McLaughlin, M. Shah, C. Lee, T. T. Harkins, A. Sartori, A. Moreno-Estrada, B. Henn, M. Sikora, O. Semino, J. Chiaroni, S. Rootsi, N. M. Myres, V. M. Cabrera, P. A. Underhill, C. D. Bustamante, E. E. Vigl, M. Samadelli, G. Cipollini, J. Haas, H. Katus, B. D. O’Connor, M. R. Carlson, B. Meder, N. Blin, E. Meese, C. M. Pusch, and A. Zink.  New insights into the Tyrolean Iceman’s origin and phenotype as inferred by whole-genome sequencing.  _Nat Commun_ , 3:698–698, 2012.  doi: 10.1038/ncomms1701.  URL http://www.ncbi.nlm.nih.gov/pubmed/22426219.
  * Kingman (1982) J. F. C. Kingman.  On the genealogy of large populations.  _Journal of Applied Probability_ , 19:27–43, 1982.  ISSN 00219002.  URL http://www.jstor.org/stable/3213548.
  * Kobyliński (2005) Z. Kobyliński.  The Slavs.  In P. Fouracre, editor, _The New Cambridge Medieval History_ , number v. 1 in The New Cambridge Medieval History, chapter 19, pages 524–544. Cambridge University Press, 2005.  ISBN 9780521362917.
  * Lao et al. (2008) O. Lao, T. T. Lu, M. Nothnagel, O. Junge, S. Freitag-Wolf, A. Caliebe, M. Balascakova, J. Bertranpetit, L. A. Bindoff, D. Comas, G. Holmlund, A. Kouvatsi, M. Macek, I. Mollet, W. Parson, J. Palo, R. Ploski, A. Sajantila, A. Tagliabracci, U. Gether, T. Werge, F. Rivadeneira, A. Hofman, A. G. Uitterlinden, C. Gieger, H. E. Wichmann, A. Rüther, S. Schreiber, C. Becker, P. Nürnberg, M. R. Nelson, M. Krawczak, and M. Kayser.  Correlation between genetic and geographic structure in Europe.  _Curr Biol_ , 18(16):1241–1248, Aug. 2008.  doi: 10.1016/j.cub.2008.07.049.  URL http://www.ncbi.nlm.nih.gov/pubmed/18691889.
  * Lawson et al. (2012) D. J. Lawson, G. Hellenthal, S. Myers, and D. Falush.  Inference of population structure using dense haplotype data.  _PLoS Genet_ , 8(1):e1002453, 01 2012.  doi: 10.1371/journal.pgen.1002453.  URL http://dx.doi.org/10.1371%2Fjournal.pgen.1002453.
  * Li and Durbin (2011) H. Li and R. Durbin.  Inference of human population history from individual whole-genome sequences.  _Nature_ , advance online publication:–, July 2011.  ISSN 14764687.  URL http://dx.doi.org/10.1038/nature10231.
  * Malécot (1969) G. Malécot.  _The Mathematics of Heredity_.  Freeman, 1969.  ISBN 9780716706786.  Translated from the French edition, 1948.
  * McCullagh and Nelder (1989) P. McCullagh and J. Nelder.  _Generalized Linear Models, Second Edition_.  Chapman and Hall/CRC Monographs on Statistics and Applied Probability Series. Chapman & Hall, 1989.  ISBN 9780412317606.
  * McVean (2009) G. McVean.  A genealogical interpretation of principal components analysis.  _PLoS Genet_ , 5(10):e1000686, 10 2009.  doi: 10.1371/journal.pgen.1000686.  URL http://dx.doi.org/10.1371%2Fjournal.pgen.1000686.
  * Menozzi et al. (1978) P. Menozzi, A. Piazza, and L. Cavalli-Sforza.  Synthetic maps of human gene frequencies in Europeans.  _Science_ , 201(4358):786–792, Sept. 1978.  URL http://www.ncbi.nlm.nih.gov/pubmed/356262.
  * Moorjani et al. (2011) P. Moorjani, N. Patterson, J. N. Hirschhorn, A. Keinan, L. Hao, G. Atzmon, E. Burns, H. Ostrer, A. L. Price, and D. Reich.  The history of African gene flow into Southern Europeans, Levantines, and Jews.  _PLoS Genet._ , 7:e1001373, Apr. 2011.  URL http://www.ncbi.nlm.nih.gov/pubmed/21533020.
  * Nelson et al. (2008) M. R. Nelson, K. Bryc, K. S. King, A. Indap, A. R. Boyko, J. Novembre, L. P. Briley, Y. Maruyama, D. M. Waterworth, G. Waeber, P. Vollenweider, J. R. Oksenberg, S. L. Hauser, H. A. Stirnadel, J. S. Kooner, J. C. Chambers, B. Jones, V. Mooser, C. D. Bustamante, A. D. Roses, D. K. Burns, M. G. Ehm, and E. H. Lai.  The Population Reference Sample, POPRES: a resource for population, disease, and pharmacological genetics research.  _Am J Hum Genet_ , 83(3):347–358, Sept. 2008\.  doi: 10.1016/j.ajhg.2008.08.005.  URL http://www.ncbi.nlm.nih.gov/pmc/articles/PMC2556436.
  * Nelson et al. (2012) M. R. Nelson, D. Wegmann, M. G. Ehm, D. Kessner, P. St. Jean, C. Verzilli, J. Shen, Z. Tang, S.-A. Bacanu, D. Fraser, L. Warren, J. Aponte, M. Zawistowski, X. Liu, H. Zhang, Y. Zhang, J. Li, Y. Li, L. Li, P. Woollard, S. Topp, M. D. Hall, K. Nangle, J. Wang, G. Abecasis, L. R. Cardon, S. Zöllner, J. C. Whittaker, S. L. Chissoe, J. Novembre, and V. Mooser.  An abundance of rare functional variants in 202 drug target genes sequenced in 14,002 people.  _Science_ , 2012.  doi: 10.1126/science.1217876.  URL http://www.sciencemag.org/content/early/2012/05/16/science.1217876.abstract.
  * Novembre and Ramachandran (2011) J. Novembre and S. Ramachandran.  Perspectives on human population structure at the cusp of the sequencing era.  _Annu Rev Genomics Hum Genet_ , 12:245–274, Sept. 2011\.  doi: 10.1146/annurev-genom-090810-183123.  URL http://www.ncbi.nlm.nih.gov/pubmed/21801023.
  * Novembre and Stephens (2008) J. Novembre and M. Stephens.  Interpreting principal component analyses of spatial population genetic variation.  _Nat Genet_ , 40(5):646–649, May 2008.  ISSN 1061-4036.  URL http://dx.doi.org/10.1038/ng.139.
  * Novembre et al. (2008) J. Novembre, T. Johnson, K. Bryc, Z. Kutalik, A. R. Boyko, A. Auton, A. Indap, K. S. King, S. Bergmann, M. R. Nelson, M. Stephens, and C. D. Bustamante.  Genes mirror geography within Europe.  _Nature_ , 456(7218):98–101, Nov. 2008.  doi: 10.1038/nature07331.  URL http://www.ncbi.nlm.nih.gov/pubmed/18758442.
  * O’Dushlaine et al. (2010) C. T. O’Dushlaine, D. Morris, V. Moskvina, G. Kirov, International Schizophrenia Consortium, M. Gill, A. Corvin, J. F. Wilson, and G. L. Cavalleri.  Population structure and genome-wide patterns of variation in Ireland and Britain.  _Eur J Hum Genet_ , 18(11):1248–1254, Nov. 2010\.  doi: 10.1038/ejhg.2010.87.  URL http://www.ncbi.nlm.nih.gov/pmc/articles/PMC2987482/.
  * Palamara et al. (2012) P. F. Palamara, T. Lencz, A. Darvasi, and I. Pe’er.  Length distributions of identity by descent reveal fine-scale demographic history, Oct. 2012.  ISSN 00029297.
  * Patterson et al. (2006) N. Patterson, A. L. Price, and D. Reich.  Population structure and eigenanalysis.  _PLoS Genet_ , 2(12):e190, 12 2006.  doi: 10.1371/journal.pgen.0020190.  URL http://dx.plos.org/10.1371%2Fjournal.pgen.0020190.
  * Patterson et al. (2012) N. Patterson, P. Moorjani, Y. Luo, S. Mallick, N. Rohland, Y. Zhan, T. Genschoreck, T. Webster, and D. Reich.  Ancient admixture in human history.  _Genetics_ , 192(3):1065–1093, Nov. 2012.  doi: 10.1534/genetics.112.145037.  URL http://www.ncbi.nlm.nih.gov/pubmed/22960212.
  * Petrov and Sizikov (2005) Y. Petrov and V. Sizikov.  _Well-posed, ill-posed, and intermediate problems with applications_ , volume 49.  Walter de Gruyter, 2005.
  * Plate (2011) T. Plate.  _RSVGTipsDevice: An R SVG graphics device with dynamic tips and hyperlinks_ , 2011.  URL http://CRAN.R-project.org/package=RSVGTipsDevice.  R package version 1.0-2, based on RSvgDevice by T Jake Luciani.
  * Pool and Nielsen (2009) J. E. Pool and R. Nielsen.  Inference of historical changes in migration rate from the lengths of migrant tracts.  _Genetics_ , 181(2):711–719, Feb. 2009.  doi: 10.1534/genetics.108.098095.  URL http://www.ncbi.nlm.nih.gov/pubmed/19087958.
  * Powell et al. (2010) J. E. Powell, P. M. Visscher, and M. E. Goddard.  Reconciling the analysis of IBD and IBS in complex trait studies.  _Nat Rev Genet_ , 11(11):800–805, Nov. 2010.  doi: 10.1038/nrg2865.  URL http://www.ncbi.nlm.nih.gov/pubmed/20877324.
  * Price et al. (2006) A. L. Price, N. J. Patterson, R. M. Plenge, M. E. Weinblatt, N. A. Shadick, and D. Reich.  Principal components analysis corrects for stratification in genome-wide association studies.  _Nat Genet_ , 38(8):904–909, Aug. 2006.  doi: 10.1038/ng1847.  URL http://www.ncbi.nlm.nih.gov/pubmed/16862161.
  * Price et al. (2009) A. L. Price, A. Helgason, S. Palsson, H. Stefansson, D. St Clair, O. A. Andreassen, D. Reich, A. Kong, and K. Stefansson.  The impact of divergence time on the nature of population structure: an example from Iceland.  _PLoS Genet_ , 5(6), June 2009.  doi: 10.1371/journal.pgen.1000505.  URL http://www.ncbi.nlm.nih.gov/pubmed/19503599.
  * Purcell et al. (2007) S. Purcell, B. Neale, K. Todd-Brown, L. Thomas, M. A. Ferreira, D. Bender, J. Maller, P. Sklar, P. I. de Bakker, M. J. Daly, and P. C. Sham.  PLINK: a tool set for whole-genome association and population-based linkage analyses.  _Am J Hum Genet_ , 81(3):559–575, Sept. 2007\.  doi: 10.1086/519795.  URL http://www.ncbi.nlm.nih.gov/pubmed/17701901.
  * R Development Core Team (2012) R Development Core Team.  _R: A Language and Environment for Statistical Computing_.  R Foundation for Statistical Computing, Vienna, Austria, 2012.  URL http://www.R-project.org/.  ISBN 3-900051-07-0.
  * Ralph and Coop (2013) P. Ralph and G. Coop.  Data from: The geography of recent genetic ancestry across Europe, 2013.  URL http://dx.doi.org/10.5061/dryad.57kc5.
  * Rohde et al. (2004) D. L. T. Rohde, S. Olson, and J. T. Chang.  Modelling the recent common ancestry of all living humans.  _Nature_ , 431(7008):562–566, September 2004\.  ISSN 0028-0836.  URL http://dx.doi.org/10.1038/nature02842.
  * Rousset (2002) F. Rousset.  Inbreeding and relatedness coefficients: what do they measure?  _Heredity_ , 88(5):371–380, May 2002.  doi: 10.1038/sj.hdy.6800065.  URL http://www.ncbi.nlm.nih.gov/pubmed/11986874.
  * Skoglund et al. (2012) P. Skoglund, H. Malmström, M. Raghavan, J. Storå, P. Hall, E. Willerslev, M. T. Gilbert, A. Götherström, and M. Jakobsson.  Origins and genetic legacy of Neolithic farmers and hunter-gatherers in Europe.  _Science_ , 336(6080):466–469, Apr. 2012.  doi: 10.1126/science.1216304.  URL http://www.ncbi.nlm.nih.gov/pubmed/22539720.
  * Slatkin (1991) M. Slatkin.  Inbreeding coefficients and coalescence times.  _Genet Res_ , 58(2):167–175, Oct. 1991.  URL http://www.ncbi.nlm.nih.gov/pubmed/1765264.
  * Soares et al. (2010) P. Soares, A. Achilli, O. Semino, W. Davies, V. Macaulay, H. J. Bandelt, A. Torroni, and M. B. Richards.  The archaeogenetics of Europe.  _Curr Biol_ , 20(4):174–183, Feb. 2010.  doi: 10.1016/j.cub.2009.11.054.  URL http://www.ncbi.nlm.nih.gov/pubmed/20178764.
  * Stuart (2010) A. M. Stuart.  Inverse problems: a Bayesian perspective.  _Acta Numer._ , 19:451–559, 2010.  ISSN 0962-4929.  doi: 10.1017/S0962492910000061.  URL http://dx.doi.org/10.1017/S0962492910000061.
  * Takahata (1993) N. Takahata.  Allelic genealogy and human evolution.  _Molecular Biology and Evolution_ , 10(1):2–22, 1993.  URL http://mbe.oxfordjournals.org/content/10/1/2.abstract.
  * Tennessen et al. (2012) 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, and on behalf of the NHLBI Exome Sequencing Project.  Evolution and functional impact of rare coding variation from deep sequencing of human exomes.  _Science_ , May 2012.  doi: 10.1126/science.1219240.  URL http://www.ncbi.nlm.nih.gov/pubmed/22604720.
  * Tikhonov and Arsenin (1977) A. N. Tikhonov and V. Y. Arsenin.  _Solutions of ill-posed problems_.  V. H. Winston & Sons, Washington, D.C.: John Wiley & Sons, New York, 1977.  Translated from the Russian, Preface by translation editor Fritz John, Scripta Series in Mathematics.
  * Turlach and Weingessel (2011) B. A. Turlach and A. Weingessel.  _quadprog: Functions to solve Quadratic Programming Problems._ , 2011\.  URL http://CRAN.R-project.org/package=quadprog.  R package version 1.5-4; S original by Berwin A. Turlach, R port by Andreas Weingessel.
  * Tyler-Smith and Xue (2012) C. Tyler-Smith and Y. Xue.  A British approach to sampling.  _Eur J Hum Genet_ , 20(2):129–130, Feb. 2012\.  ISSN 10184813.  URL http://dx.doi.org/10.1038/ejhg.2011.153.
  * Wakeley (2005) J. Wakeley.  _Coalescent Theory, an Introduction_.  Roberts and Company, Greenwood Village, CO, 2005.
  * Winney et al. (2011) B. Winney, A. Boumertit, T. Day, D. Davison, C. Echeta, I. Evseeva, K. Hutnik, S. Leslie, K. Nicodemus, E. C. Royrvik, S. Tonks, X. Yang, J. Cheshire, P. Longley, P. Mateos, A. Groom, C. Relton, D. T. Bishop, K. Black, E. Northwood, L. Parkinson, T. M. Frayling, A. Steele, J. R. Sampson, T. King, R. Dixon, D. Middleton, B. Jennings, R. Bowden, P. Donnelly, and W. Bodmer.  People of the British Isles: preliminary analysis of genotypes and surnames in a UK-control population.  _Eur J Hum Genet_ , pages 203–210, Aug. 2011.  ISSN 14765438.  URL http://dx.doi.org/10.1038/ejhg.2011.127.
  * Zeileis et al. (2009) A. Zeileis, K. Hornik, and P. Murrell.  Escaping RGBland: Selecting colors for statistical graphics.  _Computational Statistics & Data Analysis_, (53):3259–3270, 2009.  doi: doi:10.1016/j.csda.2008.11.033.

## Supplemental material

Figure S1:  Normalized density of IBD blocks of different lengths, corrected
for SNP density, across all autosomes (see section 4.3 for details). Marked
with a grey bar and “c” are the centromeres; and marked with “8p” is a large,
segregating inversion (Giglio et al., 2001). The grey curve along the bottom
shows normalized SNP density.  Figure S2:  Two measures of overdispersal of
block numbers across individuals (i.e. substructure): Suppose we have $n$
individuals from population $x$, and $N_{iy}$ is the number of IBD blocks of
length at least 1cM that individual $i$ shares with anyone from population
$y$. Our statistic of substructure within $x$ with respect to $y$ is the
variance of these numbers,
$s_{xy}=\frac{1}{n-1}\left(\sum_{i}N_{iy}^{2}-\frac{1}{n}\left(\sum_{i}N_{iy}\right)^{2}\right)$.
We obtained a “null” distribution for this statistic by randomly reassigning
all blocks shared between $x$ and $y$ to an individual from $x$, and used this
to evaluate the strength and the statistical significance of this
substructure. (A) Histogram of the “$p$-value”, of the proportion of 1000
replicates that showed a variance greater than or equal to the observed
variance $s_{xy}$, for all pairs of populations $x$ and $y$ with at least 10
individuals in population $y$. (B) The “$z$ score”, which is observed value
$s_{xy}$ minus mean value divided by standard deviation, estimated using 1000
replicates. The population $x$ is shown on the vertical axis, with text labels
giving $y$, so for instance, Italians show much more substructure with most
other populations than do Irish. Note that sample size still has a large
effect – it is easier to see substructure with respect to the Swiss French
($x=$CHf) because the large number of Swiss French samples allows greater
resolution. A vertical line is shown at $z=5$. Only pairs of populations with
at least 3 samples in country $x$ and 10 samples in country $y$ are shown.
Because of the log scale, only pairs with a positive $z$ score are shown, but
no comparisons had $z<-2.5$, and only three had $z<-2$.  Figure S3:  (A) Mean
numbers of IBD blocks of length at least 1cM per pair of individuals, shown as
a modified Cleveland dotchart, with $\pm$2 standard deviations shown as
horizontal lines. For instance, on the bottom row we see that someone from the
UK shares on average about one IBD block with someone else from the UK and
slightly less than 0.2 blocks with someone from Turkey. Note that in most
cases, the distribution of block numbers is fairly concentrated, and that
nearby populations show quite similar patterns.  Figure S4:  The positions of
our sample of the first two principal components of the genotype matrix, as
produced by EIGENSTRAT (Price et al., 2006). Population centroids are marked
by text and a transparent circle. Note the correspondence to a map of Europe,
after a rotation and flip.  Figure S5:  Comparison of figure 2A in the main
text to figure S4 – the axes are self-explanatory; the colors and symbols are
the same as in figure 2A.  Figure S6:  Comparison of figure 2B in the main
text to figure S4 – the axes are self-explanatory; the colors and symbols are
the same as in figure 2B. The four outlying UK individuals are, as in figure
2B, three who share a very high number of IBD blocks with Italians, and one
who shares a very high number with the Slovakian sample.  Figure S7:
Correlations in IBD rates, for six different length windows (omitted length
windows are similar). If there are $n$ populations, $I(x,y)$ is the mean
number of blocks in the given length range shared by a pair from populations
$x$ and $y$, and $\bar{I}(x)=(1/(n-1))\sum_{z\neq x}I(x,z)$, shown is
$(1/(n-2))\sum_{z\notin\\{x,y\\}}(I(x,z)-\bar{I}(x))(I(y,z)-\bar{I}(y))$.

http://www.eve.ucdavis.edu/plralph/ibd/sharing-rates.svg

Figure S8:  The same plot as figure 3G–I, but rendered as an SVG figure with
tooltips that allow identification of individual points (using R Plate, 2011)
– open the file in a reasonably compliant browser (e.g. Firefox, Opera) or SVG
browser (e.g. squiggle) and hover the mouse over a point of interest to see
the label.  Figure S9:  Mean IBS (“Identity by State”) against geographic
distance, calculated using plink (Purcell et al., 2007) as described in the
main text, using the same groups and fitting the same curves as in figure 3 of
the main text. The lowest set of points, roughly following a line, are mean
IBS with Turkey; unlike with IBD, mean IBS with Cyprus was significantly
higher. In fact, the other rough line of points (between the comparisons to
Turkey and the orange points) is almost entirely mean IBS with Cyprus, as well
as mean IBS to Slovakia. Since Slovakia is only represented by a single
individual in the dataset, we cannot reach further conclusions.  Figure S10:
Goodness-of-fit for our estimated error distribution – points show data from
simulations (described in the text), and lines show the parametric forms of
equations (1). Each simulated IBD block of length $x$ was either found by
BEAGLE (and passed our filters) or was not; and if it was found, it had
inferred length $y=x+\epsilon$, i.e. with length error $\epsilon$. The top
figure shows the probability that a segment of a given length is missed
entirely (and $1-c(x)$) in green, the probability that $\epsilon>0$ given the
segment was found (and $\gamma(x)$) in black, and the probability that