• Running Environment (for all programs): 1GB RAM, LINUX Red Hat OS, 2CPU PENTIUM4 XEON 2.4 GHZ.

Experiment A: (Simulation Study)

This experiment tested our haplotyping algorithm on a complex pedigree of moderate size (Figure 2 in (Lin 1996)). So far, only an approximate haplotype analysis was possible for this pedigree. We simulated a random haplotype configuration for this pedigree using the simulation guidelines described by Lin and Speed (1997).  This pedigree consists of 27 individuals and is highly inbred. All individuals, except those in the first two generations, are typed at 10 polymorphic markers, each with 5 alleles of equal frequencies.  The recombination fraction between each pair of consecutive markers was set to 0.5.
 

Experiment C: (Testing Accuracy)

This experiment tested the accuracy of SimWalk2 (Sobel and Lange, 1996), a state of the art program that uses MCMC.  We tested 75 data sets consisting of 15 to 50 individuals and 1 to 13 markers. As can be seen from the table below, SimWalk2 found a maximum likelihood assignment in 45 out of the 75 data sets.
 
 

Experiment D: (Published Disease Data)

We analyzed two published data sets:

• A data set from a study of the Krabbe disease by Oehlman et al. (1993).  This data set consists of 9 individuals typed at 8 polymorphic markers.

• A data set from a study of the Episodic Ataxia by Litt et al. (1994).  This data set consists of 29 indiviudals, which are all typed at 9 polymorphic markers except for the first two generation founders.

Experiment E: (Stochastic Algorithms)    Detailed Results.

This experiment compared the performance of different stochastic-greedy algorithms. Each of the stochastic algorithms was run for 1000 iterations after the reduction rules have been applied. The graphs used were created from simulated pedigree data.
 

Experiment F: (Total Run Time)           Detailed Results.

This experiment compared the run time of likelihood computation with the new optimization algorithm for determining an elimination order (v1.4) to the run time with the previous optimization algorithm (v1.3).  The total run time includes both optimization time and inference time.  We tested 50 randomly simulated data sets, chosen so that the run times on the new version is above 10 seconds and below 10 hours.
 
 

Experiment G: (Benchmarks)               Detailed Results.

This experiment tested the performance of the three stochastic-greedy algorithms (Min-Weight, Min-Fill and Weighted Min-Fill), on eight known benchmakrs for Bayesian networks inference.  The stochastic algorithms are run after the reduction rules have been applied.  For each benchmark, we compare between the elimination cost found by Superlink, the elimination cost found by Hugin6.1 (Andersen et al., 1989; Hugin, 2002) and the best known elimination cost.
 

Experiment H: (Reduction Rules)           Detailed Results.

This experiment tested the gain due to the reduction rules presented in Eijkhof et al. (2002).  The data sets used are 100 graphs created from simulated pedigree data.
 

References:

• Lin S. "Multipoint linkage analysis via Metropolis jumping kernels." Biometrics (1996): 52:299-309.
• Lin S. and Speed T. P. "An algorithm for haplotype analysis." J. Comput. Biol. (1997): 4:535-546.
• Sobel E and Lange K. "Descent graphs in pedigree analysis: applications to haplotyping, location scores, and marker sharing statistics."

American Journal of Human Genetic (1996): 58:1323-1337.
• Oehlman R. and Zlotogora J. and Wenger D. and Knowlton R. "Localization of the Krabbe disease gene (GALC) on chromsome 14 by multipoint linkage analysis." Am. J. Hum. Genet. (1993): 53:1250-1255.
• Litt M. and Kramer P. and Browne D. and Gancher S. and Brunt E. and Root D. and Phromchotikul T. and Dubay C. and Nutt J. "A gene for Episodic Ataxia/Myokymia maps to chromosome." Am. J. Hum. Genet. (1994): 55:702-709.
• Andersen S. K. and Olesen K. G. and Jensen F. V. and Jensen F. "HUGIN - a shell for building Bayesian belief universes for expert systems." Proc. of the 11th International Joint Conference on Artificial Intelligence (IJCAI) (1989): 2:1080-1085.
• Hugin: The API reference manual version 5.4.  February, 2002.
• Frank van den Eijkhof, Hans L. Bodlaender, Arie M.C.A. Koster. "Safe reduction rules for weighted treewidth." Konrad-Zuse-Zentrum für Informationstechnik Berlin, ZIB PaperWeb Reports / Preprints 2002.