bibliography: linkage algorithms

A Bibliography on Algorithms in Linkage Analysis

key words: Elston-Stewart algorithm, estimation-maximization algorithm (EM),
hidden Markov model (HMM), Markov chain simulation, Monte Carlo Markov chain,
Monte Carlo simulation, pedigree likelihood, random walk

This list is compiled by WentianLi of Rockefeller University.

Papers related to an approximated calculation of pedigree likelihood are labeled by

Last modified: December 29, 2003

Early History of Estimation of Linkage
(adopted from A.W.F. Edwards, Ann. Hum. Genet. 60, 237-249 (1996))

1912: G.N. Collins, "Gametic coupling as a cause of correlations", Am. Naturalist, 48, 524-534. [using Yule's measure of association.]
J.A. Harris: "A simple test of the goodness of fit of Mendelian ratios", Am. Naturalist, 46, 741-745. [using Pearson's chi goodness-of-fit.]
R.A. Fisher,"On an absolute criterion for fitting frequency curves", Mess. Math. 41, 155-160. [introduing maximum likelihood method.]

1914: G.U.Yule, F.L.Engledow, "The determination of the best value of the coupling ratio from a given set of data" (abstract), Phil. Trans. Royal Soc. A, 194, 257-319.
F.L.Engledow, G.U.Yule, "The determination of the best value of the coupling-ratio from a given set of data", Proc. Camb. Phil. Soc. 17, 436-440. (same title published in Am. Naturalist, 49, 127-128 (1915)). [following Collins (1912).]
C.B.Bridge, "The chromosome hypothesis of linkage applied to cases in sweet peas and primula", Am. Naturalist, 48, 524-534.

1916: H.J. Muller, "The mechanism of crossing-over", Am. Naturalist, 50, 193,221, "II", 50, 284-305; "III", 50, 350-366; "IV", 50, 421-434. [his doctorial thesis. he might propose 'Haldane map' before Haldane.]
R.A. Emerson, "The calculation of linkage intensities", Am. Naturalist, 50, 411-420. [similar to Engledow, Yule (1914).]

1919: J.B.S. Haldane, "The probable errors of calculated linkage values, and the most accurate method of determining gametic from certain zygotic series", J. Geneti. 8, 291-297. [similar to Engledow, Yule (1914).]
J.B.S. Haldane, "The combination of linkage values, and the calculation of distances between the loci of linked factors", J. Geneti. 8, 299-309. ['Haldane's map.]

1922: R.A. Fisher,"On the mathematical foundations of theoretical statistics", Phil. Trans. Royal Soc. A, 222, 309-368.
R.A. Fisher, "The systematic location of genes by means of crossover observations", Am. Naturalist, 56, 406-411. [application of his maximum likelihood method.]

1925: R.A. Fisher, B. Balmukand, "The estimation of linkage from the offspring of selfed heterozygotes", J. Genet. 20, 79-92. [summary of 5 ways to estimate recombination fraction.]

1934-35: J.B.S. Haldane, "Methods for the detection of autosomal linkage in man", Ann. Eugen, 6, 26-65 (1934).
R.A.Fisher, "The amount of information supplied by records of families as a function of the linkage in the population sampled", Ann. Eugen. 6, 66-70 (1934).
R.A.Fisher, "The detection of linkage with 'dominant' abnormalities", Ann. Eugen. 6, 187-201 (1935). [turn attention to linkage problem in men.]

Early History of Estimation of Linkage (adopted from A.W.F. Edwards, Ann. Hum. Genet. 60, 237-249 (1996))
1912:	G.N. Collins, "Gametic coupling as a cause of correlations", Am. Naturalist, 48, 524-534. [using Yule's measure of association.] J.A. Harris: "A simple test of the goodness of fit of Mendelian ratios", Am. Naturalist, 46, 741-745. [using Pearson's chi goodness-of-fit.] R.A. Fisher,"On an absolute criterion for fitting frequency curves", Mess. Math. 41, 155-160. [introduing maximum likelihood method.]
1914:	G.U.Yule, F.L.Engledow, "The determination of the best value of the coupling ratio from a given set of data" (abstract), Phil. Trans. Royal Soc. A, 194, 257-319. F.L.Engledow, G.U.Yule, "The determination of the best value of the coupling-ratio from a given set of data", Proc. Camb. Phil. Soc. 17, 436-440. (same title published in Am. Naturalist, 49, 127-128 (1915)). [following Collins (1912).] C.B.Bridge, "The chromosome hypothesis of linkage applied to cases in sweet peas and primula", Am. Naturalist, 48, 524-534.
1916:	H.J. Muller, "The mechanism of crossing-over", Am. Naturalist, 50, 193,221, "II", 50, 284-305; "III", 50, 350-366; "IV", 50, 421-434. [his doctorial thesis. he might propose 'Haldane map' before Haldane.] R.A. Emerson, "The calculation of linkage intensities", Am. Naturalist, 50, 411-420. [similar to Engledow, Yule (1914).]
1919:	J.B.S. Haldane, "The probable errors of calculated linkage values, and the most accurate method of determining gametic from certain zygotic series", J. Geneti. 8, 291-297. [similar to Engledow, Yule (1914).] J.B.S. Haldane, "The combination of linkage values, and the calculation of distances between the loci of linked factors", J. Geneti. 8, 299-309. ['Haldane's map.]
1922:	R.A. Fisher,"On the mathematical foundations of theoretical statistics", Phil. Trans. Royal Soc. A, 222, 309-368. R.A. Fisher, "The systematic location of genes by means of crossover observations", Am. Naturalist, 56, 406-411. [application of his maximum likelihood method.]
1925:	R.A. Fisher, B. Balmukand, "The estimation of linkage from the offspring of selfed heterozygotes", J. Genet. 20, 79-92. [summary of 5 ways to estimate recombination fraction.]
1934-35:	J.B.S. Haldane, "Methods for the detection of autosomal linkage in man", Ann. Eugen, 6, 26-65 (1934). R.A.Fisher, "The amount of information supplied by records of families as a function of the linkage in the population sampled", Ann. Eugen. 6, 66-70 (1934). R.A.Fisher, "The detection of linkage with 'dominant' abnormalities", Ann. Eugen. 6, 187-201 (1935). [turn attention to linkage problem in men.]

2003

M Fishelson, D Geiger (2003), "Optimizing exact genetic linkage computations", Proceedings of the Seventh International Conference on Research in Computational Molecular Biology , pp.114-121.
Antonio Piccolboni, Dan Gusfield (2003), "On the complexity of fundamental computational problems in pedigree analysis", Journal of Computational Biology,10(5):763-773.

2002

M Fishelson, D Geiger (2002), "Exact genetic linkage computations for general pedigrees", ISMB, 189-198.
Dajun Qian, Lasr Backmann (2002),
"Minimum-recombinant haplotyping in pedigrees",
American Journal of Human Genetics, 70:1434-1445.

2001

Jeffrey R O'Connell (2001),
"Rapid multipoint linkage analysis via inheritance vectors in the Elston-Stewart algorithm",
Human Heredity, 51(4):226-240.
[ abstract ]

2000

DF Gudbjartsson, K Jonasson, ML Frigge, and A Kong (2000),
"Allegro, a new computer program for multipoint linkage analysis",
Nature Genetics, 25:12-13.
JR O'Connell (2000),
"Genome scan of complex traits by haplotype sharing correlation",
Genetic Epidemiology, 21 (suppl 1):S582-S587.
Pradip Tapadar, Saurabh Ghosh, Partha P Majumder (2000),
"Haplotyping in pedigree via a genetic algorithm",
Human Heredity, 50:43-56.

1999

K Jense, A Kong (1999),
"Blocking Gibbs sampling for linkage analysis in large pedigrees with many loops",
American Journal of Human Genetics, 65:885-901.
JR O'Connell, DE Weeks (1999),
"An optimal algorithm for automatic genotype elimination",
American Journal of Human Genetics, 65:1733-1740.
AA Schaffer (1999),
"Computing probabilities of homozygosity by descent",
Genetic Epidemiology, 16:135-149.

1998

L Almasy, J Blangero (1998),
"Multipoint quantitative-trait linkage analysis in general pedigrees",
American Journal of Human Genetics, 62:1198-1211.
[ full text (PDF) ]
A Becker, D Geiger, AA Schaffer (1998),
"Automatic selection of loop breakers for genetic linkage analysis",
Human Heredity, 48:49-60.
CS Jensen, N Sheehan (1998),
"Problems with determination of noncommunicating classes for Monte Carlo Markov chain applications in pedigree analysis",
Biometry, 54:416-425.
L Kruglyak, ES Lander (1998),
"Faster multipoint linkage analysis using Fourier transforms",
Journal of Computational Biology, 5:1-7.

1997

SW Guo (1997),
"Computation of multilocus prior probability of autozygosity for complex inbred pedigrees",
Genetic Epidemiology, 14:1-15.
RM Idury, RC Elston (1997),
A faster and more general hidden Markov model algorithm for multipoint likelihood calculations,
Human Heredity, 47(4):197-202.
CS Jensen (1997),
"Blocking Gibbs sampling for interference in large and complex Bayesian networks with applications in genetics",
Ph.D Thesis (Dept of Computer Science, Aalborg University, Denmark)
S Lin, TP Speed (1997),
"An algorithm for haplotype analysis",
Journal of Computational Biology, 4:535-546.
Cedric AB Smith, David A Stephens (1997),
"Simple likelihood and probability calculations for linkage analysis",
in Genetic Mapping of Disease Genes eds I.H. Pawlowitzki, J.H. Edwards, E.A. Thompson, 73-96 (Academic Press, London, 1997),

1996

Leonid Kruglyak, Mark J Daly, Mary Pat Reeve-Daly, Eric S. Lander (1996),
"Parametric and non-parametric linkage analysis: a unified multipoint approach",
American Journal of Human Genetics, 58(6):1347-1363.
E Sobel, K Lange (1996),
"Descent graphs in pedigree analysis: applications to haplotyping, location scores, and marker sharing statistics",
American Journal of Human Genetics, 58:1323-1337.
E Sobel, K Lange, JR O'Connell, DE Weeks (1996),
"Haplotyping algorithms", in Genetic Mapping and DNA Sequencing , eds. T Speed, MS Waterman (Springer).
AA Schaffer (1996),
Faster linkage analysis computations for pedigrees with loops or unused alleles,
Human Heredity, 46:226-235.
EA Thompson (1996),
"Likelihood and linkage: from Fisher to the future",
Annals of Statistics, 24(2):449-465.

1995

RW Kramer, DE Weeks, DM Chiarulli (1995),
An incremental algorithm for efficient multipoint linkage analysis ,
Human Heredity, 45:323-336.
L Kruglyak, MJ Daly, ES Lander (1995),
"Rapid multipoint linkage analysis of recessive traits in nuclear families, including homozygosity mapping",
American Journal of Human Genetics, 56:519-527.
S Lin (1995),
"A scheme for constructing an irreducible Markov chain for pedigree data",
Biometrics, 51:318-322.
JR O'Connell, DE Weeks (1995),
The VITESSE algorithm for rapid exact multilocus linkage analysis via genotype set-recoding and fuzzy inheritance ,
Nature Genetics, 11:402-408.

1994

S Dwarkadas, AA Schaffer, RW Cottingham Jr., AL Cox, P Keleher, W Zwaenepoel (1994),
Parallelization of general-linkage analysis problems ,
Human Heredity, 44(3):127-41.
SW Guo, EA Thompson (1994),
"Monte Carlo estimation of mixed models for large complex pedigree",
Biometrics, 50(2):417-432.
M Irwin, N Cox, A Kong (1994),
Sequential imputation for multilocus linkage analysis ,
Proceedings of National Academy of Sciences (USA), 91:11684-11688.
S Lin, EA Thompson, EM Wijsman (1994),
"A faster mixing algorithm for Hastings-Metropolis updates on complex pedigrees",
Annals of Human Genetics, 58:343-357.
AA Schaffer, SK Gupta, K Shriram, RW Cottingham Jr. (1994),
Avoiding recomputation in linkage analysis ,
Human Heredity, 44(4):225-37.
EA Thompson (1994),
"Monte Carlo likelihood in the genetic mapping of complex traits",
Philosophical Transaction of Royal Society of London (B. Biological Sciences), 344(1310):345-350. (discussion, 350-351).
EA Thompson (1994),
"Monte Carlo likelihood in linkage analysis",
Statistical Sciences, 9:355-366.

1993

RW Cottingham Jr., RM Idury, AA Schaffer (1993),
Fast sequential genetic linkage computations ,
American Journal of Human Genetics, 53:252-263.
CJ Geyer, EA Thompson (1993),
"Annealing Markov chain Monte Carlo with applications to pedigree analysis", (preprint #589, School of Statistics, University of Minnesota)
E Sobel, K Lange (1993),
"Metropolis sampling in pedigree analysis",
Statistical Methods in Medical Research, 2:263-282.
EA Thompson (1993),
"Monte Carlo analysis on a large pedigree",
Genetic Epidemiology, 10(6):677-682.

1992

TM Goradia, K Lange, PL Miller, PM Nadkarni (1992),
Fast computation of genetic likelihoods on human pedigree data,
Human Heredity, 42:42-62.
SW Guo, EA Thompson (1992),
"A Monte Carlo method for combined segregation and linkage analysis",
American Journal of Human Genetics, 51:1111-1126.
EA Thompson (1992),
"Estimating polygenic models for multivariate data on large pedigrees",
Genetics, 131(4):971-978.

1991

SW Guo, EA Thompson (1991),
"Monte Carlo estimation of variance component models for large complex pedigrees",
IMA Journal of Mathematics Applied in Medicine and Biology, 8:171-189.
A Kong (1991),
"Effecient methods for computing linkage likelihoods of recessive diseases in unbred pedigrees",
Genetic Epidemiology, 8:81-103.
K Lange, E Sobel (1991),
"A random walk method for computing genetic location scores",
American Journal of Human Genetics, 49:1320-1334.
EA Thompson, SW Guo (1991),
"Evaluation of likelihood ratios for complex genetic models",
IMA Journal of Mathematics Applied in Medicine and Biology, 8:149-169.

1990

EA Thompson (1990),
"Pedigree analysis for quantitative traits: variance components without matrix inversion",
Biometrics, 46(2):399-413.

1989

K Lange, S Matthysse (1989),
"Simulations of pedigree genotypes by random walks",
American Journal of Human Genetics, 45:959-970.
K Lange, DE Weeks (1989),
"Effecient computation of lod scores: genotype elimination, genotype redefinition, and hybrid maximum likelihood algorithms",
Annals of Human Genetics, 53:67-83.
DE Weeks, K Lange (1989),
"Trials, tribulations, and triumphs of the EM algorithm in pedigree analysis",
IMA Journal of Mathematics Applied in Medicine & Biology, 6(4):209-232.

1988

GM Lathrop, JM Lalouel (1988),
Effecient computations in multilocus linkage analysis ,
American Journal of Human Genetics, 42:498-505.

1987

E Lander, P Green (1987),
"Construction of multilocus genetic linkage maps in human",
Proceedings of National Academy of Sciences (USA), 84:2363-2367.
K Lange, TM Goradia (1987),
"An algorithm for automatic genotype elimination", American Journal of Human Genetics, 40:250-256.
EA Thompson (1987),
"Crossover counts and likelihood in multipoint linkage analysis",
IMA Journal of Mathematics Applied in Medicine & Biology, 4:93-108.
EM Wijsman (1987),
"A deductive method of haplotype analysis in pedigree",
American Journal of Human Genetics, 41:356-373.

1986

GM Lathrop, JM Lalouel, RL White (1986),
"Construction of human genetic linkage maps: likelihood calculations for multilocus linkage analysis",
Genetic Epidemiology, 3:39-52.
A Thomas (1986),
"Optimal computation of probability functions for pedigree analysis,"
IMA Journal of Mathematics Applied in Medicine and Biology, 3:167-178.

1985

Michael Braverman (1985),
"An algorithm to improve the computational efficiency of genetic linkage analysis",
Computers and Biomedical Research, 18:24-36.
GM Lathrop, JM Lalouel, C Julier, J Ott (1985),
"Multilocus linkage analysis in humans: detection of linkage and estimation of recombination",
American Journal of Human Genetics, 37(3):482-98.

1984

GM Lathrop, JM Lalouel (1984),
Easy calculations of lod scores and genetic risks on small computers ,
American Journal of Human Genetics, 36:460-465.
GM Lathrop, JM Lalouel, C Julier, J Ott (1984),
Strategies for multilocus linkage in humans ,
Proceedings of National Academy of Science (USA), 81:3443-3446.

1983

K Lange, M Boehnke (1983),
"Extensions to pedigree analysis. V. Optimal calculation of Mendelian likelihood",
Human Heredity, 33:291-301.

1981

FM Demenais, RC Elston (1981),
A general transmission probability model for pedigree data,
Human Heredity, 31(2):93-99.

1979

J Ott (1979),
"Maximum likelihood estimation by counting methods under polygenic and mixed models in human pedigree",
American Journal of Human Genetics, 31:161-175.

1978

C Cannings, EA Thompson, MH Skolnick (1978),
"Probability functions on complex pedigrees",
Advances in Applied Probability, 10:26-61.
J Ott (1978),
"A simple scheme for the analysis of HLA linkage in pedigree",
Annals of Human Genetics, 42:255-257.

1977

EA Thompson (1977),
"Peeling programs for pedigrees of arbitrary complexity",
Technical Report No. 6, Department of Medical Biophysics and Computing, University of Utah (March).
EA Thompson (1977),
"Peeling programs for zero-loop pedigrees",
Technical Report No. 5, Department of Medical Biophysics and Computing, University of Utah.

1976

C Cannings, EA Thompson, MH Skolnick (1976),
"Recursive derivation of likelihoods on pedigrees of arbitrary complexity",
Advances in Applied Probability, 8:622-625.

1975

K Lange, RC Elston (1975),
"Extensions to pedigree analysis. I. Likelihood calculation for simple and complex pedigrees",
Human Heredity, 25:95-105.

1974

J Ott (1974),
"Estimation of the recombination fraction in human pedigree - efficient computation of the likelihood for human linkage analysis",
American Journal of Human Genetics, 26: 588-597.

1972

I Hcuch, FMH Li (1972),
"PEDIG - A computer program for calculation of genotype probabilities, using phenotypic information",
Clinical Genetics, 3:501-504

1971

GA Chase, EA Murphy, DR Bolling (1971),
"The Encu scoring system: a strategy for solving a class of single-locus genetic counseling problems",
Clinical Genetics, 2, 141-148.
RC Elston, J Stewart (1971),
A general model for the analysis of pedigree data ,
Human Heredity, 21:523-542.

1970

J Hilden (1970),
"GENEX - An algebraic approach to pedigree probability calculus",
Clinical Genetics, 1:319-348.
EA Murphy (1970),
"The Ensu scoring system in genetic counseling",
Annals of Human Genetics, 34:73-78.