Haplotype assembly of autotetraploid potato using integer linear programing

Enrico Siragusa, Niina Haiminen, Richard Finkers, Richard Visser, Laxmi Parida*

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

SUMMARY: Haplotype assembly of polyploids is an open issue in plant genomics. Recent experimental studies on highly heterozygous autotetraploid potato have shown that available methods do not deliver satisfying results in practice. We propose an optimal method to assemble haplotypes of highly heterozygous polyploids from Illumina short-sequencing reads. Our method is based on a generalization of the existing minimum fragment removal model to the polyploid case and on new integer linear programs to reconstruct optimal haplotypes. We validate our methods experimentally by means of a combined evaluation on simulated and experimental data based on 83 previously sequenced autotetraploid potato cultivars. Results on simulated data show that our methods produce highly accurate haplotype assemblies, while results on experimental data confirm a sensible improvement over the state of the art. AVAILABILITY AND IMPLEMENTATION: Executables for Linux at http://github.com/Computational Genomics/HaplotypeAssembler. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Original languageEnglish
Pages (from-to)3279-3286
Number of pages8
JournalBioinformatics (Oxford, England)
Volume35
Issue number18
DOIs
Publication statusPublished - 15 Sep 2019

Fingerprint

Linear Programming
Haplotype
Potato
Solanum tuberosum
Haplotypes
Polyploidy
Integer
Bioinformatics
Genomics
Availability
Experimental Data
Integer Program
Linux
Computational Biology
Linear Program
Sequencing
Experimental Study
Fragment
Evaluation

Cite this

Siragusa, Enrico ; Haiminen, Niina ; Finkers, Richard ; Visser, Richard ; Parida, Laxmi. / Haplotype assembly of autotetraploid potato using integer linear programing. In: Bioinformatics (Oxford, England). 2019 ; Vol. 35, No. 18. pp. 3279-3286.
@article{71ba5ec829d842e2be5b4d343a6c5c4e,
title = "Haplotype assembly of autotetraploid potato using integer linear programing",
abstract = "SUMMARY: Haplotype assembly of polyploids is an open issue in plant genomics. Recent experimental studies on highly heterozygous autotetraploid potato have shown that available methods do not deliver satisfying results in practice. We propose an optimal method to assemble haplotypes of highly heterozygous polyploids from Illumina short-sequencing reads. Our method is based on a generalization of the existing minimum fragment removal model to the polyploid case and on new integer linear programs to reconstruct optimal haplotypes. We validate our methods experimentally by means of a combined evaluation on simulated and experimental data based on 83 previously sequenced autotetraploid potato cultivars. Results on simulated data show that our methods produce highly accurate haplotype assemblies, while results on experimental data confirm a sensible improvement over the state of the art. AVAILABILITY AND IMPLEMENTATION: Executables for Linux at http://github.com/Computational Genomics/HaplotypeAssembler. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.",
author = "Enrico Siragusa and Niina Haiminen and Richard Finkers and Richard Visser and Laxmi Parida",
year = "2019",
month = "9",
day = "15",
doi = "10.1093/bioinformatics/btz060",
language = "English",
volume = "35",
pages = "3279--3286",
journal = "Bioinformatics",
issn = "1367-4803",
publisher = "Oxford University Press",
number = "18",

}

Haplotype assembly of autotetraploid potato using integer linear programing. / Siragusa, Enrico; Haiminen, Niina; Finkers, Richard; Visser, Richard; Parida, Laxmi.

In: Bioinformatics (Oxford, England), Vol. 35, No. 18, 15.09.2019, p. 3279-3286.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Haplotype assembly of autotetraploid potato using integer linear programing

AU - Siragusa, Enrico

AU - Haiminen, Niina

AU - Finkers, Richard

AU - Visser, Richard

AU - Parida, Laxmi

PY - 2019/9/15

Y1 - 2019/9/15

N2 - SUMMARY: Haplotype assembly of polyploids is an open issue in plant genomics. Recent experimental studies on highly heterozygous autotetraploid potato have shown that available methods do not deliver satisfying results in practice. We propose an optimal method to assemble haplotypes of highly heterozygous polyploids from Illumina short-sequencing reads. Our method is based on a generalization of the existing minimum fragment removal model to the polyploid case and on new integer linear programs to reconstruct optimal haplotypes. We validate our methods experimentally by means of a combined evaluation on simulated and experimental data based on 83 previously sequenced autotetraploid potato cultivars. Results on simulated data show that our methods produce highly accurate haplotype assemblies, while results on experimental data confirm a sensible improvement over the state of the art. AVAILABILITY AND IMPLEMENTATION: Executables for Linux at http://github.com/Computational Genomics/HaplotypeAssembler. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

AB - SUMMARY: Haplotype assembly of polyploids is an open issue in plant genomics. Recent experimental studies on highly heterozygous autotetraploid potato have shown that available methods do not deliver satisfying results in practice. We propose an optimal method to assemble haplotypes of highly heterozygous polyploids from Illumina short-sequencing reads. Our method is based on a generalization of the existing minimum fragment removal model to the polyploid case and on new integer linear programs to reconstruct optimal haplotypes. We validate our methods experimentally by means of a combined evaluation on simulated and experimental data based on 83 previously sequenced autotetraploid potato cultivars. Results on simulated data show that our methods produce highly accurate haplotype assemblies, while results on experimental data confirm a sensible improvement over the state of the art. AVAILABILITY AND IMPLEMENTATION: Executables for Linux at http://github.com/Computational Genomics/HaplotypeAssembler. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

U2 - 10.1093/bioinformatics/btz060

DO - 10.1093/bioinformatics/btz060

M3 - Article

VL - 35

SP - 3279

EP - 3286

JO - Bioinformatics

JF - Bioinformatics

SN - 1367-4803

IS - 18

ER -