2005-27: Combinatorial Reconstruction of Sibling Relationships in Absence of Parental Data

DIMACS TR: 2005-27

Combinatorial Reconstruction of Sibling Relationships in Absence of Parental Data

Authors: Tanya Y. Berger-Wolf, Bhaskar DasGupta, Wanpracha Chaovalitwongse and Mary V. Ashley

ABSTRACT
We present a new algorithm for reconstructing sibling relationships in a single generation of individuals without parental information, using data from codominant DNA markers such as microsatellites. We use the simple genetic constraints on the full-sibling groups, such as the limit of four alleles per single locus and no more than two alleles from each potential parent per locus. We then use combinatorial optimization techniques to extract a minimum number of groups that satisfy these constraints. The results of a simulation study of a relaxed version of the algorithm show that our approach is reasonably accurate and the full version of the algorithm should be pursued. Our algorithm does not require any a priori knowledge about allele frequency, population size, mating system, or family size distributions.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2005/2005-27.ps.gz

DIMACS Home Page