×

A simulated annealing algorithm for maximum likelihood pedigree reconstruction. (English) Zbl 1104.62115

Summary: The calculation of maximum likelihood pedigrees for related organisms using genotypic data is considered. The problem is formulated so that the domain of optimization is a permutation space. This is a feature shared by the travelling salesman problem, for which simulated annealing is known to be effective. Using this technique it is found that pedigrees can be reconstructed with minimal error using genotypic data of a quality currently realizable. In complex pedigrees accurate reconstruction can be done with no a priori age or sex information. For smaller numbers of individuals a method of efficiently enumerating all admissible pedigrees of nonzero likelihood is given.

MSC:

62P10 Applications of statistics to biology and medical sciences; meta analysis
92D15 Problems related to evolution
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aarts, E.; Korst, J., Simulated Annealing and Boltzmann Machines (1989), Wiley: Wiley Chichester · Zbl 0674.90059
[2] Aarts, E.; van Laarhoven, P. J.M., Statistical coolinga general approach to combinatorial optimization problems, Philips J. Res., 40, 193-226 (1985)
[3] Aarts, E., van Laarhoven, P.J.M., 1985b. A new polynomial-time cooling schedule. Proceedings of IEEE International Conference on Computer-Aided Design, Santa Clara, November 1985, pp. 206-208.; Aarts, E., van Laarhoven, P.J.M., 1985b. A new polynomial-time cooling schedule. Proceedings of IEEE International Conference on Computer-Aided Design, Santa Clara, November 1985, pp. 206-208.
[4] Almudevar, A., A bootstrap assessment of variability in pedigree reconstruction based on DNA markers, Biometrics, 57, 757-763 (2001) · Zbl 1209.62249
[5] Almudevar, A.; Field, C., Estimation of single generation sibling relationships based on DNA markers, J. Agric. Biol. Environ. Stat., 2, 212-229 (1999)
[6] Blouin, M. S.; Parsons, M.; Lacaille, V.; Lotz, S., Use of microsatellite loci to classify individuals by relatedness, Mol. Ecol., 5, 393-401 (1996)
[7] Bruford, M. W.; Wayne, R. K., Microsatellites and their application to population genetic studies, Curr. Opin. Genet. Dev., 3, 939-943 (1993)
[8] Cannings, C.; Thompson, E., Genealogical and Genetic Structure (1981), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0482.92012
[9] Geyer, C. J.; Ryder, O. A.; Chemnick, L. G.; Thompson, E. A., Analysis of relatedness in the California condorsfrom DNA fingerprints, Mol. Biol. Evol., 10, 571-589 (1993)
[10] Gusfield, D., Partition-distancea problem and class of perfect graphs arising in clustering, Inf. Process. Lett., 82, 159-164 (2002) · Zbl 1013.68142
[11] Haig, S. M.; Ballou, J. D.; Casna, N. J., Identification of kin structure among Guam rail foundersa comparison of pedigrees and DNA profiles, Mol. Ecol., 3, 109-119 (1994)
[12] Kirkpatrick, S.; Gelatt, C. D.; Vecchi, M. P., Optimization by simulated annealing, Science, 220, 671-680 (1983) · Zbl 1225.90162
[13] Lynch, M., Estimation of relatedness by DNA fingerprinting, Mol. Biol. Evol., 5, 584-599 (1988)
[14] Marshall, T. C.; Slate, J.; Kruuk, L. E.B.; Pemberton, J. M., Statistical confidence for likelihood-based paternity inference in natural populations, Mol. Ecol., 7, 639-655 (1998)
[15] Meagher, T. R.; Thompson, E., The relationship between single parent and parent pair genetic likelihoods in genealogy reconstruction, Theor. Popul. Biol., 29, 87-106 (1986) · Zbl 0581.92013
[16] Meagher, T. R.; Thompson, E., Analysis of parentage for naturally established seedlings of chamaelirium luteum, Ecology, 68, 803-812 (1987), (liliacae)
[17] Metropolis, N.; Rosenbluth, A. W.; Rosenbluth, M. N.; Teller, A. H.; Teller, E., Equations of state calculations by fast computing machines, J. Chem. Phys., 21, 1087-1092 (1953) · Zbl 1431.65006
[18] Painter, I., 1994. Analysis of full-sibship configurations in a maternal half-sibship. Technical Report No. 272, Dept. of Statistics, University of Washington, Seattle, Washington.; Painter, I., 1994. Analysis of full-sibship configurations in a maternal half-sibship. Technical Report No. 272, Dept. of Statistics, University of Washington, Seattle, Washington.
[19] Painter, I., Sibling reconstruction without parental information, J. Agric. Biol. Environ. Stat., 2, 212-229 (1996)
[20] Queller, D. C.; Goodnight, K. F., Estimating relatedness using genetic markers, Evolution, 43, 258-279 (1989)
[21] Thompson, E., Gene identities and multiple relationships, Biometrics, 30, 667-680 (1974) · Zbl 0292.92004
[22] Thompson, E., Estimation of pairwise relationships, Ann. Hum. Genet., 39, 173-188 (1975)
[23] Thompson, E., Inference of genealogical structure, Soc. Sci. Inf., 15, 477-526 (1976)
[24] Thompson, E., A paradox of genealogical inference, Adv. Appl. Probab., 8, 648-650 (1976)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.