期刊
IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS
卷 5, 期 4, 页码 492-502出版社
IEEE COMPUTER SOC
DOI: 10.1109/TCBB.2008.67
关键词
Single individual haplotyping problem; single nucleotide polymorphism; shotgun sequencing; conflict graph; haplotype reconstruction; entropic filter
Single nucleotide polymorphism (SNP) is the most frequent form of DNA variation. The set of SNPs present in a chromosome (called the haplotype) is of interest in a wide area of applications in molecular biology and biomedicine, including diagnostic and medical therapy. In this paper, we propose a new heuristic method for the problem of haplotype reconstruction for (portions of) a pair of homologous human chromosomes from a single individual (SIH). The problem is well known in the literature and exact algorithms have been proposed for the case when no (or few) gaps are allowed in the input fragments. These algorithms, though exact and of polynomial complexity, are slow in practice. When arbitrary gaps are considered, there are no known exact methods proved to be of polynomial complexity. Also, the problem is hard to approximate with guarantees. Therefore, fast heuristics have been proposed. In this paper, we describe SpeedHap, a new heuristic method that is able to tackle the case of many gapped fragments and retains its effectiveness even when the input fragments have high rate of reading errors (up to 20 percent) and low coverage (as low as 3). We test SpeedHap on real data from the HapMap Project.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据