  Reconstruction of family trees, or pedigree reconstruction, for a group of
individuals is a fundamental problem in genetics. The problem is known to be
NP-hard even for datasets known to only contain siblings. Some recent methods
have been developed to accurately and efficiently reconstruct pedigrees. These
methods, however, still consider relatively simple pedigrees, for example, they
are not able to handle half-sibling situations where a pair of individuals only
share one parent. In this work, we propose an efficient method, IPED2, based on
our previous work, which specifically targets reconstruction of complicated
pedigrees that include half-siblings. We note that the presence of
half-siblings makes the reconstruction problem significantly more challenging
which is why previous methods exclude the possibility of half-siblings. We
proposed a novel model as well as an efficient graph algorithm and experiments
show that our algorithm achieves relatively accurate reconstruction. To our
knowledge, this is the first method that is able to handle pedigree
reconstruction based on genotype data only when half-sibling exists in any
generation of the pedigree.
