title: ISHAPE: new rapid and accurate software for haplotyping.
abstract: BACKGROUND
  We have developed a new haplotyping program based on the combination of an iterative multiallelic EM algorithm (IEM), bootstrap resampling and a pseudo Gibbs sampler. The use of the IEM-bootstrap procedure considerably reduces the space of possible haplotype configurations to be explored, greatly reducing computation time, while the adaptation of the Gibbs sampler with a recombination model on this restricted space maintains high accuracy. On large SNP datasets (>30 SNPs), we used a segmented approach based on a specific partition-ligation strategy. We compared this software, Ishape (Iterative Segmented HAPlotyping by Em), with reference programs such as Phase, Fastphase, and PL-EM. Analogously with Phase, there are 2 versions of Ishape: Ishape1 which uses a simple coalescence model for the pseudo Gibbs sampler step, and Ishape2 which uses a recombination model instead.
  
  
  RESULTS
  We tested the program on 2 types of real SNP datasets derived from Hapmap: adjacent SNPs (high LD) and SNPs spaced by 5 Kb (lower level of LD). In both cases, we tested 100 replicates for each size: 10, 20, 30, 40, 50, 60, and 80 SNPs. For adjacent SNPs Ishape2 is superior to the other software both in terms of speed and accuracy. For SNPs spaced by 5 Kb, Ishape2 yields similar results to Phase2.1 in terms of accuracy, and both outperform the other software. In terms of speed, Ishape2 runs about 4 times faster than Phase2.1 with 10 SNPs, and about 10 times faster with 80 SNPs. For the case of 5kb-spaced SNPs, Fastphase may run faster with more than 100 SNPs.
  
  
  CONCLUSIONS
  These results show that the Ishape heuristic approach for haplotyping is very competitive in terms of accuracy and speed and deserves to be evaluated extensively for possible future widespread use.
authors.affiliation: Chaire de Bioinformatique, Conservatoire National des Arts et Métiers, Paris, France. olivier.delaneau@gmail.com <olivier.delaneau@gmail.com>
authors.forename: Olivier
authors.initials: O
authors.lastname: Delaneau
authors.forename: Cédric
authors.initials: C
authors.lastname: Coulonges
authors.forename: Pierre-Yves
authors.initials: PY
authors.lastname: Boelle
authors.forename: George
authors.initials: G
authors.lastname: Nelson
authors.forename: Jean-Louis
authors.initials: JL
authors.lastname: Spadoni
authors.forename: Jean-François
authors.initials: JF
authors.lastname: Zagury
mesh_terms: D000465:Algorithms; D001483:Base Sequence; D004252:DNA Mutational Analysis / Q000379:methods*; D006239:Haplotypes / Q000235:genetics*; D008969:Molecular Sequence Data; D020641:Polymorphism, Single Nucleotide / Q000235:genetics*; D015203:Reproducibility of Results; D012680:Sensitivity and Specificity; D017422:Sequence Analysis, DNA / Q000379:methods*; D012984:Software