Phenotype space and kinship assignment for the Simpson index

Litow, Bruce;Konovalov, Dmitry

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.

Journal

N/A

Publication Name

N/A

Volume

ISBN/ISSN

1290-385X

Edition

N/A

Issue

Pages Count

Location

N/A

Publisher

EDP Sciences

Publisher Url

N/A

Publisher Location

Les Ulis, Cedex, France

Publish Date

N/A

Url

N/A

Date

N/A

EISSN

N/A

DOI

10.1051/ita:2007034