Efficient maximum likelihood pedigree reconstruction. (English) Zbl 1403.92135
Summary: A simple and efficient algorithm is presented for finding a maximum likelihood pedigree using microsatellite (STR) genotype information on a complete sample of related individuals. The computational complexity of the algorithm is at worst \((O(n^32^n))\), where \(n\) is the number of individuals. Thus, it is possible to exhaustively search the space of all pedigrees of up to thirty individuals for one that maximizes the likelihood. A priori age and sex information can be used if available, but is not essential. The algorithm is applied in a simulation study, and to some real data on humans.
MSC:
| 92D10 | Genetics and epigenetics |
| 92D15 | Problems related to evolution |
| 62P10 | Applications of statistics to biology and medical sciences; meta analysis |
References:
| [1] | Almudevar, A., A simulated annealing algorithm for maximum likelihood pedigree reconstruction, Theoretical population biology, 63, 63-75, (2003) · Zbl 1104.62115 |
| [2] | Blouin, M.S., DNA-based methods for pedigree reconstruction and kinship analysis in natural populations, TRENDS in ecology and evolution, 18, 10, 503-511, (2003) |
| [3] | Buntine, W.L., A guide to the literature on learning probabilistic networks from data, IEEE transactions on knowledge and data engineering, 8, 195-210, (1996) |
| [4] | Butler, J.M.; Schoske, R.; Vallone, P.M.; Redman, J.W.; Kline, M.C., Allele frequencies for 15 autosomal STR loci on U.S. Caucasian, african American and hispanic populations, Journal of forensic sciences, 48, 4, (2003), Available online at www.astm.org |
| [5] | Cooper, G.F.; Herskovits, E., A Bayesian method for the induction of probabilistic networks from data, Machine learning, 9, 309-347, (1992) · Zbl 0766.68109 |
| [6] | Cowell, R.G.; Mostad, P., A clustering algorithm using DNA marker information for sub-pedigree reconstruction, Journal of forensic sciences, 48, 6, 1239-1248, (2003) |
| [7] | Cowell, R.G.; Dawid, A.P.; Lauritzen, S.L.; Spiegelhalter, D.J., Probabilistic networks and expert systems, (1999), Springer · Zbl 0937.68121 |
| [8] | Cowell, R.G.; Lauritzen, S.L.; Mortera, J., A gamma model for DNA mixture analyses, Bayesian analysis, 2, 333-348, (2007) · Zbl 1331.92093 |
| [9] | Dawid, A.P.; Mortera, J.; Pascali, V.L.; van Boxel, D., Probabilistic expert systems for forensic inference from genetic markers, Scandinavian journal of statistics, 29, 577-595, (2002) · Zbl 1035.62111 |
| [10] | Egeland, T.; Mostad, P.F.; Mevåg, B.; Stenersen, M., Beyond traditional paternity and identification cases: selecting the most probable pedigree, Forensic science international, 110, 47-59, (2000) |
| [11] | Gill, P.; Ivanov, P.L.; Kimpton, C.; Piercy, R.; Benson, N.; Tully, G.; Evett, I.; Hagelberg, E.; Sullivan, K., Identification of the remains of the romanov family by DNA analysis, Nature genetics, 6, 130-135, (1994) |
| [12] | Heckerman, D.; Geiger, D.; Chickering, D.M., Learning Bayesian networks: the combination of knowledge and statistical data, (), 293-301 |
| [13] | Jones, A.G.; Ardren, W.R., Methods of parentage analysis in natural populations, Molecular ecology, 12, 2511-2523, (2003) |
| [14] | Koivisto, M.; Sood, K., Exact Bayesian structure discovery in Bayesian networks, Journal of machine learning research, 5, 549-573, (2004) · Zbl 1222.68234 |
| [15] | Lauritzen, S.L.; Sheehan, N.A., Graphical models for genetic analyses, Statistical science, 18, 489-514, (2003) · Zbl 1055.62126 |
| [16] | Mortera, J., Analysis of DNA mixtures using probabilistic expert systems, () |
| [17] | Silander, T.; Myllymäki, P., A simple approach to finding the globally optimal Bayesian network structure, (), 445-452 |
| [18] | Singh, A.P., Moore, A.W., 2005. Finding optimal Bayesian networks by dynamic programming. Technical Report CMU-CALD-05-106, Carnegie Mellon University; Singh, A.P., Moore, A.W., 2005. Finding optimal Bayesian networks by dynamic programming. Technical Report CMU-CALD-05-106, Carnegie Mellon University |
| [19] | Thompson, E.A., Inference of genealogical structure, Social science information sur LES sciences social, 15, 477-526, (1976) |
| [20] | Thompson, E.A., Pedigree analysis in human genetics, (1986), John Hopkins University Press Baltimore |
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.
