We investigate the computational structure of the biological kinship assignment problem by abstracting away all biological details that are irrelevant to computation. The computational structure depends on phenotype space, which we formally define. We illustrate this approach by exhibiting an approximation algorithm for kinship assignment in the case of the Simpson index with a priori error bound and running time that is polynomial in the bit size of the population, but exponential in phenotype space size. This algorithm is based on a relaxed version of the assignment problem, where fractional assignments (over the reals) are permitted.
@article{ITA_2008__42_2_323_0,
author = {Litow, Bruce and Konovalov, Dmitry},
title = {Phenotype space and kinship assignment for the Simpson index},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
volume = {42},
year = {2008},
pages = {323-333},
doi = {10.1051/ita:2007034},
mrnumber = {2401265},
zbl = {1147.68875},
language = {en},
url = {http://dml.mathdoc.fr/item/ITA_2008__42_2_323_0}
}
Litow, Bruce; Konovalov, Dmitry. Phenotype space and kinship assignment for the Simpson index. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) pp. 323-333. doi : 10.1051/ita:2007034. http://gdmltest.u-ga.fr/item/ITA_2008__42_2_323_0/
[1] , A simulated annealing algorithm for maximum likelihood pedigree reconstruction. Theor. Popul. Biol. 63 (2003) 63-75. | Zbl 1104.62115
[2] and , Estimation of single-generation sibling relationships based on dna markers. J. Agr. Biol. Envir. St. 4 (1999) 136-165. | MR 1812079
[3] , and , Algorithms in Real Algebraic Geometry. Springer (2005). | MR 1998147 | Zbl 1102.14041
[4] , , and , Combinatorial reconstructions of sibling relationships. In 6th International Symposium on Computational Biology and Genome Informatics (CBGI), Salt Lake City, Utah (2005) 1252-1255.
[5] , Quantifier elimination for real closed fields by cylindrical algebraic decomposition. In Automata theory and formal languages. Springer (1975) 134-183. | MR 403962 | Zbl 0318.02051
[6] , Fast parallel matrix inversion algorithms. In 16th IEEE FOCS (1975) 11-12. | MR 428785
[7] , and , Mathematical Logic. Springer (1984). | MR 736838 | Zbl 0556.03001
[8] and . Computer software for performing likelihood tests of pedigree relationship using genetic markers. Mol. Ecol. 8 (1999) 1231-1234.
[9] , Complexity of deciding Tarski algebra. J. Symb. Comput. 5 (1988) 65-108. | MR 949113 | Zbl 0689.03021
[10] , , Vol. I. Freeman, 2nd edn. (1985). | MR 780184 | Zbl 0557.16001
[11] and , Methods of parentage analysis in natural populations. Mol. Ecol. 12 (2003) 2511-2523.
[12] , Accuracy of four heuristics for the full sibship reconstruction problem in the presence of genotype errors. In The Fourth Asia Pacific Bioinformatics Conference, 13-16 Feb, 2006, Taiwan (2006) 7-16.
[13] , and , Kingroup: a program for pedigree relationship reconstruction and kin group assignments using genetic markers. Mol. Ecol. Notes 4 (2004) 779-782.
[14] , and , Modified simpson o(n3) algorithm for the full sibship reconstruction problem. Bioinformatics 21 (2005) 3912-3917.
[15] , and , Partition-distance via the assignment problem. Bioinformatics 21 (2005) 2463-2468.
[16] , Algorithmic Algebra. Springer (1993). | MR 1239443 | Zbl 0804.13009
[17] , and , Analysis of parentage determination in atlantic salmon (salmo salar) using microsatellites. Anim. Genet. 29 (1998) 363-370.
[18] , Sur les ensembles définissables de nombres réels. Fundamenta Mathematicae 17 (1931) 210-239. | JFM 57.0060.02
[19] , A decision method for elementary algebra and geometry. Technical report, Rand Corp. (1948). | MR 28796 | Zbl 0035.00602
[20] , Sibship reconstruction from genetic data with typing errors. Genetics 166 (2004) 1963-1979.