An optimization approach to the reconstruction of positional DNA sequencing by hybridization with errors

doi:10.1016/j.ejor.2006.08.031

CSpace > 应用数学研究所

	An optimization approach to the reconstruction of positional DNA sequencing by hybridization with errors
	Zhang, Ji-Hong ; Wu, Ling-Yun; Zhao, Yu-Ying ; Zhang, Xiang-Sun
	2007-10-01
发表期刊	EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
ISSN	0377-2217
卷号	182 期号:1 页码:413-427
摘要	Positional DNA sequencing by hybridization (PSBH) is a recently proposed enhancement of DNA sequencing by hybridization (SBH, potentially a powerful alternative to the DNA sequencing by gel electrophoresis). It has been discussed in many papers and applied to large scale sequencing by hybridization. However, the computational part of PSBH reconstruction is a difficult problem, especially for the occurrence of hybridization errors. So far the problem has not been solved well. Taking PSBH as a combinatorial optimization problem, a novel reconstruction approach to PSBH is presented in this paper. The proposed approach accepts both the negative and positive errors and can greatly reduce ambiguities in the reconstruction of PSBH. The computational experiment shows that our algorithm works satisfactorily and correctly on the test data, especially for the positive errors and k-tuple repetitions. (c) 2006 Elsevier B.V. All rights reserved.
关键词	positional sequencing by hybridization reconstruction of DNA fragment positive errors and negative errors dynamic programming branch and bound algorithm
DOI	10.1016/j.ejor.2006.08.031
语种	英语
WOS研究方向	Business & Economics ; Operations Research & Management Science
WOS类目	Management ; Operations Research & Management Science
WOS记录号	WOS:000246406000027
出版者	ELSEVIER SCIENCE BV
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/4247
专题	应用数学研究所
通讯作者	Zhang, Ji-Hong
作者单位	1.Tsing Hua Univ, Sch Econ & Managements, Beijing 100084, Peoples R China 2.Chinese Acad Sci, Ctr Bioinformat, Acad Math & Syst Sci, Beijing 100080, Peoples R China 3.Beijing Foreign Studies Univ, Sch Int Business, Beijing 100089, Peoples R China
推荐引用方式 GB/T 7714	Zhang, Ji-Hong,Wu, Ling-Yun,Zhao, Yu-Ying,et al. An optimization approach to the reconstruction of positional DNA sequencing by hybridization with errors[J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH,2007,182(1):413-427.
APA	Zhang, Ji-Hong,Wu, Ling-Yun,Zhao, Yu-Ying,&Zhang, Xiang-Sun.(2007).An optimization approach to the reconstruction of positional DNA sequencing by hybridization with errors.EUROPEAN JOURNAL OF OPERATIONAL RESEARCH,182(1),413-427.
MLA	Zhang, Ji-Hong,et al."An optimization approach to the reconstruction of positional DNA sequencing by hybridization with errors".EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 182.1(2007):413-427.