title: Combinatorial reconstruction of half-sibling groups from microsatellite data.
abstract: 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 computationally demanding. In this paper, we present a formulation of the half-sibling reconstruction problem and prove its APX-hardness. We also present exact solutions for this formulation and develop heuristics. Using biological and synthetic datasets we present experimental results and compare them with the leading alternative software COLONY. We show that our results are competitive and allow half-sibling group reconstruction in the presence of polygamy, which is prevalent in nature.
authors.affiliation: Department of Computer Science, University of Illinois at Chicago, 851 S. Morgan St (M/C 152), Chicago, IL 60607, USA. saad@saadsheikh.com
authors.forename: Saad I
authors.initials: SI
authors.lastname: Sheikh
authors.forename: Tanya Y
authors.initials: TY
authors.lastname: Berger-Wolf
authors.forename: Ashfaq A
authors.initials: AA
authors.lastname: Khokhar
authors.forename: Isabel C
authors.initials: IC
authors.lastname: Caballero
authors.forename: Mary V
authors.initials: MV
authors.lastname: Ashley
authors.forename: Wanpracha
authors.initials: W
authors.lastname: Chaovalitwongse
authors.forename: Chun-An
authors.initials: CA
authors.lastname: Chou
authors.forename: Bhaskar
authors.initials: B
authors.lastname: Dasgupta
mesh_terms: D000465:Algorithms; D000483:Alleles; D000818:Animals; D019295:Computational Biology; D030541:Databases, Genetic; D005260:Female; D005399:Fishes / Q000235:genetics; D006135:Gryllidae / Q000235:genetics; D008297:Male; D018895:Microsatellite Repeats; D008957:Models, Genetic; D015233:Models, Statistical; D035781:Siblings; D012984:Software