A sequential coalescent algorithm for chromosomal inversions

Abstract

Chromosomal inversions are common in natural populations and are believed to be involved in many important evolutionary phenomena, including speciation, the evolution of sex chromosomes and local adaptation. While recent advances in sequencing and genotyping methods are leading to rapidly increasing amounts of genome-wide sequence data that reveal interesting patterns of genetic variation within inverted regions, efficient simulation methods to study these patterns are largely missing. In this work, we extend the sequential Markovian coalescent, an approximation to the coalescent with recombination, to include the effects of polymorphic inversions on patterns of recombination. Results show that our algorithm is fast, memory-efficient and accurate, making it feasible to simulate large inversions in large populations for the first time. The SMC algorithm enables studies of patterns of genetic variation (for example, linkage disequilibria) and tests of hypotheses (using simulation-based approaches) that were previously intractable.

Figure 1

Sketch of the original SMC algorithm. In the first step, a recombination event is dropped on the tree (indicated by a crossmark). The next step shows how the upper part of the branch is removed and a floating lineage is created. In the last step, the new lineage (indicated by a bold line) is reattached to the tree.

Figure 2

Sketch of how gene flux between different chromosome arrangements is modeled. The lines indicate a standard (black) and an inverted (gray) chromosome in a heterokaryotype. The letters indicate different sites along the chromosomes. The dashed lines indicate the boundaries β₁ and β₂ of the interval I that is moved from one chromosome to the other. The arrows symbolize that genetic material can be copied from one chromosome and inserted into the other (as in gene conversions), or that genetic material can be exchanged between the two chromosomes (as in double crossing-overs).

Figure 3

Sketch of the SMC algorithm with inversions for a sample of size 2. We sample one standard and one inverted chromosome. The dotted line separates the two chromosome classes; lineages to the left of the line belong to the standard class, lineages to the right to the inverted class. Each panel shows three steps: locating the recombination event, creating the floating lineage, and reattaching the floating lineage. Panel a shows a homokaryotypic recombination event, indicated by a crossmark, and the left part of a gene flux event, indicated by an open circle. Panel b shows the right part of the same gene flux event, indicated by a filled circle. Note that another gene flux event is necessary for coalescence. Bold lines show the reattached lineages.

Figure 4

Comparison of the distribution of coalescence times. (a, b) Distribution of coalescence times for samples of size 2 at sites x=0.01, 0.1 and 0.25. (c, d) Statistics that summarize the distributions. The boxes show the median, and the lower and upper quartiles of the distribution of coalescence times at sites x=0.01, 0.1, 0.2, 0.25 and 0.9. The whiskers show the minimum and the maximum of the coalescence times. Population size is N=500 and c=10⁻² in panels (a, d). (e and f) Expected coalescence time for different population sizes. Circles and crossmarks correspond to results from simulation of the SMC for N=500 and N=50 000, respectively. Solid gray line shows the analytical prediction for expected coalescence time.

Figure 5

Correlation between coalescent times. Contour plot that illustrates the correlation of coalescence times for pairs of sites if chromosomes are sampled randomly from the population. Dark regions correspond to high levels of correlation and light regions correspond to low levels of correlation. Population sizes are N=500 (a) and N=50 000 (b).

Figure 6

Correlation of coalescence times between pairs of sites. The location of the first site is fixed at x=0.1 (a) or x=0.9 (b), and the location of the second site is given on the x-axis. Solid lines correspond to the SMC algorithm, crossmarks correspond to the ARG, and circles to the FTS.

Figure A1

Cartoon example of the SMC algorithm with inversions for a sample of one standard (Chr 1) and one inverted chromosome (Chr 2). The top part of each panel shows a gene tree, with the thin vertical line separating standard and inverted chromosomes. The bottom part of each panel shows the chromosomes, where the arrow indicates the point to which the tree pertains. Crossmarks and circles indicate the breakpoints of recombination and gene flux events, respectively. The ith gene flux event is labeled F_i and the ith homokaryotypic recombination event is labeled H_i. The boundaries of gene flux events are indicated by dotted vertical lines on the chromosomes, labeled by f_i (left boundary) and f_i′ (right boundary). The chromosomal position of the ith homokaryotypic recombination event is indicated by a solid vertical line and labeled by h_i. Dashed lines in the coalescent tree show the removed part of the tree, that is, the branch above a recombination or gene flux event. The segment of the chromosome for which trees have already been constructed is shaded gray.