title: Selecting loop breakers in general pedigrees.
abstract: 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.
authors.affiliation: Station d'Amélioration Génétique des Animaux, Institut National de la Recherche Agronomique, Castanet-Tolosan, France. vitezica@toulouse.inra.fr
authors.forename: Zulma G
authors.initials: ZG
authors.lastname: Vitezica
authors.forename: Marcel
authors.initials: M
authors.lastname: Mongeau
authors.forename: Eduardo
authors.initials: E
authors.lastname: Manfredi
authors.forename: Jean-Michel
authors.initials: JM
authors.lastname: Elsen
mesh_terms: 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