UNLABELLED: PRIMUS is a pedigree reconstruction algorithm that uses estimates of genome-wide identity by descent to reconstruct pedigrees consistent with observed genetic data. However, when genetic data for individuals within a pedigree are missing, often multiple pedigrees can be reconstructed that fit the data. We report a major expansion of PRIMUS that uses mitochondrial (mtDNA) and non-recombining Y chromosome (NRY) haplotypes to eliminate many pedigree structures that are inconsistent with the genetic data. We demonstrate that discordances in mtDNA and NRY haplotypes substantially reduce the number of potential pedigrees, and often lead to the identification of the correct pedigree. AVAILABILITY AND IMPLEMENTATION: We have implemented PRIMUS updates in PERL and it is available at primus.gs.washington.edu.