Page 138 - Applied Probability

7. Computation of Mendelian Likelihoods
122
question of what two arrays to multiply at any given step. In equation (7.3)
the answer is obvious. In more complex examples, we can resort to a greedy
approach; namely, at each stage we always pick the two arrays that cost
the least to multiply. Ties at any stage are broken by arbitrarily choosing
one of the best pairs of arrays.
7.5 Array Factoring
The calculation of pedigree likelihoods involving many linked markers has
raised interesting challenges. Even with complete phenotyping of all pedi-
gree members, phase ambiguities pose a problem. Lathrop et al. [22] show
that for many fully typed nuclear families (with or without grandparents
appended), the likelihood factors into a product of likelihoods involving
subsets of the loci. These multiplicand likelihoods can be quickly evalu-
ated. Lander and Green [17] take a different approach. They redefine the
likelihood expression (7.1) so that the sums extend over loci rather than
people. In other words, their algorithm steps through the likelihood calcu-
lation locus by locus while considering all people simultaneously at each
locus. This tactic has the consequence of radically displacing the source of
computational complexity. Instead of scaling exponentially in the number
of loci, their algorithm scales linearly. However, since all pedigree members
are taken simultaneously, it scales exponentially in the number of pedigree
members. Although the clever speedups proposed by Kruglyak et al. [15, 16]
help, very large pedigrees are simply beyond the reach of the Lander and
Green algorithm.
A synthesis of these two methods is possible [9]. On one hand, the factor-
ization method of Lathrop et al. [22] ultimately depends on being able to
factor the prior, penetrance, and transmission arrays. On the other hand,
the method of Lander and Green [17] shifts summations from people to
loci. It is possible to decompose on both people and loci in such a manner
that the prior, penetrance, and transmission arrays factor. This sugges-
tion entails viewing the multilocus ordered genotypes of a given person
as originating from a Cartesian product of his or her single-locus ordered
genotypes. A negative consequence of this synthesis is the substitution of a
swarm of small arrays where a few large ones formerly sufficed. In compen-
sation for this complication is the potential benefit of encountering much
smaller initial and intermediate arrays in the likelihood calculation.
To elaborate on this synthesis, consider again a typical person i in a
pedigree with n members. Suppose that i’s phenotype X i is determined
by m loci 1,... ,m taken in their natural order along a chromosome. A
multilocus ordered genotype G i of i decomposes into an ordered sequence
G i =(G i1 , ..., G im ) of single-locus ordered genotypes G ij . Under Hardy-