WhatsHap: Haplotype Assembly for Future-Generation Sequencing Reads

M. Patterson, T. Marschall, N. Pisanti, L.J.J. van Iersel, L. Stougie, G.W. Klau, A. Schoenhuth

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

The human genome is diploid, that is each of its chromosomes comes in two copies. This requires to phase the single nucleotide polymorphisms (SNPs), that is, to assign them to the two copies, beyond just detecting them. The resulting haplotypes, lists of SNPs belonging to each copy, are crucial for downstream analyses in population genetics. Currently, statistical approaches, which avoid making use of direct read information, constitute the state-of-the-art. Haplotype assembly, which addresses phasing directly from sequencing reads, suffers from the fact that sequencing reads of the current generation are too short to serve the purposes of genome-wide phasing. Future sequencing technologies, however, bear the promise to generate reads of lengths and error rates that allow to bridge all SNP positions in the genome at sufficient amounts of SNPs per read. Existing haplotype assembly approaches, however, profit precisely, in terms of computational complexity, from the limited length of current-generation reads, because their runtime is usually exponential in the number of SNPs per sequencing read. This implies that such approaches will not be able to exploit the benefits of long enough, future-generation reads. Here, we suggest WhatsHap, a novel dynamic programming approach to haplotype assembly. It is the first approach that yields provably optimal solutions to the weighted minimum error correction (wMEC) problem in runtime linear in the number of SNPs per sequencing read, making it suitable for future-generation reads. WhatsHap is a fixed parameter tractable (FPT) approach with coverage as the parameter. We demonstrate that WhatsHap can handle datasets of coverage up to 20x, processing chromosomes on standard workstations in only 1-2 hours. Our simulation study shows that the quality of haplotypes assembled by WhatsHap significantly improves with increasing read length, both in terms of genome coverage as well as in terms of switch errors. The switch error rates we achieve in our simulations are superior to those obtained by state-of-the-art statistical phasers. © 2014 Springer International Publishing Switzerland.

Fingerprint

Haplotype
Single nucleotide Polymorphism
Nucleotides
Polymorphism
Sequencing
Genome
Genes
Coverage
Chromosomes
Chromosome
Error Rate
Switch
Switches
Population Genetics
Error correction
Error Correction
Dynamic programming
Dynamic Programming
Profit
Assign

Bibliographical note

Proceedings title: Research in Computational Molecular Biology. 18th International Conference on Research in Computational Molecular Biology (RECOMB)
Publisher: Springer
Place of publication: Berlin
Editors: R. Sharan

Cite this

Patterson, M., Marschall, T., Pisanti, N., van Iersel, L. J. J., Stougie, L., Klau, G. W., & Schoenhuth, A. (2014). WhatsHap: Haplotype Assembly for Future-Generation Sequencing Reads. Lecture Notes in Computer Science, 8394, 237-249. https://doi.org/10.1007/978-3-319-05269-4_19
Patterson, M. ; Marschall, T. ; Pisanti, N. ; van Iersel, L.J.J. ; Stougie, L. ; Klau, G.W. ; Schoenhuth, A. / WhatsHap: Haplotype Assembly for Future-Generation Sequencing Reads. In: Lecture Notes in Computer Science. 2014 ; Vol. 8394. pp. 237-249.
@article{dbe3870fa6bd44a4bb03a7709f0335e7,
title = "WhatsHap: Haplotype Assembly for Future-Generation Sequencing Reads",
abstract = "The human genome is diploid, that is each of its chromosomes comes in two copies. This requires to phase the single nucleotide polymorphisms (SNPs), that is, to assign them to the two copies, beyond just detecting them. The resulting haplotypes, lists of SNPs belonging to each copy, are crucial for downstream analyses in population genetics. Currently, statistical approaches, which avoid making use of direct read information, constitute the state-of-the-art. Haplotype assembly, which addresses phasing directly from sequencing reads, suffers from the fact that sequencing reads of the current generation are too short to serve the purposes of genome-wide phasing. Future sequencing technologies, however, bear the promise to generate reads of lengths and error rates that allow to bridge all SNP positions in the genome at sufficient amounts of SNPs per read. Existing haplotype assembly approaches, however, profit precisely, in terms of computational complexity, from the limited length of current-generation reads, because their runtime is usually exponential in the number of SNPs per sequencing read. This implies that such approaches will not be able to exploit the benefits of long enough, future-generation reads. Here, we suggest WhatsHap, a novel dynamic programming approach to haplotype assembly. It is the first approach that yields provably optimal solutions to the weighted minimum error correction (wMEC) problem in runtime linear in the number of SNPs per sequencing read, making it suitable for future-generation reads. WhatsHap is a fixed parameter tractable (FPT) approach with coverage as the parameter. We demonstrate that WhatsHap can handle datasets of coverage up to 20x, processing chromosomes on standard workstations in only 1-2 hours. Our simulation study shows that the quality of haplotypes assembled by WhatsHap significantly improves with increasing read length, both in terms of genome coverage as well as in terms of switch errors. The switch error rates we achieve in our simulations are superior to those obtained by state-of-the-art statistical phasers. {\circledC} 2014 Springer International Publishing Switzerland.",
author = "M. Patterson and T. Marschall and N. Pisanti and {van Iersel}, L.J.J. and L. Stougie and G.W. Klau and A. Schoenhuth",
note = "Proceedings title: Research in Computational Molecular Biology. 18th International Conference on Research in Computational Molecular Biology (RECOMB) Publisher: Springer Place of publication: Berlin Editors: R. Sharan",
year = "2014",
doi = "10.1007/978-3-319-05269-4_19",
language = "English",
volume = "8394",
pages = "237--249",
journal = "Lecture Notes in Computer Science",
issn = "0302-9743",
publisher = "Springer Verlag",

}

