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 a panmictic population under the infinite-site model of mutation has been known 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 show here how to obtain this expected SFS as the solution of a linear system. More precisely, we propose 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 using an iterative method. We then build a specialization for the simplest case of the symmetrical n-island model to arrive at a ready-to-use software called SISiFS from which a demographic parameters inference framework could easily be developed.