Haplotype assembly from aligned weighted SNP fragments

doi:10.1016/j.compbiolchem.2005.05.001

CSpace > 应用数学研究所

	Haplotype assembly from aligned weighted SNP fragments
	Zhao, YY; Wu, LY; Zhang, JH; Wang, RS; Zhang, XS
	2005-08-01
发表期刊	COMPUTATIONAL BIOLOGY AND CHEMISTRY
ISSN	1476-9271
卷号	29 期号:4 页码:281-287
摘要	Given an assembled genome of a diploid organism the haplotype assembly problem can be formulated as retrieval of a pair of haplotypes from a set of aligned weighted SNP fragments. Known computational formulations (models) of this problem are minimum letter flips (MLF) and the weighted minimum letter flips (WMLF; Greenberg et al. (INFORMS J. Comput. 2004,14, 211-213)). In this paper we show that the general WMLF model is NP-hard even for the gapless case. However the algorithmic solutions for selected variants of WMFL can exist and we propose a heuristic algorithm based on a dynamic clustering technique. We also introduce a new formulation of the haplotype assembly problem that we call COMPLETE WMLF (CWMLF). This model and algorithms for its implementation take into account a simultaneous presence of multiple kinds of data errors. Extensive computational experiments indicate that the algorithmic implementations of the CWMLF model achieve higher accuracy of haplotype reconstruction than the WMLF-based algorithms, which in turn appear to be more accurate than those based on MLF. (c) 2005 Elsevier Ltd. All rights reserved.
关键词	SNP haplotype assembly minimum letter flips dynamic clustering
DOI	10.1016/j.compbiolchem.2005.05.001
语种	英语
WOS研究方向	Life Sciences & Biomedicine - Other Topics ; Computer Science
WOS类目	Biology ; Computer Science, Interdisciplinary Applications
WOS记录号	WOS:000231333000003
出版者	ELSEVIER SCI LTD
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/2352
专题	应用数学研究所
通讯作者	Zhao, YY
作者单位	CAS, Acad Math & Syst Sci, Inst Appl Math, Beijing 100080, Peoples R China
推荐引用方式 GB/T 7714	Zhao, YY,Wu, LY,Zhang, JH,et al. Haplotype assembly from aligned weighted SNP fragments[J]. COMPUTATIONAL BIOLOGY AND CHEMISTRY,2005,29(4):281-287.
APA	Zhao, YY,Wu, LY,Zhang, JH,Wang, RS,&Zhang, XS.(2005).Haplotype assembly from aligned weighted SNP fragments.COMPUTATIONAL BIOLOGY AND CHEMISTRY,29(4),281-287.
MLA	Zhao, YY,et al."Haplotype assembly from aligned weighted SNP fragments".COMPUTATIONAL BIOLOGY AND CHEMISTRY 29.4(2005):281-287.