IMPUTE2 aims to reduce the computing burden through a Monte Carlo algorithm that separates the phasing and imputation tasks. This approach alternately samples phase configurations for genotyped markers and imputes allele probabilities for markers not typed in the GWAS. The cost of the phasing component is proportional to the number of GWAS individuals (N), the number of genotyped markers in the GWAS data (MGWAS), the number of iterations (I), and the square of the number of templates used in each phasing update (K2), or O(N * MGWAS * I * K2). The cost of the imputation component is proportional to the number of GWAS haplotypes (2N), the number of markers in the reference panel (MREF), the number of iterations (I), and the number of haplotypes in the reference panel (H), or O(N * MREF * I * H). Partitioning the analysis in this way allows better scaling with reference panel size, but it requires I repetitions of the imputation step (one for each sampled phase configuration).
