Page 190 - Applied Probability

175
9. Descent Graph Methods
of simulated annealing, almost all proposed steps are accepted, and the
chain broadly samples the state space. As τ declines, fewer unfavorable
steps are taken, and the chain eventually settles on some nearly optimal
state. With luck this state is k or a state equivalent to k if several states are
optimal. Simulated annealing is designed to mimic the gradual freezing of a
substance into a crystalline state of perfect symmetry and hence minimum
energy.
9.4 Descent States and Descent Graphs
To apply the MCMC method to the analysis of human pedigree data, we
must choose an appropriate state space and a mechanism for moving be-
tween neighboring states of the space. Given our goal of computing lo-
cation scores, the state space must capture gene flow at multiple marker
loci. For the sake of simplicity and in keeping with most genetic practice,
only codominant alleles will be allowed at the marker loci. The state space
will also omit mention of the trait locus. This locus is handled somewhat
differently and appears later in our discussion.
The states of our state space are rather complicated graphs describing
gene flow in a pedigree at the participating marker loci. It suffices to fo-
cus on a single pedigree because location scores are computed pedigree
by pedigree. Figure 9.1 (a) depicts a typical pedigree with marker pheno-
types noted at a codominant marker locus. Figure 9.1 (b) conveys more
detailed, but consistent, information about the gene flow in the pedigree.
Each person is replaced by two nodes; the left node is a place holder for
his maternally inherited gene, and the right node is a place holder for his
paternally inherited gene. Arcs connect parent nodes to child nodes and
determine which grandparental genes children inherit. For example, the
granddaughter 8 inherits from her father 4 the maternal gene of her grand-
mother 1. The maternal gene of the grandmother is labeled allele 1, which
is consistent with the observed phenotype 1/4 of the granddaughter. The
combination of the gene flow graph and the assigned founder alleles in Fig-
ure 9.1 (b) constitutes a descent state at the locus. The gene flow graph
alone is called a descent graph at the locus. An assignment of one descent
state (respectively, descent graph) to each participating locus constitutes
a descent state (respectively, descent graph) of the pedigree.
Several comments are in order at this point. First, a descent state at
a locus determines an ordered genotype for each and every person in the
pedigree. Some descent states are consistent with the observed phenotypes
of the pedigree, and some descent states are not. Those that are consistent
are said to be legal; those that are not are illegal. Second, if a descent
graph is consistent with at least one legal descent state, then the descent
graph is legal; otherwise, it is illegal. Obviously, the collection of descent