Page 201 - Applied Probability

9. Descent Graph Methods
186
process. If a parent is homozygous at a locus, then randomly
assign sources to all genes contributed by the parent to his or
her children. Exit the algorithm with success.
(b) If any genotype list is empty, then either there is an inconsistency
in the pedigree data, or one of the rare counterexamples to the
optimality of genotype elimination has occurred. In either case,
exit the algorithm with failure.
(c) Otherwise, choose one of the people with multiple genotypes
currently listed and randomly eliminate all but one of his or her
ordered genotypes. Now return to step 2.
If the algorithm fails, then one should check the pedigree for phenotyp-
ing errors and nonpaternity. One of these two alternatives is certain for a
graphically simple pedigree. If no errors are found, and the pedigree has
cycles or loops—for instance, if it is inbred—then the algorithm should be
retried with different random choices in step 3, part (c).

9.9 Haplotyping

In haplotyping one attempts to find the most likely descent state for a se-
lected group of markers typed on a pedigree [19, 34]. Simulated annealing
is designed to solve combinatorial optimization problems of just this sort.
Because the space of descent states is very large, it is again advantageous to
work on the much smaller state of descent graphs. This entails maximizing
a different function than the conditional likelihood π =Pr(G | M)of a
0
0 G
descent graph G given the marker phenotypes M. Here we assign to G the
0
0
joint likelihood Pr(G) = Pr(G∩M) of the most likely descent state G con-
sistent with both G and M. This modified objective function is substituted
0
for π in the simulated annealing acceptance probability (9.7).
0 G
Recall that the transmission probability Trans(G) in the joint likelihood
Pr(G ∩ M) does not depend on G. A best descent state corresponding to
the descent graph G therefore maximizes the product
0
m

Prior(G) = Pr(a i ),
i=1
where a i is any legal allele vector assigned to component C i of the founder
tree graph associated with G. To maximize Prior(G), one simply maximizes
0
each factor Pr(a i ) over its set S i of legal allele vectors. When the set S i
has one or two members, then it is trivial to choose the best member. If S i
consists of more than two members, then C i must consist of a single descent
tree, and S i contains all possible alleles for the corresponding founder gene.
In this case, one chooses the allele with maximum population frequency.