{'fraction_non_alphanumeric': 0.05280146561688949, 'fraction_numerical': 0.015768467427100828, 'mean_word_length': 3.8402829093212287, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 22, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Approximating genealogies for partially linked neutral loci under a selective sweep

Consider a genetic locus carrying a strongly beneficial allele which has recently fixed in a large population. As strongly beneficial alleles fix quickly, sequence diversity at partially linked neutral loci is reduced. This phenomenon is known as a selective sweep. The fixation of the beneficial allele not only affects sequence diversity at single neutral loci but also the joint allele distribution of several partially linked neutral loci. This distribution can be studied using the ancestral recombination graph for samples of partially linked neutral loci during the selective sweep. To approximate this graph, we extend recent work by Schweinsberg&Durrett 2005 and Etheridge, Pfaffelhuber&Wakolbinger 2006 using a marked Yule tree for the genealogy at a single neutral locus linked to a strongly beneficial one. We focus on joint genealogies at two partially linked neutral loci in the case of large selection coefficients \alpha and recombination rates \rho = O(\alpha/\log\alpha) between loci. Our approach leads to a full description of the genealogy with accuracy of O((\log \alpha)^{-2}) in probability. As an application, we derive the expectation of Lewontin's D as a measure for non-random association of alleles.


Introduction
The model of selective sweeps, also known as genetic hitchhiking, introduced by Maynard-Smith and Haigh in [MSH74], is the starting point for a large body of both empirical and theoretical population genetic studies ( [Nur05]). It predicts that sequence diversity is reduced close to a strongly selected locus on a recombining genome near the time of fixation of the beneficial allele. Theoretical studies aim at describing these patterns of genetic diversity in detail while empirical work uses this prediction to identify genes under selection.
If a species or a population adapts to its environment, several genes might be under strong selection. Moreover, if the function of genes were known, we would have predictions as to which genes are responsible for the adaptive process. Unfortunately, functional information is scarce. Without functional knowledge and in the presence of recombination, the model of selective sweeps helps to identify candidate genes affected by recent selective pressures. Genome scans are carried out for a sample of individuals, which show patterns of sequence diversity at lots of marker loci in the whole genome ([NWK + 05]). If a marker shows low diversity, statistical tests help to decide if a gene under selection is located nearby ( [KS02,LS05]).
Most theoretical studies of selective sweeps have focused on a model with one selective and one partially linked neutral locus ([MSH74, SWL92, KHL89, Bar98,SD05,EPW06]). This simple model already describes the reduction in sequence diversity. However genetic data are frequently available for many partially linked loci. This raises the question of whether selective sweeps also generate distinct patterns of multi-locus allele frequencies. We will follow [SSL06] and study a three locus model with one selective and two partially linked neutral loci. Using this model, it is possible to study the non-random association of allelic types at the two neutral loci, which is usually called linkage disequilibrium.
An influential idea in the analysis of selective sweeps was to study approximate genealogies describing relationships between the individuals in a sample from the population. Studying genealogies at the selected site started with [KDH88] and was carried further to linked neutral loci in [KHL89].
The genealogy at a single neutral locus can be constructed as a structured coalescent. Here, the beneficial and wild-type allele at the selected locus form two subpopulations. Their sizes are determined by the frequency path of the beneficial allele during the selective sweep. Assume a new gamete is built (forward in time) by recombination of a beneficial allele at the selected locus and a neutral variant linked to a wild-type. Following the neutral variant backward in time leads to a migration event from the beneficial to the wild-type background. Therefore, recombination acts as migration between the beneficial and the wild-type backgrounds.
Genealogies of two or more loci can be constructed using the ancestral recombination graph ( [Hud83,GM97]). Therefore, we will construct ancestries of two partially linked neutral loci under a selective sweep by a structured ancestral recombination graph. As in the case of only one locus, the two subpopulations are distinguished by the beneficial and wild-type allele at the selected locus, respectively. This ancestral recombination graph will serve as the exact model for genealogies at partially linked loci under a selective sweep. However, an exact analysis is hard to obtain, because the graph must be conditioned on the random frequency path of the beneficial allele.
An alternative approach uses a two-step procedure for genealogies at the selective and the neutral locus. First, the (approximate) genealogy at the selective locus is generated and second, the genealogy at the neutral locus is added, which might differ due to recombination. Two approximate genealogies at the selected site have been proposed. First, a star-like genealogy, which means that the most recent common ancestor of all pairs in the population is the individual which carried the beneficial allele first ([SD05, NWK + 05]). Second, a Yule process, i.e., a pure birth process, which allows for coalescences also during the selective sweep ( [SD05,EPW06]). It was shown in [SD05, Theorems 1.1, 1.2] that the Yule process approximation is more exact than the star-like approximation. Therefore, we will use this Yule process approximation for the genealogy at the selected site to study the three locus model of [SSL06] for selective sweeps. We will show that the analysis carried out in [EPW06] in the two locus case can be extended to the three locus case (Theorem 1). Moreover, the approximation by a Yule process can be used to calculate characteristics of linkage disequilibrium explicitly (Theorem 2).    Figure 1: The two possible geometries of the selected (S) and the two neutral loci (L and R). The scaled recombination rates between loci are given by ρ SL , ρLR, ρ LS and ρ SR .

The model
Consider a beneficial allele which enters a population of (haploid) size N at time t = 0 and has a selective advantage of s with respect to the wild-type allele. Set α = sN , which is called the scaled selection coefficient. As selection can only be detected if the beneficial allele fixes in the population, we condition on fixation of the beneficial allele and let T be the (random) time of fixation.
Assume reproduction in the population follows a Wright-Fisher model, or, more generally, a Cannings model with individual offspring variance 1. In the limit of infinite N and a time rescaling in units of N generations, the frequency path of the beneficial allele is the solution with a standard Brownian motion W and X 0 = 0. This diffusion arises as h-transform of the process describing the unconditional frequency path with the fixation probability of the beneficial allele as a harmonic function and has 0 as an entrance boundary. (See e.g. [Gri03], p. 245 and [EPW06], (2.1).) Two neutral loci are partially linked to the selected locus. For simplicity, we refer to the two neutral loci as the left and r ight neutral locus, denoted by L and R. As illustrated in Figure 1, the selected locus lies either (i) outside or (ii) in between the neutral loci. All other possible geometries are equivalent to either (i) or (ii) because of the symmetry in the model.
Recombination can break up the association of these three loci. (We only consider recombination as simple crossing over. Gene conversion is not considered in our model.) As we take a limiting infinite population and rescale time by a factor of N , we have to consider scaled recombination rates. These are different for the two geometries. For geometry (i) we denote the recombination rates between the selective and neutral loci by ρ SL , ρ LR and for geometry (ii) by ρ LS , ρ SR respectively.
The two linked neutral loci do not affect the frequency path of the beneficial allele. In contrast, neutral variants which are linked to the beneficial allele at the beginning of the selective sweep rise in frequency. Looking backward in time from the time T of fixation, we can trace back the history of a finite sample at all three loci. As the neutral loci are linked to the selected one, the genealogies at all three loci are correlated.
For the construction of the ancestral recombination graph relating all loci, time is running backward, so we set β = T − t. Conditioned on a frequency path X = (X t ) 0≤t≤T , given by (2.1), we will describe the ancestral recombination graph as a partition-valued process ξ X = (ξ X β ) 0≤β≤T . Assume we take a sample from the population at time T . Every individual in the sample carries one L and one R-locus. Of all Land R-loci present in the sample we want to trace back a number ℓ of Land r of R-loci. These loci are represented by sets ℓ for the Land r for the R-loci. So, ℓ := |ℓ|, r := |r|. To define the state space of the structured ancestral recombination graph denote by P A the set of partitions of A for a finite set A and define The coordinates ξ B and ξ b contain partition elements located in the beneficial and the wildtype background, respectively. For ξ ∈ P ′ ℓ∪r we write ξ (j) for the partition element containing j ∈ ℓ ∪ r.
The ancestral process is started at the time β = 0 of fixation of the beneficial allele. So, the sample of Land R-loci is linked to the beneficial allele. Therefore, we start the process in ξ X 0 = (π, ∅) for some π ∈ P ℓ ∪ r . Assume the state at time β is ξ X β = (ξ B , ξ b ) ∈ P ′ ℓ ∪ r . For j ∈ ℓ ∪ r the partition element which contains j ∈ ℓ, i.e., (ξ X β ) (j) , encodes the set of Land R-loci, taken from the population at time T , which have the same ancestor as j at time T − β. Usually we will study the genealogy of n pairs of Land R-loci. In this case set ℓ := {1, . . . , n} and r := {n + 1, . . . , 2n} and start the process with π = {{1, n + 1}, . . . , {n, 2n}}.
The dynamics of the process is given as follows: Coalescence events occur for lines in the beneficial and the wild-type background with pair coalescence rate 1/X T −β and 1/(1 − X T −β ) at time β, respectively. So, given ξ (2.2) respectively. For transitions in the process ξ X due to recombination we focus on geometry (i) first. A recombination event hits one line between the S and the L locus with rate ρ SL and between the L and the R locus with rate ρ LR . If a recombination event occurs between the S and the L locus, it may be that both recombining chromosomes carry the same allele at the S locus. This gives a recombination event which cannot be seen effectively and we ignore it in the process ξ X . All other recombination events must be modeled.
Here, (3 i ) encodes a recombination event which takes a pair of linked Land R-loci from the beneficial to the wild-type background; an event (4 i ) separates the R-locus of a line and takes it to the wild-type background; by (5 i ) the L and R loci of a line in the beneficial background are split but remain both in the same background; (6 i ) describes the same transition for a line in the wild-type background. The transitions (7 i ) and (8 i ) describe the back-recombination of loci into the beneficial background.
Example 2.1. An example displaying the dynamics of the process ξ X for geometry (i) is shown in Figure 2. The sets of Land R-loci are ℓ = {1, 2, 3} and r = {4, 5, 6}, respectively. The starting partition is ξ X 0 = (π, ∅) with π = {{1, 4}, {2, 5}, {3, 6}}. Several kinds of events can happen; coalescences in the beneficial background, i.e., an event (1), recombinations which leave the two neutral loci together but change the allele at the selected site, i.e., an event (3 i ) and recombination events which split the two neutral loci. The last kind of event may either bring one of the two neutral loci in a different background, (4 i ), or split a line within the beneficial background, (5 i ), or split a line in the wild-type background, (6 i ). The final partition is ξ X . For geometry (ii) we have (rescaled) recombination rates ρ LS and ρ SR between the left neutral and the selective and the right and the selective locus, respectively. Here, transitions occur from (ξ B , ξ b ) to These events refer to a change in background from the beneficial to the wild-type background either for the L-locus, (3 ii ), or the R-locus, (4 ii ). Splits in the beneficial and wild-type background may happen as in the case of geometry (i); see events (5 ii ) and (6 ii ). Backrecombinations to the beneficial background are denoted by (7 ii ) for the Land (8 ii ) for the R-locus. Observe that a transition which takes both loci on one line from the beneficial to the wild-type background cannot occur for geometry (ii); cf. event (3 i ).
Definition 2.2. Assume ℓ and r are sets of left and right neutral loci, respectively, and X = (X t ) 0≤t≤T is a frequency path of the beneficial allele given by (2.1).
The mixture of ξ X T over the distribution of frequency paths given by (2.1) defines the random partition Γ π = (Γ B π , Γ b π ), i.e.,

Main result
We study selective sweeps in the infinite population limit, i.e., the frequency of the beneficial allele follows the SDE given by (2.1). Moreover, selection is most efficient for large selection coefficients. Our goal is to derive a simpler but approximate expression for Γ π in the regime of large α. It was shown in [EPW06] that for the fixation time T of the beneficial allele for large α. This suggests that only under the scaling ρ = O(α/ log α) for the recombination rate a non-trivial number of recombination events occurs during the sweep for large α. This is true for all possible kinds of recombination events during the sweep, so the recombination rates ρ SL , ρ LR and ρ LS , ρ SR for geometries (i) and (ii) should be of this order. Henceforth, we assume Our approximation of Γ π is based on a Yule tree, which serves as an approximation of the genealogy at the selected locus. A Yule tree is the realization of a Yule process, i.e., a pure birth process which starts with one line and every line splits in two lines after an exponential waiting time.
In our approximation the quantity will play an important role. Assume ℓ and r are sets of left and right loci and π ∈ P ℓ∪r . Three mechanisms determine the Yule approximation of the partition Γ π . First, we approximate splits in the beneficial background, i.e., events (5 i ) and (5 ii ), by the following procedure: For all partition elements π 1 , . . . , π |π| realize Bernoulli random variables U 1 , . . . , U |π| which are 1 with success probability If U i = 1, split the ith partition element in its left and right locus. Altogether, this defines a partition Next, realize a Yule process with branching rate α, i.e., each line splits in two lines at rate α. Stop this process when it has ⌊2α⌋ lines. Call this tree Y. To obtain the genealogy of a sample of size |π ′ | from this tree with ⌊2α⌋ extant leaves, we use the following construction: Start with |π ′ | lines from the full Yule tree Y with ⌊2α⌋ lines. When there are k lines left at the time the full tree has i lines, the probability that a coalescence event occurs among the k lines at the time the full tree goes from i to i − 1 lines is By this construction we build a tree Y |π ′ | with the partition elements of π ′ as leaves and nodes which record the number of lines in the full Yule tree. (3.4) Remark 3.1. To construct the sample tree Y |π ′ | from Y is a task equivalent to describing an exchangeable sample from a tree which arises by exchangeable binary coalescence dynamics. This has been studied by [STW84] and was recalled in [EPW06, Lemma 4.8]. If I t = i is the number of lines in the Yule tree Y at time t, denote by K i the number of lines in Y |π ′ | while I t = i. The process (K i ) ⌊2α⌋≥i≥1 is a time-inhomogeneous Markov chain with transition probabilities Moreover, the sample tree can be described forward in time by noting that Table 1: For geometry (i), we mark every branch in the Yule tree by at most one from three different kinds of events. If a branch starts when the full Yule tree has i 1 and ends when it has i 2 lines, the probabilities for all marks are given in the table.
The sample tree which is pruned out of the full tree in this way represents the genealogy at the selected site. To describe the genealogies at the partially linked neutral sites we mark the sample Yule tree to determine further recombination events. A mark stands for one (or two) recombination events that may occur. This works in the following way: Let a branch in the tree Y |π ′ | be given which starts when the full tree has i 1 lines and ends when the full genealogy has i 2 lines. For geometry (i), every branch can be hit by at most one of three different kinds of marks indicating recombination events. These are SL-, LR-, and SLR-marks. Their probabilities are given in Table 1. For geometry (ii) the branch is hit independently by LSand SR-marks with probabilities (1 − p i 2 i 1 (γ LS )) and (1 − p i 2 i 1 (γ SR )). Here, SL-marks separate the Sfrom the L-locus on each branch of the tree, etc. For geometry (i), SLR-marks separate the Sfrom the Land the Lfrom the R-locus. (3.5) Example 3.2. The above construction is illustrated in Figure 3. We consider geometry (i) here. A set ℓ = {1, 2, 3, 4} of L-loci and r = {5, 6, 7, 8} of R-loci is given. Starting with π = {{1, 5}, {2, 6}, {3, 7}, {4, 8}}, every partition element is split with probability p ⌊2α⌋ 0 according to (3.3). This results in the finer partition π ′ . The partition elements of π ′ are used to construct a sample tree from a full Yule tree which has ⌊2α⌋ lines. The coalescence probabilities for the sample are given by (3.4). On the sample tree, branches are marked by SL-, LR-, or SLR-marks according to Table 1. The resulting partition π ′′ is constructed as given in Definition 3.3.
We are now in a position to define our approximation based on the Yule process.
Definition 3.3. Assume ℓ and r are sets of left and right neutral loci, respectively, and π ∈ P ℓ∪r . By (3.3) construct the partition π ′ and by (3.4) and (3.5) a Yule tree Y |π ′ | with

marks. For geometry (i) define the equivalence relation:
where the bold lines indicate for which part of the tree Y |π ′ | relating two lines with the root of the tree, the constraint on marks applies. For geometry (ii) set (3.9) Then the random partition is called the Yule approximation of Γ π .
Example 3.4. For the example in Figure 3 the SL-, LRand SLR-marks on the sample tree lead to the realization Theorem 1. Let π ∈ P ℓ∪r and Γ π and Υ π be as in Definitions 2.2 and 3.3. Then, Remark 3.5.
1. The Theorem states that, for large α, the random partitions Γ π and Υ π are close in variation distance. Here, variation distance refers to the maximal difference in the probabilities to obtain any partition ξ ∈ P ′ ℓ∪r . The order of accuracy, given by the Landau symbol, still depends on several parameters. These are the cardinalities ℓ and r and recombination constants γ SL , γ LR for geometry (i) and γ LS and γ SR for geometry (ii). The proof of Theorem 1 will be given in Section 5.
2. At first sight, comparing the Definitions 3.3 and 2.2 the Yule approximation does not look any simpler than the exact model. However, the Yule approximation has advantages both analytically and computationally. The random partition Γ π relies on constructing a frequency path X , while the Yule approximation Γ π constructs the ancestral recombination graph for the sample directly. Analytically, as we will see in Section 4, this means that explicit calculations are possible. Computationally, i.e., for simulations of the ancestral recombination graph, the direct construction of the ancestry of the sample allows for fast algorithms; see [PHW06] for the case of a single neutral locus.
3. The current paper is a generalisation of results found in [EPW06] for a two-locus system with only one neutral locus. More precisely, consider the projection of Γ π on only one locus, i.e., on either ℓ or r. In Propositions 4.2 and 4.7 of that paper it was shown that the projection of Υ π on ℓ or r is an approximation to a structured coalescent with an error in probability of the order O (log α) −2 .
4. In [EPW06] an approximate sampling formula was given in the two-locus case. A similar approach would be possible here. However, we refrain from its derivation because it was shown in [PHW06] that the sampling formula in the two-locus case only produces numerically sound results for n ≤ 5. [PHW06], the Yule approximation can be improved. To understand how this works, we need to collect the errors which contribute to the error of order O(1/(log α) 2 ). First, the Yule approximation ignores events (2), (6 ii ), (7) and (8). Second, as will be clear in the proof of Proposition 5.5, the coalescent rate in the beneficial background is decreased from 1/Xdt to (1 − X)/Xdt by the Yule process. It is the latter error that dominates, at least in large samples, because the total coalescence rate increases quadratically with the number of lines. However, increasing the coalescence probability in (3.4) to

As indicated numerically in
at the time the Yule tree has i lines corrects for this error.
6. For simulations of genealogies it is most important that the Yule approximation given above is not restricted to the case of two neutral loci. The take-home-message from the construction of the Yule approximation is that splits in the beneficial background are generated first and afterwards marks on a Yule tree determine all recombination events. Both, splits in the beneficial background and recombination events along the Yule tree can be given along a continuous chromosome.

Application: D
Lewontin's D is a measure of linkage disequilibrium (non-random association of alleles) and is frequently used as a simple statistic in a multi-locus setting ( [Lew64]; see also [Ewe04, (2.89)]). Given two loci L and R with alleles 0 or 1 at each locus, it is defined as where p LR is the frequency of individuals carrying allele 1 at both loci, p L is the frequency of 1's at the L locus and p R is the frequency of 1's at the R locus.. To predict patterns of D between pairs of neutral loci at the time T of fixation of a beneficial allele we next approximate E[D(T )] using Theorem 1. It is crucial to observe that E[p LR (T )] as well as E[p L (T )p R (T )] may be derived by the distribution of genealogies of linked neutral loci under selection and the expected allele frequencies at the beginning of the sweep. To see this, note that E[p LR (T )] equals the probability that the ancestors of the Land R-locus of one randomly picked individual from the population at time T carry alleles 1 at both neutral loci. Analogously, E[p L (T )p R (T )] is the probability that the ancestors of the Land Rloci of two different individuals at time T both carry allele 1. Denote by q the probability that both loci, L and R from one individual, picked at time T , have a common ancestor at the beginning of the sweep. Analogously, q ′ is the same probability for the Land R-loci from two different individuals. Using these definitions we see that (4.2) Combining (4.2) with the definition of D from (4.1), Both, q and q ′ may be approximated by Theorem 1. Formally, setting ℓ = {1}, r = {2}, As Γ π may be approximated by Υ π this brings us in a position to predict patterns of D at the end of a selective sweep. Theorem 2. For geometry (i),

5)
and for geometry (ii), (4.6) Remark 4.1. 1. Patterns of Lewontin's D can be studied by deterministic forward calculations instead of our genealogical approach. This was carried out in [SSL06] under the assumption that strong selection leads to a deterministic behaviour of allele frequencies. Specifically, the frequency of the beneficial allele follows the logistic differential equation In real populations, random effects due to genetic drift are not negligible. This has been pointed out by [LSP06]. The Yule process approximation captures most random effects. Indeed, comparison with simulations from [LSP06] shows that the results produced by the Yule process approximation are more accurate than those of [SSL06].
2. For empirical studies it is most interesting to know which patterns of linkage disequilibrium to look for in real data. The pattern genetic hitchhiking can produce was discussed in [SSL06] and [RT06]. Surprisingly, hitchhiking reduces levels of linkage disequilibrium compared to the neutral expectation. This is evident from Figure 4. If the selected locus is far from both neutral loci, linkage disequilibrium between the neutral loci is not affected by hitchhiking. Therefore, values of D for large ρ SL converge to the expectation of D under neutrality. This effect was taken up by [RT06] to argue that genetic hitchhiking produces patterns in the association of alleles similar to recombination hotspots, which are e.g. important in genetic association studies in humans ( [Con05]). However, genetic hitchhiking certainly produces patterns different from recombination hotspots in general, e.g., a low neutral diversity or a distinctive site frequency spectrum ([FW00]).
3. An accurate approximation of E[D(T )] does not suffice to predict patterns of linkage disequilibrium in general. In addition to genetic drift, random effects which affect D(T ) were found in [SSL06] to be the allelic type of the founder of the sweep and its frequency. The resulting variance in D can be considerably higher than under neutrality.
Now we come to the proof of Theorem 2.
Proof. The key in the proof is to compute the probabilities q and q ′ . This is achieved by the Yule process approximation Υ π of Theorem 1. We start with geometry (ii). Here, we can see from the Yule approximation (3.7) that q = q ′ up to a term of order 1/(log α) 2 since one L and one R locus are identical by descent iff there is no LS mark on

