Haplotype assembly from aligned weighted SNP fragments

doi:10.1016/j.compbiolchem.2005.05.001

	Haplotype assembly from aligned weighted SNP fragments
	Zhao, YY; Wu, LY; Zhang, JH; Wang, RS; Zhang, XS
刊名	COMPUTATIONAL BIOLOGY AND CHEMISTRY
	2005-08-01
卷号	29 期号:4 页码:281-287
关键词	SNP haplotype assembly minimum letter flips dynamic clustering
ISSN号	1476-9271
DOI	10.1016/j.compbiolchem.2005.05.001
英文摘要	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.
WOS研究方向	Life Sciences & Biomedicine - Other Topics ; Computer Science
语种	英语
出版者	ELSEVIER SCI LTD
WOS记录号	WOS:000231333000003
内容类型	期刊论文
源URL	[http://ir.amss.ac.cn/handle/2S8OKBNM/2351]
专题	中国科学院数学与系统科学研究院
通讯作者	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.