Voir la notice de l'article provenant de la source Numdam
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.
Keywords: population biology, kinship assignment complexity, Tarski algebra, phenotype space
@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},
pages = {323--333},
publisher = {EDP-Sciences},
volume = {42},
number = {2},
year = {2008},
doi = {10.1051/ita:2007034},
mrnumber = {2401265},
zbl = {1147.68875},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ita:2007034/}
}
TY - JOUR AU - Litow, Bruce AU - Konovalov, Dmitry TI - Phenotype space and kinship assignment for the Simpson index JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2008 SP - 323 EP - 333 VL - 42 IS - 2 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ita:2007034/ DO - 10.1051/ita:2007034 LA - en ID - ITA_2008__42_2_323_0 ER -
%0 Journal Article %A Litow, Bruce %A Konovalov, Dmitry %T Phenotype space and kinship assignment for the Simpson index %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2008 %P 323-333 %V 42 %N 2 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ita:2007034/ %R 10.1051/ita:2007034 %G en %F 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) no. 2, pp. 323-333. doi: 10.1051/ita:2007034
Cité par Sources :