Rapid multipoint linkage analysis via inheritance vectors in the Elston-Stewart algorithm
- PMID: 11287744
- DOI: 10.1159/000053346
Rapid multipoint linkage analysis via inheritance vectors in the Elston-Stewart algorithm
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.
Copyright 2001 S. Karger AG, Basel.
Similar articles
-
The VITESSE algorithm for rapid exact multilocus linkage analysis via genotype set-recoding and fuzzy inheritance.Nat Genet. 1995 Dec;11(4):402-8. doi: 10.1038/ng1295-402. Nat Genet. 1995. PMID: 7493020
-
Technical note: determining peeling order using sparse matrix algorithms.J Dairy Sci. 2002 Jun;85(6):1623-9. doi: 10.3168/jds.S0022-0302(02)74233-1. J Dairy Sci. 2002. PMID: 12146496
-
PedStr software for cutting large pedigrees for haplotyping, IBD computation and multipoint linkage analysis.Ann Hum Genet. 2009 Sep;73(Pt 5):527-31. doi: 10.1111/j.1469-1809.2009.00531.x. Epub 2009 Jul 9. Ann Hum Genet. 2009. PMID: 19604226
-
Linkage analysis with sequential imputation.Genet Epidemiol. 2003 Jul;25(1):25-35. doi: 10.1002/gepi.10249. Genet Epidemiol. 2003. PMID: 12813724 Review.
-
Breaking loops in large complex pedigrees.Hum Hered. 2008;65(2):57-65. doi: 10.1159/000108937. Epub 2007 Sep 26. Hum Hered. 2008. PMID: 17898536 Review.
Cited by
-
KELVIN: a software package for rigorous measurement of statistical evidence in human genetics.Hum Hered. 2011;72(4):276-88. doi: 10.1159/000330634. Epub 2011 Dec 23. Hum Hered. 2011. PMID: 22189470 Free PMC article.
-
The cluster variation method for efficient linkage analysis on extended pedigrees.BMC Bioinformatics. 2006 Mar 20;7 Suppl 1(Suppl 1):S1. doi: 10.1186/1471-2105-7-S1-S1. BMC Bioinformatics. 2006. PMID: 16723002 Free PMC article.
-
Online system for faster multipoint linkage analysis via parallel execution on thousands of personal computers.Am J Hum Genet. 2006 Jun;78(6):922-35. doi: 10.1086/504158. Epub 2006 May 1. Am J Hum Genet. 2006. PMID: 16685644 Free PMC article.
-
Exploiting gene x gene interaction in linkage analysis.BMC Proc. 2007;1 Suppl 1(Suppl 1):S64. doi: 10.1186/1753-6561-1-s1-s64. Epub 2007 Dec 18. BMC Proc. 2007. PMID: 18466565 Free PMC article.
-
A survey of current software for linkage analysis.Hum Genomics. 2003 Nov;1(1):63-5. doi: 10.1186/1479-7364-1-1-63. Hum Genomics. 2003. PMID: 15601534 Free PMC article. Review.
Publication types
MeSH terms
Grants and funding
LinkOut - more resources
Full Text Sources
Other Literature Sources