移位变换下一类进化树的重构问题

The problem on polygenetic tree reconstruction by translocations

讨论多重基因组在移位变换下的一类进化树的重构问题:给定一个由若干基因组组成的集族Ⅱ与另一个基因组A,其中所有基因组由同样的一些有向的基因组成,且每个基因组由相同数目的染色体组成,每一个基因在每个基因组中恰好出现一次,所有基因组有相同的尾基因集合,要求构造一个由A到Ⅱ的进化树,使得沿此树所发生的移位变换数目最少.给出由一个基因组生成一些给定基因组的近似算法;在一个特殊情况下给出其多项式时间算法.

Polygenetic tree reconstruction of multiple signed genomes by translocations is discussed: Given a collection of signed genomes and another genome A, in which all genomes contain the same set of genes and all genes appearing within a genome are pairwise different, and all genome has the same set of nodal genes, the number of chromosomes are same, a polygenetic tree is reconstructed, such that the number of all evolutionary events occurred along the tree is minimum, i.e. , the collection are generated from A in a minimum number of translocations. The approximation algorithm is given for the problem, and a polynomial algorithm is given in a special case.