Combinatorial reconstruction of half-sibling groups

Saad I. Sheikh*, Tanya Y. Berger-Wolf, Ashfaq A, Khokhar, Isabel C. Caballero, Mary V. Ashley, Wanpracha Chaovalitwongse, Bhaskar DasGupta

Department of Computer Science, University of Illinois at Chicago, 851 S. Morgan St (M/C 152), Chicago, IL 60607, USA. ssheikh@cs.uic.edu

Proc LSS Comput Syst Bioinform Conf. August, 2009. Vol. 8, p. 59-67. Full-Text PDF

*To whom correspondence should be addressed.

While full sibling group reconstruction from microsatellite data is a well studied problem, reconstruction of half sibling groups is much less studied, theoretically challenging, and a computationally intense problem. In this paper, we present two different formulations of the half-sib reconstruction problem and prove their NP-hardness. We also present exact solutions for these formulations and develop heuristics. Using biological and synthetics data sets we present experimental results and compare them with the leading alternative software COLONY. We show that our results are computationally superior and allow half-sib group reconstruction in the presence of polygamy (unlike COLONY), which is prevalent in nature.