9 Greedy finestructure

We have created a simple bash script that uses the pre-existing finestructure commands to compute the MAP (maximum aposteriori) state estimation using greedy optimisation. This can be many times faster than performing full MCMC, and is suitable for very large datasets (it is probably your only option for 10000+ samples). ChromoPainter will have become a very significant cost by this point.

To use greedy optimization, you should:

1. Run ChromoPainter to obtain the combined coancestry matrix using fs <filename>.cp <options> -combines2.
2. Run finestructuregreedy.sh <filename>.chunkcounts.out outputfile.xml This uses the ”tree building” step of finestructure by repeatedly:
   • Attempting MCMC moves, accepting only if they increase the posterior probability.
   • Checking after a certain amount of iterations whether any progress has been made.

IMPORTANT NOTE: The -x option controls how many steps are taken between each step. The default of 50000 may be moderately slow, but it does try hard to find a better state. If this is too low, the algorithm will terminate prematurely.

There is a danger of getting stuck in a local optima, and of failing to find a possible move that would increase the Posterior. However, empirically the approach does perform well enough for exploratory data analysis. Convergence is assessed simply by counting the number of populations (as it unlikely that adding then removing populations is possible).