Genetic linkage analysis is a challenging application which requires Bayesian networks consisting of thousands of vertices. Consequently, computing the likelihood of data, which is needed for learning linkage parameters, using exact inference procedures calls for an extremely efficient implementation that carefully optimizes the order of conditioning and summation operations. In this paper we present the use of stochastic greedy algorithms for optimizing this order. Our algorithm has been incorporated into the newest version of superlink, which is currently the fastest genetic linkage program for exact likelihood computations in general pedigrees. We demonstrate an order of magnitude improvement in run times of likelihood computations using our new optimization algorithm, and hence enlarge the class of problems that can be handled effectively by exact computations.

Abstract Motivation: Genetic linkage analysis is a useful statistical tool for mapping disease genes and for associating functionality of genes with their location on the chromosome. There is a need for a program that computes multipoint likelihood on general pedigrees with many markers that also deals with two-locus disease models. Results: In this paper we present algorithms for performing exact multipoint likelihood calculations on general pedigrees with a large number of highly polymorphic markers, taking into account a variety of disease models. We have implemented these algorithms in a new computer program called superlink which outperforms leading linkage software with regards to functionality, speed, memory requirements and extensibility. Availability: superlink is available at http://bioinfo.cs.technion.ac.il/superlink Contact: [email protected]@cs.technion.ac.il Keywords: Bayesian networks; Fastlink; Genehunter; linkage analysis; Vitesse.