Restricting the search space in this way allows us to reduce the number of burn-in iterations from 56 to 5, the number of sampling iterations from 200 to 95, and the number of MH steps taken at each iteration for each individual from 2N to 100, where N is the number of samples being phased. This reduces the complexity of our phasing algorithm from O(N2) to O(N). Although our implementation of the Hamming distance search has complexity O(N2), for N = 30,000, the impact of the search on run time is small (~5% of run time on each chunk). A chunk of 1024 sites can be phased in ~200 minutes using ~1.3GB of RAM. Once sample sizes are encountered where the Hamming distance search begins to dominate, our implementation could be replaced with O(N log N) clustering algorithms that we have implemented within the SHAPEIT3 algorithm12.
