基因组移位变换中值问题的近似算法  

Approximation Algorithm for the Translocation Median Problem of Genomes

作　　者：王骁力[1] 夏云清[2] 

机构地区：[1]南阳师范学院数学与统计学院,河南南阳473061 [2]中州大学基础科学学院,郑州450015

出　　处：《河南大学学报（自然科学版）》2011年第4期339-344,共6页Journal of Henan University:Natural Science

基　　金：河南省自然科学基金资助项目(102300410184);河南省教育厅自然科学基金资助项目(2009B11017);南阳师院高层次人才科研启动费资助

摘　　要：讨论基因组在移位变换下的中值问题(TMP).给定m个基因组,每个基因组含N条染色体,TMP问题是求另一个基因组,使该基因组与其它基因组之间的移位距离和最小.对无向模型,用转化为旅行售货员问题的断点中值问题给出其近似解;对有向模型,借助于求图的最大权匹配给出TMP问题的近似算法.The Translocation Median Problem（TMP） of genomes was considered in the paper.Given m multi-genomes each containing N chromosomes,TMP is to find another genome such that sum of the translocation distances between this genome and the given ones is minimized.For the unsigned model,the Breakpoint Median Problem（BMP）,which can be transformed to the Travelling Salesman Problem（TSP）,was studied to approximate TMP.For the signed model,TMP was approximated by computing a maximum weighted matching in a constructed graph.

关 键 词：移位距离 中值问题 基因组重构 近似算法 

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