Selecting loop breakers in general pedigrees

The presence of loops in pedigrees poses severe computational problems in likelihood calculation that can be solved by creating an equivalent unlooped pedigree. We introduce a heuristic polynomial-time dynamic-programming algorithm, called SFH, that addresses the problem of selecting a minimal-cost set of loop breakers. We report computational experiments on simulated pedigrees with up to 1000 individuals and 361 loops, and multiple marriages. We compare the loop-breaker set selected by our method with that obtained using the software package FASTLINK 4.1P. Our approach outperforms FASTLINK 4.1P on the computational-time point of view, on the point of view of quality of the loop-breaker set obtained, and on the point of view of the size of the problem that can be addressed.