基于基因次序的基因组间距离的计算

Approach to Computation of Genome Distance Based on Gene Order

给出了计算两个具有相同内容、不同次序的基因组之间距离的算法。给定一组内容相同、次序不同的基因组,构造一个完全图,寻找一个基因组使得它与给定的各个基因组之间距离的累加和达到最小,这个问题可以转化为TSP问题。利用最小生成树方法找到一个中心基因组,接下来构造断点图,最后利用断点图来计算集合中的每一个基因组和中心基因组之间的距离。

A new algorithm is presented, for computing the distance between genomes with the same content but different orders. Given a set of genomes with the same content but different orders, we a complete graph is con- structed, and then produced a new genome called median genome that will minimize the sum of the distances from it to the others, which can be changed into a TSP problem, First, Kruskal algorithm is applyed to find the median genome; second, The breakpoint graph is constructed; finally, the distance is computed between the median genome and every genome.