Assume that we are given two trained HMM models of diploid genotypes (i.e. two haplotypes per individual) for two di erent populations, such that each HMM models the same haplotypes of length m (i.e. m SNPs) with k states at each SNP (i.e. a total of 2k states across the two models). The transition probabilities now also describe the probability of moving between each pair of states coming from the two di erent models. We wish to de ne a test for the local ancestry of a particular segment in the genome. Speci cally, let W be a segment of interest of length w (i.e. a substring of the haplotype), given an input genotype g, we want to calculate the ratio S(g) = l1/l2 , where l1 is the likelihood of the most likely pair of paths of g on the two HMMs given that it traverses only through the HMM of population 1 in window W, and l2 is similarly de ned for the second population. (a) Change the Viterbi algorithm to allow us to calculate S(g)