Patterson, M, Marschall, T, Pisanti, N, van Iersel, LJJ, Stougie, L, Klau, GW & Schoenhuth, A 2014, 'WhatsHap: Haplotype Assembly for Future-Generation Sequencing Reads', Lecture Notes in Computer Science, vol. 8394, pp. 237-249. https://doi.org/10.1007/978-3-319-05269-4_19

WhatsHap: Haplotype Assembly for Future-Generation Sequencing Reads. / Patterson, M.; Marschall, T.; Pisanti, N.; van Iersel, L.J.J.; Stougie, L.; Klau, G.W.; Schoenhuth, A.

In: Lecture Notes in Computer Science, Vol. 8394, 2014, p. 237-249.

Research output: Contribution to JournalArticleAcademicpeer-review

TY - JOUR

T1 - WhatsHap: Haplotype Assembly for Future-Generation Sequencing Reads

AU - Patterson, M.

AU - Marschall, T.

AU - Pisanti, N.

AU - van Iersel, L.J.J.

AU - Stougie, L.

AU - Klau, G.W.

AU - Schoenhuth, A.

N1 - Proceedings title: Research in Computational Molecular Biology. 18th International Conference on Research in Computational Molecular Biology (RECOMB) Publisher: Springer Place of publication: Berlin Editors: R. Sharan

PY - 2014

Y1 - 2014

N2 - The human genome is diploid, that is each of its chromosomes comes in two copies. This requires to phase the single nucleotide polymorphisms (SNPs), that is, to assign them to the two copies, beyond just detecting them. The resulting haplotypes, lists of SNPs belonging to each copy, are crucial for downstream analyses in population genetics. Currently, statistical approaches, which avoid making use of direct read information, constitute the state-of-the-art. Haplotype assembly, which addresses phasing directly from sequencing reads, suffers from the fact that sequencing reads of the current generation are too short to serve the purposes of genome-wide phasing. Future sequencing technologies, however, bear the promise to generate reads of lengths and error rates that allow to bridge all SNP positions in the genome at sufficient amounts of SNPs per read. Existing haplotype assembly approaches, however, profit precisely, in terms of computational complexity, from the limited length of current-generation reads, because their runtime is usually exponential in the number of SNPs per sequencing read. This implies that such approaches will not be able to exploit the benefits of long enough, future-generation reads. Here, we suggest WhatsHap, a novel dynamic programming approach to haplotype assembly. It is the first approach that yields provably optimal solutions to the weighted minimum error correction (wMEC) problem in runtime linear in the number of SNPs per sequencing read, making it suitable for future-generation reads. WhatsHap is a fixed parameter tractable (FPT) approach with coverage as the parameter. We demonstrate that WhatsHap can handle datasets of coverage up to 20x, processing chromosomes on standard workstations in only 1-2 hours. Our simulation study shows that the quality of haplotypes assembled by WhatsHap significantly improves with increasing read length, both in terms of genome coverage as well as in terms of switch errors. The switch error rates we achieve in our simulations are superior to those obtained by state-of-the-art statistical phasers. © 2014 Springer International Publishing Switzerland.

AB - The human genome is diploid, that is each of its chromosomes comes in two copies. This requires to phase the single nucleotide polymorphisms (SNPs), that is, to assign them to the two copies, beyond just detecting them. The resulting haplotypes, lists of SNPs belonging to each copy, are crucial for downstream analyses in population genetics. Currently, statistical approaches, which avoid making use of direct read information, constitute the state-of-the-art. Haplotype assembly, which addresses phasing directly from sequencing reads, suffers from the fact that sequencing reads of the current generation are too short to serve the purposes of genome-wide phasing. Future sequencing technologies, however, bear the promise to generate reads of lengths and error rates that allow to bridge all SNP positions in the genome at sufficient amounts of SNPs per read. Existing haplotype assembly approaches, however, profit precisely, in terms of computational complexity, from the limited length of current-generation reads, because their runtime is usually exponential in the number of SNPs per sequencing read. This implies that such approaches will not be able to exploit the benefits of long enough, future-generation reads. Here, we suggest WhatsHap, a novel dynamic programming approach to haplotype assembly. It is the first approach that yields provably optimal solutions to the weighted minimum error correction (wMEC) problem in runtime linear in the number of SNPs per sequencing read, making it suitable for future-generation reads. WhatsHap is a fixed parameter tractable (FPT) approach with coverage as the parameter. We demonstrate that WhatsHap can handle datasets of coverage up to 20x, processing chromosomes on standard workstations in only 1-2 hours. Our simulation study shows that the quality of haplotypes assembled by WhatsHap significantly improves with increasing read length, both in terms of genome coverage as well as in terms of switch errors. The switch error rates we achieve in our simulations are superior to those obtained by state-of-the-art statistical phasers. © 2014 Springer International Publishing Switzerland.

U2 - 10.1007/978-3-319-05269-4_19

DO - 10.1007/978-3-319-05269-4_19

M3 - Article

VL - 8394

SP - 237

EP - 249

JO - Lecture Notes in Computer Science

T2 - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

SN - 0302-9743

ER -