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.
Vitezica
Zulma G
ZG
Station d'Amélioration Génétique des Animaux, Institut National de la Recherche Agronomique, Castanet-Tolosan, France. vitezica@toulouse.inra.fr
Mongeau
Marcel
M
Manfredi
Eduardo
E
Elsen
Jean-Michel
JM
D000465:Algorithms; D005260:Female; D008040:Genetic Linkage; D005838:Genotype; D006801:Humans; D016013:Likelihood Functions; D008297:Male; D008957:Models, Genetic; D015233:Models, Statistical; D009679:Nuclear Family; D010375:Pedigree; D012984:Software; D013223:Statistics as Topic; D013997:Time Factors