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

Approximation Algorithm for the Translocation Median Problem of Genomes

讨论基因组在移位变换下的中值问题(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.