• •
. It does not depend on the linkage of the L and the R locus at the end of the sweep. Consequently, (4.6) follows. For geometry (i), we start with the approximation of q ′ . For one L and one R locus from two different individuals there is a random number K of lines in the full tree of the Yule approximation at the time the selected loci which are linked to the neutral ones coalesce. To obtain the distribution of K, we compute Hence we compute

Proof of Theorem 1
The proof deals with geometries (i) and (ii) simultaneously. We will write events at rates (3)-(8) whenever we refer to the rates (3 i )-(8 i ) for geometry (i) and (3 ii )-(8 ii ) for geometry (ii), respectively. We will be dealing with several random partitions all of which agree up to an error of order O (log(α)) −2 . Exactly, we will prove where Γ π , ∆ π , Ξ π and Υ π are given in Definitions 2.2, 5.1, 5.3 and 3.3, respectively and '≈' means that the random partitions differ by O (log α) −2 in variation distance. While Γ π is the random partition which is defined by the structured ancestral recombination graph, the other random partitions are approximations. First, ∆ π arises by (i) ignoring events which occur according to rates (2), (6 ii ), (7) and (8) and (ii) realizing all events according to rate (5) first and only afterwards, construct the process using rates (1), (3), (4) and (6 i ). Second, Ξ π already deals with the Yule process. It is derived by marking an infinite Yule tree by two constant rate Poisson processes with rates ρ SL , ρ LR for geometry (i) and ρ LS , ρ SR for geometry (ii). Finally, the Yule approximation Υ π of Γ π arises by considering only the number of lines in an infinite Yule tree at times of coalescence in a sample.
In the whole proof we rely on a probability measure P on a probability space on which the solution of (2.1) as well as arbitrarily many independent Poisson processes and other random variables are realized.
Definition 5.1. Define a P ′ ℓ ∪ r -valued random variable ∆ π as follows: starting in π ∈ P ℓ∪r split all partition elements ξ ∈ π independently into ξ ∩ ℓ, ξ ∩ r with probability where ρ = ρ LR for geometry (i) and ρ = ρ LS +ρ SR for geometry (ii). The resulting partition π ′ is used for the starting point (π ′ , ∅) of a process η X = (η X β ) 0≤β≤T , conditioned on a frequency path X = (X t ) 0≤t≤T with transitions according to events (1),(3 i ), (4 i ), (6 i ), given by (2.3), for geometry (i) and to events (1), (3 ii ) and (4 ii ), given by (2.4), for geometry (ii), respectively. Given η X , define Proposition 5.2. Let π ∈ P ℓ∪r and Γ π and ∆ π be as in Definitions 2.2 and 5.1. Then, Proof. We proceed in several steps. Our arguments in Step 1 show that we may discard events which occur at rates (2), (6 ii ), (7) and (8). In Step 2 we use a fixed number of Poisson processes to generate the random partition we want to approximate. Our goal is to separate events (5) from the rest by verifying a certain order of the possible events and establishing an approximate independence of the events (5). Particularly, we show in Step 3 that splits in the beneficial background (i.e., events (5)) take place before all other events with high probability. The approximate independence will be proved in Steps 5 and 6 by an application of a general result on mixed Poisson processes we establish in Step 4.
Step 2 (Construction of ζ X by Poisson processes) Recall that ℓ := |ℓ| and r := |r| are the number of L and R loci under consideration. Take Poisson processes which are all conditionally independent given the random frequency path X of the beneficial allele. For coalescence, take a Poisson process T 1 with rate ℓ + r 2 at time β for geometry (ii). We have combined recombinations to the wild-type and splits in the wild-type background in case of geometry (i) since they happen with the same rates. Additionally, let W = (W i,m ) i=1,3,4,5,m=1,2,... be a random array such that all W i,m 's are independent, W 1,m is uniformly distributed on all pairs of ℓ ∪ r, W 3,m is uniformly distributed on ℓ, and W 4,m and W 5,m are uniformly distributed on r, m = 1, 2, . . ..
The set ℓ ∪ r can be totally ordered, so we may assume that every partition element in ζ ∈ P ′ ℓ∪r has a smallest element. Recall that we write ζ (j) for the partition element containing j ∈ ℓ ∪ r.
We abbreviate by T 3 -T 5 the Poisson processes T 3 i -T 5 i for geometry (i) and the Poisson processes T 3 ii -T 5 ii for geometry (ii). We next show that the distribution of ζ X T is the image measure of the tupel (T 1 , T 3 , T 4 , T 5 , W ) under a map ϕ. Specifically, the distribution of ζ X T is uniquely determined by the distribution of (T 1 , T 3 , T 4 , T 5 , W ).
To define ϕ, consider a discrete set T 1 ⊆ [0, T ] and finite sets T 3 , T 4 , T 5 ⊆ [0, T ] such that T i 1 ∩ T i 2 = ∅ for i 1 = i 2 and set T = i T i . Furthermore w = (w i,m ) i=1,3,4,5,m=1,2,... such that for all m = 1, 2, . . ., w 1,m is a pair in ℓ ∪ r, w 3,m ∈ ℓ and w 4,m , w 5,m ∈ r. Given (T 1 , T 3 , T 4 , T 5 , w) we generate a partition by considering the events in T in decreasing order. Assume ζ X 0 = (π, ∅) and after the (m − 1)st event at time β we obtain a partition ζ X β = (ζ B , ζ b ) ∈ P ′ ℓ∪r and the mth event in T to be realized happens at time β ′ ∈ T. Consider first the case β ′ is the mth event is the m 1 st event in β ′ ∈ T 1 . The pair w 1,m1 = (j, k) gives a random pair of loci. If ζ (j) , ζ (k) ∈ ζ B and if both, j and k, are the smallest elements of their partition elements, coalesce these partition elements, i.e., make the transition Otherwise do nothing. The next case to consider is that β ′ is the m 3 rd event in T 3 and w 3,m3 = j for some j ∈ ℓ. If ζ (j) ∈ ζ B and if j is the smallest element of ζ (j) ∩ ℓ, change the partition element from ζ B to ζ b , i.e., make the transition (5.5) Otherwise do nothing. The case t ∈ T 5 is similar and is omitted. If β ′ is the m 4 th event in T 4 and w 4,m4 = j for j ∈ r the partition ζ again only changes if j = min ζ (j) ∩ r. We distinguish two cases, ζ (j) ∈ ζ B and ζ (j) ∈ ζ b . In the former case, split the Land R-loci in the partition element in two partition elements and bring all R-loci into the wild-type background, i.e., make the transition This corresponds to an event (4). In the latter case split all Land R-loci of ζ (j) and leave them in the wild-type background, i.e., make the transition which corresponds to an event (6 i ). Recall that for geometry (ii) one Land one R-locus cannot recombine to the wild-type background together. Hence partition elements in ζ b are either subsets of ℓ or of r such that the last transition must not occur for this geometry. By generating all events according to this procedure we end with a partition ζ X T . Therefore we have defined the map ϕ : T is the image measure of (T 1 , T 3 , T 4 , T 5 , W ) under the map ϕ. (5.8) To see this, observe first, that there are only finitely many recombination events (3), (4), (5) and (6 i ). Almost surely, all events in the Poisson processes occur at different times, so ϕ is defined on a set of probability 1. By the above construction, we obtain that two partition elements in ζ B coalesce by event (1). The Poisson processes T 1 , T 3 , T 4 , T 5 produce exactly the recombination events (3), (4), (5) and (6 i ). Hence (5.8) is proved. Given w, the random partition ϕ(T 1 , T 3 , T 4 , T 5 , w) only depends on the order of time points in T 1 , T 3 , T 4 , T 5 . There is another feature we will need: Let β ′ , β ′′ be consecutive time points in T with β ′ ∈ T 3 , β ′′ ∈ T 4 . Exchanging β ′ and β ′′ does not alter the random partition Assume β ′ is the m 3 rd event in T 3 , w 3,m3 = j and β ′′ is the m 4 th event in T 4 and w 4,m4 = m.
If j and k are not in the same partition element for β < β ′ , the claim is trivial as recombination events only make the partition finer. Similarly, if j > min ζ (j) ∩ ℓ or k > min ζ (k) ∩ r only one transition occurs and the claim follows. In the case ζ (j) = ζ (k) , j = min ζ (j) ∩ ℓ, k = min ζ (j) ∩ r two transitions occur if and only if ζ (j) = ζ (k) ∈ ζ B . We illustrate this situation in Figure 5.
Observe that the two-step transitions for the pair (5.5), (5.7) (see Figure 5(a)) as well as for the pair (5.6), (5.5) (see Figure 5(b)) are given by i.e, the partition element both moves from ζ B to ζ b and is split in its Land R-loci. This proves (5.9).
In the next three steps we will show that realizing the different splits independently from a fixed sample path X = (X t ) 0≤t≤T will cause only a small error. To see this we will establish a general result on mixed Poisson processes in Step 4 and apply it to the Poisson processes introduced in Step 2. The proof of Proposition 5.2 will then be concluded by an application of these two steps.
Step as δ → 0. Denote the distribution function of the Poisson distribution with parameter λ by Poi λ (·). We claim that for k, l ∈ N 0 Note that by a Taylor series approximation, for a random variable Ψ in R + with second moments and someΨ satisfying Ψ where the terms in {. . .} only show up if the denominators are non-zero and the last step follows from the fact that the Poisson weights in {. . .} lie in [0, 1]. As this holds for every Ψ(δ), (5.15) follows immediately from (5.14). Moreover, by a calculation similar to (5.17), Additionally, (5.16) follows easily from the fact that by the Cauchy-Schwarz inequality.
because T 3 , T 4 , T 5 are randomly time-changed Poisson processes. By (5.15) and (5.16), (5.18) and (5.19) follow once we have shown First observe that (X t ) 0≤t≤T has the same distribution as (1−X T −t ) 0≤t≤T by time-reversibility (see e.g. [KT81,Gri03]). Hence the inequalities on the left hand side of (5.21) and (5.22) follow. Second, we verify the expressions on the right hand side of (5.21) and (5.22) by an application of the Green function G(., .) of the diffusion (X t ) 0≤t≤T . This function satisfies if x ≥ y, see e.g. [KT81,EPW06]. More generally, G(., .) satisfies for all k = 1, 2, . . . which can be proved by induction. We may thus write, because G(x, y) = G(0, y) for y ≥ x, Step 6 (Approximate independence) As we have seen in (5.8) the distribution of ζ X T is determined by the distribution of the order of events in the Poisson processes T 1 , T 3 , T 4 and T 5 . The calculations in Step 3 allow us to make the assumptions on the ordering of events in these Poisson processes as these events have probability 1 − O (log α) −2 . Furthermore, we know from (5.9) that events in T 3 and T 4 may be exchanged without changing the distribution of ζ X T . Hence, the distribution of ζ X T is determined once the joint distribution of is known. To approximate the joint distribution of these objects, define where we have used the fact that T ε is a stopping time and the strong Markov property of the process X . Note that by (5.11) we may assume K 5 = T 5 ∩ [T ε , T ] which gives an error of O (log α) 2 α in probability. From Steps 4 and 5 we get and using the strong Markov property of X a second time we get and we are done.
By Proposition 5.2, events (5) can be generated independently of the frequency path and of all other events. The rates of the recombination events (3), (4), (6 i ) at time β are all proportional to (1 − X T −β ). This is reminiscent of the case of only one neutral locus, studied in [EPW06], where a line carrying one neutral locus in recombination distance ρ recombines to the wild-type background with rate ρ(1 − X T −β ). As a consequence we can use the same techniques used there, especially their Proposition 3.6. which states that a marked Yule tree approximately gives the same partition as the structured coalescent.
Let Y be an infinite Yule tree with branching rate α. Moreover, consider the random tree Y |π ′ | which arises by sampling |π ′ | lines from Y at infinity. Identify each of the |π ′ | partition elements of π ′ with one sampled line. Between the root of the Yule tree Y starts and the time it has ⌊2α⌋ lines, mark all lines by the following procedure: For geometry (i), the tree is marked by Poisson processes with rates ρ SL and ρ LR . These marks are relabelled such that each branch is hit by at most one mark. Call the corresponding marks SL-, LRand SLR-marks. The following rules are applied:  For geometry (ii), mark the tree by two independent Poisson processes with rates ρ LS and ρ SR . If a branch is hit by one or more events of the Poisson process with rate ρ LS , it gets an LS-mark. If it is hit by one or more events with rate ρ SR , it additionally gets an SR-mark.
The result of this procedure is a marked Yule tree Y |π ′ | . Given π ′ and the marked Yule tree Y |π ′ | we use the same equivalence relation as given in (3.6) and (3.7) to define π ′′ ∈ P ′ ℓ∪r . Furthermore, we use (3.8) and (3.9) to define the random partition Example 5.4. The two cases in which an SLR-mark occurs for geometry (i) are illustrated in Figure 6. Consider the line in the sample Yule tree which can be identified with the partition element {j, k} where j ∈ ℓ and k ∈ r. Consider case (a) first, shown on the left side of Figure  6: The SL-mark hitting a branch in Y |π ′ | leads to a jump of the partition element into the wild-type background. We now have to consider the additional Poisson process at rate ρ LR to determine whether or not the line will split within the wild-type background. If an event with rate ρ LR occurs, the Lis separated from the R-locus on this line. Case (b) is illustrated on the right side of Figure 6. Here, the line which refers to the partition element {j, k} is first (backward in time) hit by an LR-mark, bringing the R-locus into the wild-type background, and after that an additional SL-mark hits the same branch, which additionally brings the L-locus into the wild-type background. In both cases the loci j and k end up separated in the wild-type background. This is summarized in Definition 5.3 by an SLR-mark.
As a next step in the Proof of Theorem 1 we now show that ∆ π ≈ Ξ π .
Proposition 5.5. Let π ∈ P ′ ℓ∪r and ∆ π and Ξ π be as in Definitions 5.1 and 5.3. Then, Proof. As the mechanism to generate splits in the beneficial background is the same for both random partitions, ∆ π and Ξ π , we concentrate on all other events.
The proof follows along the lines of the Yule approximation in the case of only one neutral locus, given in [EPW06, Definition 3.3. and Section 4.3.]. The crucial observation is that by a random time change t → τ given by dτ = (1 − X t )dt the frequency path X , given by (2.1), is taken to the solution Z = (Z t ) t≥0 of with a standard Brownian motion W and Z 0 = 0. This is an α-supercritical Feller branching process conditioned on non-extinction. It was shown in [EO94] and [O'C93] that the genealogy of the α-supercritical branching process is a Yule process with branching rate α. Observe that the time-transformation t → τ only works until the supercritical branching process has reached frequency 1. From 4.5(b) in [EPW06] we see that at this time the number of lines in the Yule process is Poisson distributed with mean 2α. (The additional factor of 2 arises because we made the assumption that the individual offspring variance in the underlying Cannings model is 1 rather than 2. See also [PHW06].) However, as typical deviations in this Poisson distribution are of the order √ α ≪ α we may instead assume that the Yule process has ⌊2α⌋ lines. This was made precise in the proof of Proposition 4.7. in [EPW06]. Moreover, for geometries (i) and (ii) the rates in the process ξ change at time β from ρ SL (1 − X T −β ), ρ LR (1 − X T −β ) to ρ SL , ρ LR and from ρ LS (1 − X T −β ), ρ SR (1 − X T −β ) to ρ LS , ρ SR , respectively. Especially, the time-changed rates are constant. Under the random time change the coalescence rate (1) changes at time β from 1/X T −β to 1/(X T −β (1 − X T −β )). However, it was shown in [EPW06, Proposition 4.2.] that the change of these rates can only produce an error in probability of order O (log α) −2 . This fact was used in [EPW06, Lemma 4.5., Proposition 4.7.] to prove that the marked Yule process gives an accurate approximation in the case for one neutral locus. However, this result carries over to the present situation because all Poisson processes along the Yule process have constant rates.
It remains to check whether the equivalence relation Ξ π coincides with ∆ π given the change in the coalescence rate has no effect. First of all, realize the splits in the beneficial background according to Definition 5.1. Then, take j, k ∈ ℓ ∪ r and trace their partition elements backwards up to time t = 0, β = T . We only consider geometry (i) and j ∈ ℓ, k ∈ r, since the other cases j, k ∈ ℓ and j, k ∈ r and all cases for geometry (ii) are similar. If we consider the process η X from Definition 5.1 without any recombination events we would obtain a tree for the genealogy relating j and k. However, recombination events may cause the L-locus j and the R-locus k to end up in different partition element in the random partitions ∆ π . This will be the case if and only if one of the following events occurs in the process η X : , which takes either j or k to the wild-type background before coalescence, (b) a recombination event (4 i ) with rate ρ LR (1 − X)  , which takes k to the wildtype background before coalescence with j, (c) an event (4 i ) with rate ρ LR (1 − X) before (backward in time) an event with rate ρ SL (1 − X) happens on that branch; in this case j and k have coalesced, but a recombination event brings k to the wild-type background without j, before (backward in time) an event with rate ρ LR (1 − X) happens on that branch, which brings both j and k to the wild-type background. Here, an event (6 i ) at rate ρ LR (1 − X) happens which splits j and k in the wild-type background.
The trees in events (a)-(d) refer to trees generated by η X . By the random time change and our assumption that the change in coalescence rate does not alter random partitions we can as well take trees generated by the Yule process and change the rates ρ SL (1− X) and ρ LR (1− X) to ρ SL and ρ LR . Hence we are dealing with a Yule tree with branching rates α marked by Poisson processes with rates ρ SL and ρ LR which is the exact situation of Definition 5.3. Using the definition of the SL-, LRand SLR-marks, we note that

• •
. If none of these marks occur, j and k are in the same partition element of Ξ π by (3.6). Hence ∆ π and Ξ π coincide with high probability.
We conclude the proof of Theorem 1 by showing that Ξ π from Definition 5.3 and Υ π from Definition 3.3 are close in variation distance.
Proposition 5.6. Let π ∈ P ′ ℓ∪r and Ξ π and Υ π be as in Definitions 5.3 and 3.3. Then, Consider a branch which starts when the full Yule tree has i 1 lines and ends when it has i 2 lines. Using Definition 5.3 this line is hit by an SL-mark iff it is hit by the Poisson process at rate ρ SL and an independent Poisson process with rate ρ LR produces no mark between time 0 and the time the Yule tree has i 2 lines. Hence the probability for an SL-mark in Ξ π is approximately given by If a branch is hit by the Poisson process with rate ρ SL but did not obtain an SL-mark, it obtains an SLR-mark. Hence the probability for such a mark is given by The branch is hit by an LR-mark if it is hit by the Poisson process at rate ρ LR but not by the Poisson process with rate ρ SL . Hence the probability for an LR-mark is As a consequence, the marks in Y |π ′ | and Y |π ′ | coincide approximately (cf. Table 1) and we are done.