Speaker: Bogdan Pasaniuc
Day:  Wednesday, 11/08/2006
Room: ITEB 201
Time: 2:30pm
 
Title: Set Covering approach for Reconstruction of Sibling Relationships
 
Knowledge about sibling relationships is used in genetic epidemiology,
conservation biology, and animal management. For example, knowledge of the
genetic relationships among individuals is critical for estimating
heritability of quantitative characters, for characterizing mating systems
and fitness, and for managing populations of endangered species. When
parental data are available, sibling groups can be established through
parentage assignments. Assignment of individuals to full or half sibling
groups in the absence of parental data is more challenging. Nonetheless,
for many studies, particularly those that rely on sampling of wild
populations it is often more practical to sample cohorts of offspring
rather than parent/offspring groups. A set cover optimization technique for
reconstructing sibling relationships based on single generation genetic
data without parental information is presented. The output of the algorithm
is a partition of the individuals into some number of clusters. In order to
evaluate the goodness of the partition relative to the true family
partition, a distance between two partitions is defined. A method of
computing the distance between two partitions in polynomial time is also
discussed.
 
References:
1. W.A. Chaovalitwongse, T. Y. Berger-Wolf, B. DasGupta, and M.V. Ashley.
Set Covering Approach for Reconstruction of Sibling Relationships, to
appear in Optimization Methods and Software.
2. D. Gusfield. Partition-distance: A problem and class of perfect graphs
arising in clustering. Information Processing Letters, 82(3):159--164, May
2002.