• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Computational Biology and Bioinformatics, IEEE/ACM Transactions on >LGH: A Fast and Accurate Algorithm for Single Individual Haplotyping Based on a Two-Locus Linkage Graph
【24h】

LGH: A Fast and Accurate Algorithm for Single Individual Haplotyping Based on a Two-Locus Linkage Graph

机译：LGH：一种基于两位置链接图的单人单体型快速准确算法

获取原文
获取原文并翻译 | 示例
       
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

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.
机译：分阶段的单倍型信息对于我们在遗传水平上完全了解个体之间的差异至关重要。给定从同源染色体对中测序的DNA片段的集合，单人单体型（SIH）的问题旨在使用计算机算法重建一对单体型。在本文中，我们将对齐的DNA片段的信息编码为两位置连锁图，并通过图的顶点标记解决SIH问题。为了找到具有最小不相容边权重之和的顶点标签，我们开发了一种快速而准确的启发式算法。它首先通过自适应的广度优先搜索来检测容错组件。然后为每个组件标识正确的顶点标签，通过这些标签可以进一步纠正定序错误，并相应地调整边缘权重。将每个容错组件收缩到单个顶点后，将在生成的压缩链接图中重复上述过程，直到不再检测到容错组件为止。该算法最后根据顶点标记输出单倍型对。在模拟和真实数据上进行的大量实验表明，与单个现有单元型的五个现有算法相比，我们的算法更准确，更快。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号