AUTOMATIC SELECTION OF LOOP BREAKERS FOR GENETIC-LINKAGE ANALYSIS

Pedigree loops pose a difficult computational challenge in genetic lin kage analysis. The most popular linkage analysis package, LINKAGE, use s an algorithm that converts a looped pedigree into a loopless pedigre e, which is traversed many times. The conversion is controlled by user selection of individuals to act as loop breakers. The selection of lo op breakers has significant impact on the running time of the subseque nt linkage analysis. We have automated the process of selecting loop b reakers, implemented a hybrid algorithm for it in the FASTLINK version of LINKAGE, and tested it on many real pedigrees with excellent perfo rmance. We point out that there is no need to break each loop by a dis tinct individual because, with minor modification to the algorithms in LINKAGE/FASTLINK, a single individual that participates in multiple m arriages 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 kn own algorithm for breaking loops in general graphs. The contribution o f this work is the adaptation of abstract methods from computer scienc e to a challenging problem in genetics.