基因组断点Median问题的算法研究

摘要：

为有效解决生物信息学中的基因组断点median问题,针对4个以上环形基因组的一般情形,建立了该问题的图模型.鉴于基因组断点median问题自身的NP-困难性,从问题转化的角度,将其等价地化为图上的旅行商问题(TSP),找出二者之间最优解的关系,进而给出了其p-近似算法,其中p为用于求解TSP问题的近似算法的近似比.对算法的复杂度和近似比进行了分析,基于LINGO软件的算例表明了该算法的可行性和有效性.

关键词：基因组、断点median、旅行商问题、哈密尔顿圈、近似算法

所属期刊栏目：31

分类号：TP301.6;Q332(计算技术、计算机技术)

资助基金：国家自然科学基金项目10901093

在线出版日期：2010-12-16（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：4524-4526,4530