H-PoP and H-PoPG: heuristic partitioning algorithms for single individual haplotyping of polyploids

doi:10.1093/bioinformatics/btw537

	H-PoP and H-PoPG: heuristic partitioning algorithms for single individual haplotyping of polyploids
	Xie, Minzhu ; Wu, Qiong 1; Wang, Jianxin 2; Jiang, Tao 3,4,5
	2016
发表期刊	BIOINFORMATICS
ISSN	1367-4803
卷号	32 期号:24 页码:3735-3744
摘要	Motivation: Some economically important plants including wheat and cotton have more than two copies of each chromosome. With the decreasing cost and increasing read length of next-generation sequencing technologies, reconstructing the multiple haplotypes of a polyploid genome from its sequence reads becomes practical. However, the computational challenge in polyploid haplotyping is much greater than that in diploid haplotyping, and there are few related methods. Results: This article models the polyploid haplotyping problem as an optimal poly-partition problem of the reads, called the Polyploid Balanced Optimal Partition model. For the reads sequenced from a k-ploid genome, the model tries to divide the reads into k groups such that the difference between the reads of the same group is minimized while the difference between the reads of different groups is maximized. When the genotype information is available, the model is extended to the Polyploid Balanced Optimal Partition with Genotype constraint problem. These models are all NP-hard. We propose two heuristic algorithms, H-PoP and H-PoPG, based on dynamic programming and a strategy of limiting the number of intermediate solutions at each iteration, to solve the two models, respectively. Extensive experimental results on simulated and real data show that our algorithms can solve the models effectively, and are much faster and more accurate than the recent state-of-the-art polyploid haplotyping algorithms. The experiments also show that our algorithms can deal with long reads and deep read coverage effectively and accurately. Furthermore, H-PoP might be applied to help determine the ploidy of an organism. Availability and Implementation: https://github.com/MinzhuXie/H-PoPG Contact: xieminzhu@hotmail.com Supplementary information: Supplementary data are available at Bioinformatics online.
学科领域	Biochemical Research Methods ; Biotechnology & Applied Microbiology ; Computer Science, Interdisciplinary Applications ; Mathematical & Computational Biology ; Statistics & Probability
DOI	10.1093/bioinformatics/btw537
收录类别	SCI
语种	英语
WOS关键词	SNP FRAGMENTS ; ACCURATE ; DISCOVERY ; ALIGNMENT ; GENOMES
WOS研究方向	Science Citation Index Expanded (SCI-EXPANDED)
WOS记录号	WOS:000399806500006
出版者	OXFORD UNIV PRESS
文献子类	Article
出版地	OXFORD
EISSN	1460-2059
资助机构	National Natural Science Foundation of ChinaNational Natural Science Foundation of China (NSFC) [61370172, 61232001, 61420106009] ; US National Science FoundationNational Science Foundation (NSF) [DBI-1262107]
作者邮箱	xieminzhu@hotmail.com
作品OA属性	Green Published, Bronze
引用统计	被引频次：30[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://ir.ibcas.ac.cn/handle/2S10CLM1/25018
专题	系统与进化植物学国家重点实验室
作者单位	1.Hunan Normal Univ, Coll Phys & Informat Sci, Key Lab Internet Things Technol & Applicat, Changsha 410081, Hunan, Peoples R China 2.Chinese Acad Sci, Inst Bot, State Key Lab Systemat & Evolutionary Bot, Beijing 100093, Peoples R China 3.Cent S Univ, Sch Informat Sci & Engn, Changsha 410083, Hunan, Peoples R China 4.Univ Calif Riverside, Dept Comp Sci & Engn, Riverside, CA 92521 USA 5.Tsinghua Univ, TNLIST, MOE Key Lab Bioinformat, Dept Comp Sci & Technol, Beijing, Peoples R China 6.Tsinghua Univ, TNLIST, Bioinformat Div, Dept Comp Sci & Technol, Beijing, Peoples R China
推荐引用方式 GB/T 7714	Xie, Minzhu,Wu, Qiong,Wang, Jianxin,et al. H-PoP and H-PoPG: heuristic partitioning algorithms for single individual haplotyping of polyploids[J]. BIOINFORMATICS,2016,32(24):3735-3744.
APA	Xie, Minzhu,Wu, Qiong,Wang, Jianxin,&Jiang, Tao.(2016).H-PoP and H-PoPG: heuristic partitioning algorithms for single individual haplotyping of polyploids.BIOINFORMATICS,32(24),3735-3744.
MLA	Xie, Minzhu,et al."H-PoP and H-PoPG: heuristic partitioning algorithms for single individual haplotyping of polyploids".BIOINFORMATICS 32.24(2016):3735-3744.

条目包含的文件
文件名称/大小	文献类型	版本类型	开放类型	使用许可
Xie-2016-H-PoP and H（1308KB）	期刊论文	出版稿	开放获取	CC BY-NC-SA	浏览请求全文