Half-sibling reconstruction is the task of determining maternal and paternal sibling relationships from observed genotypes of same-generation individuals in a population. Knowledge of how populations are structured allows biologists to understand mating habits of different species, how threatened a population is, and how best to protect threatened or endangered species. This thesis examines the problem of half-sibling reconstruction and explains an accurate and fast heurstic for reconstructing half-siblings. The heuristic reconstructs half-sibling relationships with high accuracy on large biological populations where existing algorithms fail due to running time constraints. In addition to identifying and discussing some of the major problems with half-sibling reconstruction, we also prove that even the task of determining whether a half-sibling reconstruction obeys genetic inheritance laws is NP-complete. Some solutions for overcoming the inherent difficulty of half-sibling reconstruction are also proposed.

Half-sibling reconstruction is the task of determining maternal and paternal sibling relationships from observed genotypes of same-generation individuals in a population. Knowledge of how populations are structured allows biologists to understand mating habits of different species, how threatened a population is, and how best to protect threatened or endangered species. This thesis examines the problem of half-sibling reconstruction and explains an accurate and fast heurstic for reconstructing half-siblings. The heuristic reconstructs half-sibling relationships with high accuracy on large biological populations where existing algorithms fail due to running time constraints. In addition to identifying and discussing some of the major problems with half-sibling reconstruction, we also prove that even the task of determining whether a half-sibling reconstruction obeys genetic inheritance laws is NP-complete. Some solutions for overcoming the inherent difficulty of half-sibling reconstruction are also proposed.