ABSTRACT
Haplotype data is valuable in mapping disease-susceptibility genes in the study of Mendelian and complex diseases. We present algorithms for inferring a most likely haplotype configuration for general pedigrees, implemented in the newest version of the genetic linkage analysis system SUPERLINK. In SUPERLINK, genetic linkage analysis problems are represented internally using Bayesian networks. The use of Bayesian networks enables efficient maximum likelihood haplotyping for more complex pedigrees than was previously possible. Furthermore, to support efficient haplotyping for larger pedigrees, we have also incorporated a novel algorithm for determining a better elimination order for the variables of the Bayesian network. The presented optimization algorithm also improves likelihood computations. We present experimental results for the new algorithms on a variety of real and semiartificial data sets, and use our software to evaluate MCMC approximations for haplotyping.
Subject(s)
Algorithms , Bayes Theorem , Genetic Predisposition to Disease/genetics , Haplotypes/genetics , Likelihood Functions , Pedigree , Ataxia/genetics , Chromosome Mapping/methods , Computer Simulation , Gene Frequency/genetics , Humans , Leukodystrophy, Globoid Cell/genetics , SoftwareABSTRACT
We have recently described a novel autosomal recessive disorder, lethal congenital contractural syndrome type 2 (LCCS2) (OMIM 607598), in a large Israeli Bedouin kindred. The phenotype, which is lethal in the neonatal period, is distinguished by the presence of a markedly distended urinary bladder. Association of LCCS2 to the known loci associated with arthogryposis was excluded. In the present study, we set out to determine the genetic locus harboring the gene defective in this disease. We performed genome-wide linkage analysis, demonstrating linkage to a approximately 6 cM (corresponding to approximately 7.2 Mb) homozygosity region on chromosome 12q13 between markers D12S1604 and D12S83. Based on recombination events, the interval harboring the disease-associated locus was further narrowed to a region spanning approximately 6 cM ( approximately 6.4 Mb) between D12S325 and D12S1072. Linkage of LCCS2 to that locus was established, with two significant maximum peaks at markers D12S1604 (Z(max) = 10.56 at theta = 0.01) and D12S1700 (Z(max) = 9.23 at theta = 0.00).
Subject(s)
Chromosome Mapping/methods , Chromosomes, Human, Pair 12/genetics , Contracture/genetics , Contracture/congenital , Family Health , Female , Genetic Linkage , Genome, Human , Haplotypes , Homozygote , Humans , Lod Score , Male , Microsatellite Repeats , Pedigree , SyndromeABSTRACT
Genetic linkage analysis is a challenging application which requires Bayesian networks consisting of thousands of vertices. Consequently, computing the probability of data, which is needed for learning linkage parameters, using exact computation 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 a fast 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.
