期刊
BIOINFORMATICS
卷 24, 期 16, 页码 I153-I159出版社
OXFORD UNIV PRESS
DOI: 10.1093/bioinformatics/btn298
关键词
-
类别
资金
- Div Of Information & Intelligent Systems
- Direct For Computer & Info Scie & Enginr [0810905] Funding Source: National Science Foundation
Motivation: The goal of the haplotype assembly problem is to reconstruct the two haplotypes (chromosomes) for an individual using a mix of sequenced fragments from the two chromosomes. This problem has been shown to be computationally intractable for various optimization criteria. Polynomial time algorithms have been proposed for restricted versions of the problem. In this article, we consider the haplotype assembly problem in the most general setting, i.e. fragments of any length and with an arbitrary number of gaps. Results: We describe a novel combinatorial approach for the haplotype assembly problem based on computing max-cuts in certain graphs derived from the sequenced fragments. Levy et al. have sequenced the complete genome of a human individual and used a greedy heuristic to assemble the haplotypes for this individual. We have applied our method HapCUT to infer haplotypes from this data and demonstrate that the haplotypes inferred using HapCUT are significantly more accurate (2025 lower maximum error correction scores for all chromosomes) than the greedy heuristic and a previously published method, Fast Hare. We also describe a maximum likelihood based estimator of the absolute accuracy of the sequence-based haplotypes using population haplotypes from the International HapMap project.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据