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

Algorithmic research on genome breakpoint median problem

作　　者：王继强[1] 

机构地区：[1]山东财政学院统计与数理学院,山东济南250014

出　　处：《计算机工程与设计》2010年第20期4524-4526,4530,共4页Computer Engineering and Design

基　　金：国家自然科学基金项目(10901093)

摘　　要：为有效解决生物信息学中的基因组断点median问题,针对4个以上环形基因组的一般情形,建立了该问题的图模型。鉴于基因组断点median问题自身的-困难性,从问题转化的角度,将其等价地化为图上的旅行商问题(TSP),找出二者之间最优解的关系,进而给出了其-近似算法,其中为用于求解TSP问题的近似算法的近似比。对算法的复杂度和近似比进行了分析,基于LINGO软件的算例表明了该算法的可行性和有效性。To solve the genome breakpoint median problem in bioinformatics efficiently,a graph model is constructed for the general case where more than 4 circular genomes are involved.In view of the-hardness of the genome breakpoint median problem,it is equivalently transformed into the traveling salesman problem（TSP） in the graph from the angle of problem transformation,then the relationship between their optimal solutions is found and a-approximation algorithm is proposed,where is the approximation ratio of some approximation algorithm for the TSP.After analyzing the complexity and approximation ratio of this algorithm,an instance based on LINGO software demonstrates its feasibility and efficiency.

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] Q332[自动化与计算机技术—计算机科学与技术]