HapCompass: A Fast Cycle Basis Algorithm for Accurate Haplotype Assembly of Sequence Data
HapCompass: A Fast Cycle Basis Algorithm for Accurate Haplotype Assembly of Sequence Data
复制标题
DOI：
10.1089/cmb.2012.0084
复制
发表时间：
2012-06-01
影响因子：
1.7
通讯作者：
Istrail, Sorin
中科院分区：
文献类型：
--
作者：
Aguiar, Derek;Istrail, Sorin
由于目前测序技术的限制，基因组组装方法产生单倍型相位模糊组装。确定个体的单倍型相位在计算上具有挑战性并且在实验上昂贵。然而，单倍型相位信息在许多生物信息学工作流程中是至关重要的，例如遗传关联研究和基因组插补。当前从序列数据确定单体型相位的计算方法-称为单体型组装-对于大数据（1000个基因组类型）难以产生准确的结果，或者在考虑到现代高通量测序技术的不现实的受限优化上操作。我们提出了一种新的算法，HapCompass，密集测序的人类基因组数据的单倍型组装。HapCompass算法在图上操作，其中单核苷酸多态性（SNP）是节点，并且边缘由序列读数定义，并且被视为单倍型中共发生的SNP等位基因的支持证据。在我们的图模型中，单倍型定相对应于生成树。我们定义了最小加权边缘去除优化这个图，并开发了一个算法的基础上循环的基础上解决冲突的证据的局部优化。然后，我们估计产生染色体的完整单倍型组装所需的测序量。使用这些估计值以及从基因组组装和单倍型定相中借来的指标，我们比较了HapCompass，基因组分析工具包和HapCut的准确性，用于1000个基因组计划和模拟数据。我们表明，HapCompass在各种数据和指标上的表现明显更好。HapCompass可免费下载（www.brown.edu/Research/Istrail_Lab/）。
Genome assembly methods produce haplotype phase ambiguous assemblies due to limitations in current sequencing technologies. Determining the haplotype phase of an individual is computationally challenging and experimentally expensive. However, haplotype phase information is crucial in many bioinformatics workflows such as genetic association studies and genomic imputation. Current computational methods of determining haplotype phase from sequence data-known as haplotype assembly-have difficulties producing accurate results for large (1000 genomes-type) data or operate on restricted optimizations that are unrealistic considering modern high-throughput sequencing technologies. We present a novel algorithm, HapCompass, for haplotype assembly of densely sequenced human genome data. The HapCompass algorithm operates on a graph where single nucleotide polymorphisms (SNPs) are nodes and edges are defined by sequence reads and viewed as supporting evidence of co-occurring SNP alleles in a haplotype. In our graph model, haplotype phasings correspond to spanning trees. We define the minimum weighted edge removal optimization on this graph and develop an algorithm based on cycle basis local optimizations for resolving conflicting evidence. We then estimate the amount of sequencing required to produce a complete haplotype assembly of a chromosome. Using these estimates together with metrics borrowed from genome assembly and haplotype phasing, we compare the accuracy of HapCompass, the Genome Analysis ToolKit, and HapCut for 1000 Genomes Project and simulated data. We show that HapCompass performs significantly better for a variety of data and metrics. HapCompass is freely available for download (www.brown.edu/Research/Istrail_Lab/).