Phenotype space and kinship assignment for the Simpson index
Litow, Bruce, and Konovalov, Dmitry (2008) Phenotype space and kinship assignment for the Simpson index. RAIRO - Theoretical Informatics and Applications, 42 (2). pp. 323-333.
PDF (Pubished Version)
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.
|Item Type:||Article (Refereed Research - C1)|
|Keywords:||population biology; kinship assignment complexity; Tarski algebra; phenotype space|
Reproduced with permission from EDP Sciences. RAIRO - Theoretical Informatics and Applications.
|Date Deposited:||27 Mar 2010 00:37|
|FoR Codes:||08 INFORMATION AND COMPUTING SCIENCES > 0802 Computation Theory and Mathematics > 080201 Analysis of Algorithms and Complexity @ 70%
06 BIOLOGICAL SCIENCES > 0604 Genetics > 060411 Population, Ecological and Evolutionary Genetics @ 30%
|SEO Codes:||89 INFORMATION AND COMMUNICATION SERVICES > 8999 Other Information and Communication Services > 899999 Information and Communication Services not elsewhere classified @ 100%|
|Citation Count from Web of Science||