Like the IMPUTE2 Monte Carlo algorithm, pre-phasing separates the phasing and imputation steps when imputing a GWAS dataset. The computational cost of pre-phasing in our framework is O(N * MGWAS * I * K2). This is the same as the phasing cost for Monte Carlo integration, although in this context the phasing must be performed just once per GWAS dataset. Given a set of pre-phased GWAS haplotypes, the cost of imputation is then O(N * MREF * H); the efficiency of this step makes imputation from pre-phased haplotypes very fast. The cost of each step in our current computing system, in CPU hours, is approximately N * MGWAS * I * K2 * 10−11 for phasing and N * MREF * H * 10−11 for imputation.
