H-PoP and H-PoPG: heuristic partitioning algorithms for single individual haplotyping of polyploids
H-PoP and H-PoPG: heuristic partitioning algorithms for single individual haplotyping of polyploids
复制标题
H-PoP 和 H-PoPG：用于多倍体单个个体单倍型分析的启发式分区算法
DOI：
10.1093/bioinformatics/btw537
复制
发表时间：
2016-12-15
期刊：
影响因子：
5.8
通讯作者：
Jiang, Tao
中科院分区：
文献类型：
--
作者：
Xie, Minzhu;Wu, Qiong;Jiang, Tao
动机：一些重要的经济作物，包括小麦和棉花，每条染色体都有两个以上的拷贝。随着下一代测序技术成本的降低和读数长度的增加，从ITS序列读数重建多倍体基因组的多种单倍型成为现实。然而，多倍体单倍体测序的计算挑战远大于二倍体单倍体测序，相关方法也很少。结果：本文将多倍体单倍体测序问题建模为阅读子的最优多重分配问题，称为多倍体平衡最优分配模型。对于从k倍体基因组测序的读数，该模型试图将读数分成k个组，使得相同组的读数之间的差异被最小化，而不同组的读数之间的差异被最大化。在已知遗传信息的情况下，将该模型推广到具有基因约束的多倍体平衡最优分割问题。这些模型都是NP难的。我们提出了两种基于动态规划的启发式算法H-POP和H-PoPG，并提出了一种限制每次迭代中间解数量的策略来分别求解这两个模型。在模拟数据和真实数据上的大量实验结果表明，我们的算法能够有效地求解模型，并且比目前最先进的多倍体单倍体单倍体算法更快、更准确。实验还表明，该算法能够有效、准确地处理长读和深读。此外，H-POP可能被应用于帮助确定生物体的倍性。可用性和实施：https://github.com/MinzhuXie/H-PoPGContact：ximinzhu@hotmail.com补充信息：补充数据可在BioInformation Online上获得。
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-PoPGContact: xieminzhu@hotmail.comSupplementary information: Supplementary data are available at Bioinformatics online.