title: A fast algorithm for genome-wide haplotype pattern mining.
abstract: BACKGROUND
  Identifying the genetic components of common diseases has long been an important area of research. Recently, genotyping technology has reached the level where it is cost effective to genotype single nucleotide polymorphism (SNP) markers covering the entire genome, in thousands of individuals, and analyse such data for markers associated with a diseases. The statistical power to detect association, however, is limited when markers are analysed one at a time. This can be alleviated by considering multiple markers simultaneously. The Haplotype Pattern Mining (HPM) method is a machine learning approach to do exactly this.
  
  
  RESULTS
  We present a new, faster algorithm for the HPM method. The new approach use patterns of haplotype diversity in the genome: locally in the genome, the number of observed haplotypes is much smaller than the total number of possible haplotypes. We show that the new approach speeds up the HPM method with a factor of 2 on a genome-wide dataset with 5009 individuals typed in 491208 markers using default parameters and more if the pattern length is increased.
  
  
  CONCLUSIONS
  The new algorithm speeds up the HPM method and we show that it is feasible to apply HPM to whole genome association mapping with thousands of individuals and hundreds of thousands of markers.
authors.affiliation: Bioinformatics Research Center, University of Aarhus, Denmark. besen@birc.au.dk
authors.forename: Søren
authors.initials: S
authors.lastname: Besenbacher
authors.forename: Christian N S
authors.initials: CN
authors.lastname: Pedersen
authors.forename: Thomas
authors.initials: T
authors.lastname: Mailund
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D030541:Databases, Genetic; D005819:Genetic Markers; D020022:Genetic Predisposition to Disease; D014644:Genetic Variation; D015894:Genome, Human; D006239:Haplotypes / Q000235:genetics*; D006801:Humans; D020641:Polymorphism, Single Nucleotide
chemical_list: D005819:Genetic Markers