Minimum Conflict Individual Haplotyping from SNP Fragments and Related Genotype

CSpace > 应用数学研究所

	Minimum Conflict Individual Haplotyping from SNP Fragments and Related Genotype
	Zhang, Xiang-Sun2 ; Wang, Rui-Sheng 1; Wu, Ling-Yun2 ; Zhang, Wei 3
	2006
发表期刊	EVOLUTIONARY BIOINFORMATICS
ISSN	1176-9343
卷号	2 页码:261-270
摘要	The Minimum Error Correction (MEC) is an important model for haplotype reconstruction from SNP fragments. However, this model is effective only when the error rate of SNP fragments is low. In this paper, we propose a new computational model called Minimum Conflict Individual Haplotyping (MCIH) as an extension to MEC. In contrast to the conventional approaches, the new model employs SNP fragment information and also related genotype information, thereby a high accurate inference can be expected. We first prove the MCIH problem to be NP-hard. To evaluate the practicality of the new model we design an exact algorithm (a dynamic programming procedure) to implement MCIH on a special data structure. The numerical experience indicates that it is fairly effective to use MCIH at the cost of related genotype information, especially in the case of SNP fragments with a high error rate. Moreover, we present a feed-forward neural network algorithm to solve MCIH for general data structure and large size instances. Numerical results on real biological data and simulation data show that the algorithm works well and MCIH is a potential alternative in individual haplotyping.
关键词	individual haplotyping minimum conflict individual haplotyping NP-hard dynamic programming feed-forward neural network reconstruction rate
语种	英语
资助项目	National Natural Science Foundation of China[10471141] ; National Natural Science Foundation of China[60503004] ; Some Important Problems in Bioinformatics, CAS, China ; Kyoto University, Japan ; Research Fund of School of Information, Renmin University of China
WOS研究方向	Evolutionary Biology ; Mathematical & Computational Biology
WOS类目	Evolutionary Biology ; Mathematical & Computational Biology
WOS记录号	WOS:000205733800023
出版者	BIOINFORMATICS INST
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/3717
专题	应用数学研究所
通讯作者	Wang, Rui-Sheng
作者单位	1.Renmin Univ China, Sch Informat, Beijing 100872, Peoples R China 2.Chinese Acad Sci, Acad Math & Syst Sci, Beijing 100080, Peoples R China 3.N Carolina State Univ, Raleigh, NC 27695 USA
推荐引用方式 GB/T 7714	Zhang, Xiang-Sun,Wang, Rui-Sheng,Wu, Ling-Yun,et al. Minimum Conflict Individual Haplotyping from SNP Fragments and Related Genotype[J]. EVOLUTIONARY BIOINFORMATICS,2006,2:261-270.
APA	Zhang, Xiang-Sun,Wang, Rui-Sheng,Wu, Ling-Yun,&Zhang, Wei.(2006).Minimum Conflict Individual Haplotyping from SNP Fragments and Related Genotype.EVOLUTIONARY BIOINFORMATICS,2,261-270.
MLA	Zhang, Xiang-Sun,et al."Minimum Conflict Individual Haplotyping from SNP Fragments and Related Genotype".EVOLUTIONARY BIOINFORMATICS 2(2006):261-270.