LGH: A Fast and Accurate Algorithm for Single Individual Haplotyping Based on a Two-Locus Linkage Graph
LGH: A Fast and Accurate Algorithm for Single Individual Haplotyping Based on a Two-Locus Linkage Graph
复制标题
LGH：一种基于二位点连锁图的快速准确的单个体单体型分析算法
DOI：
10.1109/tcbb.2015.2430352
复制
发表时间：
2015-11-01
影响因子：
4.5
通讯作者：
Chen, Xin
中科院分区：
文献类型：
--
作者：
Xie, Minzhu;Wang, Jianxin;Chen, Xin
阶段性单倍型信息对于我们在基因水平上完全理解个体之间的差异至关重要。给定从一对同源染色体中测得的一组DNA片段，单个体单倍型(SIH)问题旨在使用计算机算法重建一对单倍型。本文将DNA序列的比对信息编码成一个双轨迹链接图，并通过对该图的顶点标记来解决SIH问题。为了找到不相容边权重和最小的顶点标注问题，提出了一种快速、准确的启发式算法。它首先通过自适应的广度优先搜索来检测容错组件。然后为每个分量识别适当的顶点标记，利用该标记进一步校正排序错误，并相应地调整边权重。在将每个容错组件收缩为单个顶点后，在得到的压缩链接图上迭代上述过程，直到不再检测到容错组件。该算法最终输出基于顶点标记的单倍型对。在模拟和真实数据上的大量实验表明，我们的算法比现有的五种单倍体单倍型算法更准确、更快。
Phased haplotype information is crucial in our complete understanding of differences between individuals at the genetic level. Given a collection of DNA fragments sequenced from a homologous pair of chromosomes, the problem of single individual haplotyping (SIH) aims to reconstruct a pair of haplotypes using a computer algorithm. In this paper, we encode the information of aligned DNA fragments into a two-locus linkage graph and approach the SIH problem by vertex labeling of the graph. In order to find a vertex labeling with the minimum sum of weights of incompatible edges, we develop a fast and accurate heuristic algorithm. It starts with detecting error-tolerant components by an adapted breadth-first search. A proper labeling of vertices is then identified for each component, with which sequencing errors are further corrected and edge weights are adjusted accordingly. After contracting each error-tolerant component into a single vertex, the above procedure is iterated on the resulting condensed linkage graph until error-tolerant components are no longer detected. The algorithm finally outputs a haplotype pair based on the vertex labeling. Extensive experiments on simulated and real data show that our algorithm is more accurate and faster than five existing algorithms for single individual haplotyping.