Combinatorial reconstruction of half-sibling groups from microsatellite data.
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.
Sheikh
Saad I
SI
Department of Computer Science, University of Illinois at Chicago, 851 S. Morgan St (M/C 152), Chicago, IL 60607, USA. saad@saadsheikh.com
Berger-Wolf
Tanya Y
TY
Khokhar
Ashfaq A
AA
Caballero
Isabel C
IC
Ashley
Mary V
MV
Chaovalitwongse
Wanpracha
W
Chou
Chun-An
CA
Dasgupta
Bhaskar
B
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