Loading…

Sparse Tensor Decomposition for Haplotype Assembly of Diploids and Polyploids

Haplotype assembly is the task of reconstructing haplotypes of an individual from a mixture of sequenced chromosome fragments. Haplotype information enables studies of the effects of genetic variations on an organism's phenotype. Most of the mathematical formulations of haplotype assembly are k...

Full description

Saved in:
Bibliographic Details
Published in:BMC genomics 2018-03, Vol.19 (Suppl 4), p.191-191, Article 191
Main Authors: Hashemi, Abolfazl, Zhu, Banghua, Vikalo, Haris
Format: Article
Language:English
Subjects:
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c465t-8d6b169170b4c7f92428b6e8a450502fa14fe827af3b9cd69a4ad33a4b39331b3
cites cdi_FETCH-LOGICAL-c465t-8d6b169170b4c7f92428b6e8a450502fa14fe827af3b9cd69a4ad33a4b39331b3
container_end_page 191
container_issue Suppl 4
container_start_page 191
container_title BMC genomics
container_volume 19
creator Hashemi, Abolfazl
Zhu, Banghua
Vikalo, Haris
description Haplotype assembly is the task of reconstructing haplotypes of an individual from a mixture of sequenced chromosome fragments. Haplotype information enables studies of the effects of genetic variations on an organism's phenotype. Most of the mathematical formulations of haplotype assembly are known to be NP-hard and haplotype assembly becomes even more challenging as the sequencing technology advances and the length of the paired-end reads and inserts increases. Assembly of haplotypes polyploid organisms is considerably more difficult than in the case of diploids. Hence, scalable and accurate schemes with provable performance are desired for haplotype assembly of both diploid and polyploid organisms. We propose a framework that formulates haplotype assembly from sequencing data as a sparse tensor decomposition. We cast the problem as that of decomposing a tensor having special structural constraints and missing a large fraction of its entries into a product of two factors, U and [Formula: see text]; tensor [Formula: see text] reveals haplotype information while U is a sparse matrix encoding the origin of erroneous sequencing reads. An algorithm, AltHap, which reconstructs haplotypes of either diploid or polyploid organisms by iteratively solving this decomposition problem is proposed. The performance and convergence properties of AltHap are theoretically analyzed and, in doing so, guarantees on the achievable minimum error correction scores and correct phasing rate are established. The developed framework is applicable to diploid, biallelic and polyallelic polyploid species. The code for AltHap is freely available from https://github.com/realabolfazl/AltHap . AltHap was tested in a number of different scenarios and was shown to compare favorably to state-of-the-art methods in applications to haplotype assembly of diploids, and significantly outperforms existing techniques when applied to haplotype assembly of polyploids.
doi_str_mv 10.1186/s12864-018-4551-y
format article
fullrecord <record><control><sourceid>proquest_doaj_</sourceid><recordid>TN_cdi_doaj_primary_oai_doaj_org_article_b7512e637063480fae57ee0a770ce17f</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><doaj_id>oai_doaj_org_article_b7512e637063480fae57ee0a770ce17f</doaj_id><sourcerecordid>2019472235</sourcerecordid><originalsourceid>FETCH-LOGICAL-c465t-8d6b169170b4c7f92428b6e8a450502fa14fe827af3b9cd69a4ad33a4b39331b3</originalsourceid><addsrcrecordid>eNpVkctu1jAQRiME6v0B2KAs2QQ8vmeDVLVAKxWBRLu2bGdcXCVxsPNXytuTkrZqVx5_M3Ns6VTVeyCfALT8XIBqyRsCuuFCQLO8qQ6AK2goSP72Rb1fHZZyRwgoTcVetU9boVsh-EH14_dkc8H6GseScn2OPg1TKnGOaazDmlzYqU_zMmF9WgoOrl_qFOrzuKaxK7Udu_pX6pftely9C7YvePJ4HlU3375en100Vz-_X56dXjWeSzE3upMOZAuKOO5VaCmn2knUlgsiCA0WeEBNlQ3Mtb6TreW2Y8xyx1rGwLGj6nLjdsnemSnHwebFJBvN_yDlW2PzHH2PxikBFCVTRDKuSbAoFCKxShGPoMLK-rKxpp0bsPM4ztn2r6CvO2P8Y27TvRFaUSHZCvj4CMjp7w7LbIZYPPa9HTHtiqEEWq4oZWIdhW3U51RKxvD8DBDzoNRsSs2q1DwoNcu68-Hl_543nhyyfyihnak</addsrcrecordid><sourcetype>Open Website</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2019472235</pqid></control><display><type>article</type><title>Sparse Tensor Decomposition for Haplotype Assembly of Diploids and Polyploids</title><source>Publicly Available Content (ProQuest)</source><source>PubMed Central</source><creator>Hashemi, Abolfazl ; Zhu, Banghua ; Vikalo, Haris</creator><creatorcontrib>Hashemi, Abolfazl ; Zhu, Banghua ; Vikalo, Haris</creatorcontrib><description>Haplotype assembly is the task of reconstructing haplotypes of an individual from a mixture of sequenced chromosome fragments. Haplotype information enables studies of the effects of genetic variations on an organism's phenotype. Most of the mathematical formulations of haplotype assembly are known to be NP-hard and haplotype assembly becomes even more challenging as the sequencing technology advances and the length of the paired-end reads and inserts increases. Assembly of haplotypes polyploid organisms is considerably more difficult than in the case of diploids. Hence, scalable and accurate schemes with provable performance are desired for haplotype assembly of both diploid and polyploid organisms. We propose a framework that formulates haplotype assembly from sequencing data as a sparse tensor decomposition. We cast the problem as that of decomposing a tensor having special structural constraints and missing a large fraction of its entries into a product of two factors, U and [Formula: see text]; tensor [Formula: see text] reveals haplotype information while U is a sparse matrix encoding the origin of erroneous sequencing reads. An algorithm, AltHap, which reconstructs haplotypes of either diploid or polyploid organisms by iteratively solving this decomposition problem is proposed. The performance and convergence properties of AltHap are theoretically analyzed and, in doing so, guarantees on the achievable minimum error correction scores and correct phasing rate are established. The developed framework is applicable to diploid, biallelic and polyallelic polyploid species. The code for AltHap is freely available from https://github.com/realabolfazl/AltHap . AltHap was tested in a number of different scenarios and was shown to compare favorably to state-of-the-art methods in applications to haplotype assembly of diploids, and significantly outperforms existing techniques when applied to haplotype assembly of polyploids.</description><identifier>ISSN: 1471-2164</identifier><identifier>EISSN: 1471-2164</identifier><identifier>DOI: 10.1186/s12864-018-4551-y</identifier><identifier>PMID: 29589554</identifier><language>eng</language><publisher>England: BioMed Central</publisher><subject>Haplotype assembly ; Iterative algorithm ; Tensor decomposition</subject><ispartof>BMC genomics, 2018-03, Vol.19 (Suppl 4), p.191-191, Article 191</ispartof><rights>The Author(s) 2018</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c465t-8d6b169170b4c7f92428b6e8a450502fa14fe827af3b9cd69a4ad33a4b39331b3</citedby><cites>FETCH-LOGICAL-c465t-8d6b169170b4c7f92428b6e8a450502fa14fe827af3b9cd69a4ad33a4b39331b3</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktopdf>$$Uhttps://www.ncbi.nlm.nih.gov/pmc/articles/PMC5872563/pdf/$$EPDF$$P50$$Gpubmedcentral$$Hfree_for_read</linktopdf><linktohtml>$$Uhttps://www.ncbi.nlm.nih.gov/pmc/articles/PMC5872563/$$EHTML$$P50$$Gpubmedcentral$$Hfree_for_read</linktohtml><link.rule.ids>230,314,727,780,784,885,27924,27925,37013,53791,53793</link.rule.ids><backlink>$$Uhttps://www.ncbi.nlm.nih.gov/pubmed/29589554$$D View this record in MEDLINE/PubMed$$Hfree_for_read</backlink></links><search><creatorcontrib>Hashemi, Abolfazl</creatorcontrib><creatorcontrib>Zhu, Banghua</creatorcontrib><creatorcontrib>Vikalo, Haris</creatorcontrib><title>Sparse Tensor Decomposition for Haplotype Assembly of Diploids and Polyploids</title><title>BMC genomics</title><addtitle>BMC Genomics</addtitle><description>Haplotype assembly is the task of reconstructing haplotypes of an individual from a mixture of sequenced chromosome fragments. Haplotype information enables studies of the effects of genetic variations on an organism's phenotype. Most of the mathematical formulations of haplotype assembly are known to be NP-hard and haplotype assembly becomes even more challenging as the sequencing technology advances and the length of the paired-end reads and inserts increases. Assembly of haplotypes polyploid organisms is considerably more difficult than in the case of diploids. Hence, scalable and accurate schemes with provable performance are desired for haplotype assembly of both diploid and polyploid organisms. We propose a framework that formulates haplotype assembly from sequencing data as a sparse tensor decomposition. We cast the problem as that of decomposing a tensor having special structural constraints and missing a large fraction of its entries into a product of two factors, U and [Formula: see text]; tensor [Formula: see text] reveals haplotype information while U is a sparse matrix encoding the origin of erroneous sequencing reads. An algorithm, AltHap, which reconstructs haplotypes of either diploid or polyploid organisms by iteratively solving this decomposition problem is proposed. The performance and convergence properties of AltHap are theoretically analyzed and, in doing so, guarantees on the achievable minimum error correction scores and correct phasing rate are established. The developed framework is applicable to diploid, biallelic and polyallelic polyploid species. The code for AltHap is freely available from https://github.com/realabolfazl/AltHap . AltHap was tested in a number of different scenarios and was shown to compare favorably to state-of-the-art methods in applications to haplotype assembly of diploids, and significantly outperforms existing techniques when applied to haplotype assembly of polyploids.</description><subject>Haplotype assembly</subject><subject>Iterative algorithm</subject><subject>Tensor decomposition</subject><issn>1471-2164</issn><issn>1471-2164</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2018</creationdate><recordtype>article</recordtype><sourceid>DOA</sourceid><recordid>eNpVkctu1jAQRiME6v0B2KAs2QQ8vmeDVLVAKxWBRLu2bGdcXCVxsPNXytuTkrZqVx5_M3Ns6VTVeyCfALT8XIBqyRsCuuFCQLO8qQ6AK2goSP72Rb1fHZZyRwgoTcVetU9boVsh-EH14_dkc8H6GseScn2OPg1TKnGOaazDmlzYqU_zMmF9WgoOrl_qFOrzuKaxK7Udu_pX6pftely9C7YvePJ4HlU3375en100Vz-_X56dXjWeSzE3upMOZAuKOO5VaCmn2knUlgsiCA0WeEBNlQ3Mtb6TreW2Y8xyx1rGwLGj6nLjdsnemSnHwebFJBvN_yDlW2PzHH2PxikBFCVTRDKuSbAoFCKxShGPoMLK-rKxpp0bsPM4ztn2r6CvO2P8Y27TvRFaUSHZCvj4CMjp7w7LbIZYPPa9HTHtiqEEWq4oZWIdhW3U51RKxvD8DBDzoNRsSs2q1DwoNcu68-Hl_543nhyyfyihnak</recordid><startdate>20180321</startdate><enddate>20180321</enddate><creator>Hashemi, Abolfazl</creator><creator>Zhu, Banghua</creator><creator>Vikalo, Haris</creator><general>BioMed Central</general><general>BMC</general><scope>NPM</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>7X8</scope><scope>5PM</scope><scope>DOA</scope></search><sort><creationdate>20180321</creationdate><title>Sparse Tensor Decomposition for Haplotype Assembly of Diploids and Polyploids</title><author>Hashemi, Abolfazl ; Zhu, Banghua ; Vikalo, Haris</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c465t-8d6b169170b4c7f92428b6e8a450502fa14fe827af3b9cd69a4ad33a4b39331b3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2018</creationdate><topic>Haplotype assembly</topic><topic>Iterative algorithm</topic><topic>Tensor decomposition</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Hashemi, Abolfazl</creatorcontrib><creatorcontrib>Zhu, Banghua</creatorcontrib><creatorcontrib>Vikalo, Haris</creatorcontrib><collection>PubMed</collection><collection>CrossRef</collection><collection>MEDLINE - Academic</collection><collection>PubMed Central (Full Participant titles)</collection><collection>DOAJ Directory of Open Access Journals</collection><jtitle>BMC genomics</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Hashemi, Abolfazl</au><au>Zhu, Banghua</au><au>Vikalo, Haris</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Sparse Tensor Decomposition for Haplotype Assembly of Diploids and Polyploids</atitle><jtitle>BMC genomics</jtitle><addtitle>BMC Genomics</addtitle><date>2018-03-21</date><risdate>2018</risdate><volume>19</volume><issue>Suppl 4</issue><spage>191</spage><epage>191</epage><pages>191-191</pages><artnum>191</artnum><issn>1471-2164</issn><eissn>1471-2164</eissn><abstract>Haplotype assembly is the task of reconstructing haplotypes of an individual from a mixture of sequenced chromosome fragments. Haplotype information enables studies of the effects of genetic variations on an organism's phenotype. Most of the mathematical formulations of haplotype assembly are known to be NP-hard and haplotype assembly becomes even more challenging as the sequencing technology advances and the length of the paired-end reads and inserts increases. Assembly of haplotypes polyploid organisms is considerably more difficult than in the case of diploids. Hence, scalable and accurate schemes with provable performance are desired for haplotype assembly of both diploid and polyploid organisms. We propose a framework that formulates haplotype assembly from sequencing data as a sparse tensor decomposition. We cast the problem as that of decomposing a tensor having special structural constraints and missing a large fraction of its entries into a product of two factors, U and [Formula: see text]; tensor [Formula: see text] reveals haplotype information while U is a sparse matrix encoding the origin of erroneous sequencing reads. An algorithm, AltHap, which reconstructs haplotypes of either diploid or polyploid organisms by iteratively solving this decomposition problem is proposed. The performance and convergence properties of AltHap are theoretically analyzed and, in doing so, guarantees on the achievable minimum error correction scores and correct phasing rate are established. The developed framework is applicable to diploid, biallelic and polyallelic polyploid species. The code for AltHap is freely available from https://github.com/realabolfazl/AltHap . AltHap was tested in a number of different scenarios and was shown to compare favorably to state-of-the-art methods in applications to haplotype assembly of diploids, and significantly outperforms existing techniques when applied to haplotype assembly of polyploids.</abstract><cop>England</cop><pub>BioMed Central</pub><pmid>29589554</pmid><doi>10.1186/s12864-018-4551-y</doi><tpages>1</tpages><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 1471-2164
ispartof BMC genomics, 2018-03, Vol.19 (Suppl 4), p.191-191, Article 191
issn 1471-2164
1471-2164
language eng
recordid cdi_doaj_primary_oai_doaj_org_article_b7512e637063480fae57ee0a770ce17f
source Publicly Available Content (ProQuest); PubMed Central
subjects Haplotype assembly
Iterative algorithm
Tensor decomposition
title Sparse Tensor Decomposition for Haplotype Assembly of Diploids and Polyploids
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-24T01%3A45%3A43IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_doaj_&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Sparse%20Tensor%20Decomposition%20for%20Haplotype%20Assembly%20of%20Diploids%20and%20Polyploids&rft.jtitle=BMC%20genomics&rft.au=Hashemi,%20Abolfazl&rft.date=2018-03-21&rft.volume=19&rft.issue=Suppl%204&rft.spage=191&rft.epage=191&rft.pages=191-191&rft.artnum=191&rft.issn=1471-2164&rft.eissn=1471-2164&rft_id=info:doi/10.1186/s12864-018-4551-y&rft_dat=%3Cproquest_doaj_%3E2019472235%3C/proquest_doaj_%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c465t-8d6b169170b4c7f92428b6e8a450502fa14fe827af3b9cd69a4ad33a4b39331b3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2019472235&rft_id=info:pmid/29589554&rfr_iscdi=true