Rapid Multipoint Linkage Analysis via Inheritance
Vectors in the Elston-Stewart Algorithm
Jeffrey R. O'Connell
Human Heredity, 51(4):226-240 (2001)
Abstract
The calculation of multipoint likelihoods of pedigree data is
crucial for extracting the full available information needed for
both parametric and nonparametric linkage analysis. Recent
mathematical advances in both the Elston-Stewart and
Lander-Green algorithms for computing exact multipoint
likelihoods of pedigree data have enabled researchers to
analyze data sets containing more markers and more
individuals both faster and more efficiently. This paper
presents novel algorithms that further extend the
computational boundary of the Elston-Stewart algorithm.
They have been implemented into the software package
VITESSE v. 2 and are shown to be several orders of
magnitude faster than the original implementation of the
Elston-Stewart algorithm in VITESSE v. 1 on a variety of
real pedigree data. VITESSE v. 2 was faster by a factor
ranging from 168 to over 1,700 on these data sets, thus
making a qualitative difference in the analysis. The main
algorithm is based on the faster computation of the
conditional probability of a component nuclear family within
the pedigree by summing over the joint genotypes of the
children instead of the parents as done in the VITESSE v. 1.
This change in summation allows the parent-child
transmission part of the calculation to be not only computed
for each parent separately, but also for each locus
separately by using inheritance vectors as is done in the
Lander-Green algorithm. Computing both of these
separately can lead to substantial computational savings.
The use of inheritance vectors in the nuclear family
calculation represents a partial synthesis of the techniques
of the Lander-Green algorithm into the Elston-Stewart
algorithm. In addition, the technique of local set recoding is
introduced to further reduce the complexity of the nuclear
family computation. These new algorithms, however, are not
universally faster on all types of pedigree data compared to
the method implemented in VITESSE v. 1 of summing over
the parents. Therefore, a hybrid algorithm is introduced
which combines the strength of both summation methods by
using a numerical heuristic to decide which of the two to use
for a given nuclear family within the pedigree and is shown
to be faster than either method on its own. Finally, this paper
discusses various complexity issues regarding both the
Elston-Stewart and Lander-Green algorithms and possible
future directions of further synthesis.
back to link-compute