RAIRO-Theor. Inf. Appl.
Volume 42, Number 2, April-June 2008
|Page(s)||323 - 333|
|Published online||06 September 2007|
Phenotype space and kinship assignment for the simpson index
Bioinformatics Applications Research Centre,
School of MP & IT, James Cook University, Townsville, Qld. 4811, Australia;
Accepted: 3 August 2007
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.
Mathematics Subject Classification: 68X30 / 68W25 / 92D25
Key words: Population biology / kinship assignment complexity / Tarski algebra / phenotype space
© EDP Sciences, 2007
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.