SDhaP: Haplotype Assembly for Diploids and Polyploids Via Semi-Definite Programming

Simple item page
dc.contributor.utaustinauthorDas, Shreepriyaen_US
dc.contributor.utaustinauthorVikalo, Harisen_US
dc.creatorDas, Shreepriyaen_US
dc.creatorVikalo, Harisen_US
dc.date.accessioned2016-10-28T19:53:30Z
dc.date.available2016-10-28T19:53:30Z
dc.date.issued2015-04en_US
dc.description.abstractThe goal of haplotype assembly is to infer haplotypes of an individual from a mixture of sequenced chromosome fragments. Limited lengths of paired-end sequencing reads and inserts render haplotype assembly computationally challenging; in fact, most of the problem formulations are known to be NP-hard. Dimensions (and, therefore, difficulty) of the haplotype assembly problems keep increasing as the sequencing technology advances and the length of reads and inserts grow. The computational challenges are even more pronounced in the case of polyploid haplotypes, whose assembly is considerably more difficult than in the case of diploids. Fast, accurate, and scalable methods for haplotype assembly of diploid and polyploid organisms are needed. Results: We develop a novel framework for diploid/polyploid haplotype assembly from high-throughput sequencing data. The method formulates the haplotype assembly problem as a semi-definite program and exploits its special structure - namely, the low rank of the underlying solution - to solve it rapidly and with high accuracy. The developed framework is applicable to both diploid and polyploid species. The code for SDhaP is freely available at https://sourceforge.net/projects/sdhap. Conclusion: Extensive benchmarking tests on both real and simulated data show that the proposed algorithms outperform several well-known haplotype assembly methods in terms of either accuracy or speed or both. Useful recommendations for coverages needed to achieve near-optimal solutions are also provided.en_US
dc.description.departmentElectrical and Computer Engineeringen_US
dc.description.sponsorshipNational Science Foundation CCF-1320273en_US
dc.identifierdoi:10.15781/T2XK84T0R
dc.identifier.citationDas, Shreepriya, and Haris Vikalo. "SDhaP: haplotype assembly for diploids and polyploids via semi-definite programming." BMC genomics, Vol. 16, No. 1 (Apr., 2015): 1.en_US
dc.identifier.doi10.1186/s12864-015-1408-5en_US
dc.identifier.issn1471-2164en_US
dc.identifier.urihttp://hdl.handle.net/2152/43347
dc.language.isoEnglishen_US
dc.relation.ispartofen_US
dc.relation.ispartofserialBMC Genomicsen_US
dc.rightsAdministrative deposit of works to Texas ScholarWorks: This works author(s) is or was a University faculty member, student or staff member; this article is already available through open access or the publisher allows a PDF version of the article to be freely posted online. The library makes the deposit as a matter of fair use (for scholarly, educational, and research purposes), and to preserve the work and further secure public access to the works of the University.en_US
dc.rights.restrictionOpenen_US
dc.subjecthaplotype assemblyen_US
dc.subjectsemi-definite programmingen_US
dc.subjectdiploiden_US
dc.subjectpolyploiden_US
dc.subjectgenome sequence dataen_US
dc.subjectgrothendiecks inequalityen_US
dc.subjectreconstructionen_US
dc.subjectalgorithmsen_US
dc.subjectcuten_US
dc.subjectbiotechnology & applied microbiologyen_US
dc.subjectgenetics & heredityen_US
dc.titleSDhaP: Haplotype Assembly for Diploids and Polyploids Via Semi-Definite Programmingen_US
dc.typeArticleen_US

Access full-text files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
2015_04_Das.pdf
Size:
1.56 MB
Format:
Adobe Portable Document Format
Download

License bundle

Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.65 KB
Format:
Plain Text
Description:
Download

Collections

UT Faculty/Researcher Works