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 (150Kb)
View at Publisher Website: http://dx.doi.org/10.1051/ita:2007034

Abstract

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 (Refereed Research - C1)
Keywords: population biology; kinship assignment complexity; Tarski algebra; phenotype space
Additional Information:

Reproduced with permission from EDP Sciences. RAIRO - Theoretical Informatics and Applications.

Related URLs:
ISSN: 1290-385X
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 Web of Science 2
Downloads: Total: 43
Last 12 Months: 1
More Statistics

Actions (Repository Staff Only)

Item Control Page Item Control Page