Exact calculation of the expected SFS in structured populations

The Site Frequency Spectrum (SFS), summary statistic of the distribution of derived allele frequencies in a sample of DNA sequences, provides information about genetic variation and can be used to make population inferences. The exact calculation of the expected SFS in panmictic population has been derived in the Markovian coalescent theory for decades, but its generalization to the structured coalescent is hampered by the almost exponential growth of the states space. We propose here a complete algorithmic procedure, from how to build a suitable state space and sort it, to how to take advantage of the sparsity of the rate matrix and to solve numerically the linear system by an iterative method. The simplest case of the symmetrical n-island is then processed to arrive at a ready-to-use demographic parameters inference framework.