Most contemporary methods for multipoint linkage analysis are based on either the Elston-Stewart algorithm1 or the Lander-Green Hidden Markov model2 (HMM). The Elston-Stewart algorithm scales exponentially in the number of markers, whereas the Lander-Green HMM scales exponentially in the number of pedigree members. The Vitesse3 and Superlink4 software packages are based on the Elston-Stewart algorithm and, with the most recent advancements, can handle a moderate number of markers in large pedigrees. Existing multipoint linkage analysis packages based on the Lander-Green HMM, Genehunter5, Allegro6 and Merlin7, can handle arbitrarily many markers but are limited to∼ 25-bit pedigrees. The bit size of a pedigree is 2n–f–g, where n is the number of nonfounders, f is the number of founders and g is the number of ungenotyped founder couples.

We developed a new software package based on multiterminal binary decision diagrams8 (MTBDDs). This software package is the second version of our Allegro6 software package (http://www. decode. com/software/allegro) and uses an implementation of MTBDDs from the Cudd package (http://vlsi. colorado. edu/∼ fabio/CUDD). It includes all the main features of the older version: lod scores based on allele sharing models, parametric lod scores, NPL scores, haplotyping, counting of forced recombinations, pairwise IBD sharing calculations, expected crossover counts, all analysis available for the X chromosome and a multitude of scoring functions, including imprinting models and the option to specify a weight for every pair of individuals. MTBDDs offer compact storage of probability distributions through two properties: uniqueness and nonredundancy