Automatic selection of loop breakers for genetic linkage analysis

Abstract

Pedigree loops pose a difficult computational challenge in genetic linkage analysis. The most popular linkage analysis package, LINKAGE, uses an algorithm that converts a looped pedigree into a loopless pedigree, which is traversed many times. The conversion is controlled by user selection of individuals to act as loop breakers. The selection of loop breakers has significant impact on the running time of the subsequent linkage analysis. We have automated the process of selecting loop breakers, implemented a hybrid algorithm for it in the FASTLINK version of LINKAGE, and tested it on many real pedigrees with excellent performance. We point out that there is no need to break each loop by a distinct individual because, with minor modification to the algorithms in LINKAGE/FASTLINK, a single individual that participates in multiple marriages can serve as a loop breaker for several loops. Our algorithm for finding loop breakers, called LOOPBREAKER, is a combination of: (1) a new algorithm that is guaranteed to be optimal in the special case of pedigrees with no multiple marriages and (2) an adaptation of a known algorithm for breaking loops in general graphs. The contribution of this work is the adaptation of abstract methods from computer science to a challenging problem in genetics.