Limits...
ISHAPE: new rapid and accurate software for haplotyping.

Delaneau O, Coulonges C, Boelle PY, Nelson G, Spadoni JL, Zagury JF - BMC Bioinformatics (2007)

Bottom Line: 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.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.

View Article: PubMed Central - HTML - PubMed

Affiliation: Chaire de Bioinformatique, Conservatoire National des Arts et Métiers, Paris, France. olivier.delaneau@gmail.com <olivier.delaneau@gmail.com>

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.

Conclusion: 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.

Show MeSH
A schematic representation of the algorithm : (I) Partition strategy of the SNPs into segments thank's to the multiallelic IEM, with a new segment creation at each orphan haplotype (see text). (II) IEM-bootstrap-GS algorithm to obtain reliable haplotypes for each segment. (III) Ligation of the haplotyped segments with the same multiallelic IEM-bootstrap-GS to obtain reliable results on all the genotype dataset.
© Copyright Policy - open-access
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC1919397&req=5

Figure 1: A schematic representation of the algorithm : (I) Partition strategy of the SNPs into segments thank's to the multiallelic IEM, with a new segment creation at each orphan haplotype (see text). (II) IEM-bootstrap-GS algorithm to obtain reliable haplotypes for each segment. (III) Ligation of the haplotyped segments with the same multiallelic IEM-bootstrap-GS to obtain reliable results on all the genotype dataset.

Mentions: The two first improvements (IEM and bootstrap) are combined to generate a set of candidate haplotypes of reasonable size very rapidly, and then the third improvement is used to produce an optimal solution from the previously defined set of possible solutions. In case of larger datasets, we have adapted a new partition-ligation strategy in which the segments which have been haplotyped according to our algorithm (IEM bootstrap followed by a pseudo Gibbs sampler) are in turn treated as simple loci with the same multiallelic IEM, bootstrap and pseudo Gibbs sampler approach (Figure 1).


ISHAPE: new rapid and accurate software for haplotyping.

Delaneau O, Coulonges C, Boelle PY, Nelson G, Spadoni JL, Zagury JF - BMC Bioinformatics (2007)

A schematic representation of the algorithm : (I) Partition strategy of the SNPs into segments thank's to the multiallelic IEM, with a new segment creation at each orphan haplotype (see text). (II) IEM-bootstrap-GS algorithm to obtain reliable haplotypes for each segment. (III) Ligation of the haplotyped segments with the same multiallelic IEM-bootstrap-GS to obtain reliable results on all the genotype dataset.
© Copyright Policy - open-access
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC1919397&req=5

Figure 1: A schematic representation of the algorithm : (I) Partition strategy of the SNPs into segments thank's to the multiallelic IEM, with a new segment creation at each orphan haplotype (see text). (II) IEM-bootstrap-GS algorithm to obtain reliable haplotypes for each segment. (III) Ligation of the haplotyped segments with the same multiallelic IEM-bootstrap-GS to obtain reliable results on all the genotype dataset.
Mentions: The two first improvements (IEM and bootstrap) are combined to generate a set of candidate haplotypes of reasonable size very rapidly, and then the third improvement is used to produce an optimal solution from the previously defined set of possible solutions. In case of larger datasets, we have adapted a new partition-ligation strategy in which the segments which have been haplotyped according to our algorithm (IEM bootstrap followed by a pseudo Gibbs sampler) are in turn treated as simple loci with the same multiallelic IEM, bootstrap and pseudo Gibbs sampler approach (Figure 1).

Bottom Line: 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.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.

View Article: PubMed Central - HTML - PubMed

Affiliation: Chaire de Bioinformatique, Conservatoire National des Arts et Métiers, Paris, France. olivier.delaneau@gmail.com <olivier.delaneau@gmail.com>

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.

Conclusion: 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.

Show MeSH