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.

[img] PDF (Pubished Version)
Download (154kB)
View at Publisher Website:


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 ID: 7093
Item Type: Article (Research - C1)
ISSN: 1290-385X
Keywords: population biology; kinship assignment complexity; Tarski algebra; phenotype space
Related URLs:
Additional Information:

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%
Downloads: Total: 1167
Last 12 Months: 73
More Statistics

Actions (Repository Staff Only)

Item Control Page Item Control Page