COMBINATORIAL RECONSTRUCTION OF HALF-SIBLINGGROUPS FROM MICROSATELLITE DATA

摘要

While full-sibling group reconstruction from microsatellite data is a well-studied prob-lem, 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 solu-tions for this formulation and develop heuristics. Using biological and synthetic datasetswe present experimental results and compare them with the leading alternative software