For imputation using mimimac3, we break up a chromosome into K consecutive segments. If Ui denotes the number of unique haplotypes and Mi denotes the number of markers in segment i, then complexity is O(N×∑i=1,…,KUiMi)+O(NKH) The second term accounts for the complexity of transitions between blocks, which occur in the original state space. Thus, although very short segments could reduce the number of unique haplotypes per segment (Ui) and complexity measured by the first term, such segments would also increase the total number of segments (K) and complexity measured by the second term. An optimal allocation of genomic regions must balance these two goals.
