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