计算有向基因组圈图的连通分支的有效算法

Efficient algorithm for computing the connected components of the cycle graph of two signed permutations

基因组重排问题是分子生物学中的重要问题,进化问题的研究可归结为进化距离问题的研究.即计算从一个基因组进化为另一个基因组所需的最少的进化变换数目.可借助基因组之间的圈图研究翻转进化问题,Hannenhalli给出了一个计算圈图分支的一个线性时间算法,但考察的对象为圈图上的圈集合,且需要一些等价变换.从边集合出发给出了计算有向基因组的圈图连通分支的线性时间算法.

Genomes rearrangement is an important problem in evolutionary molecular biology. From a computational perspective, the study of evolution based on rearrangements leads to a rearrangement distance problem, i.e., computing the minimum number of rearrangement events required to transform one genome to another. Bader et al give a linear-time algorithm, which requires two equivalent transformations of signed Bader et al permutations and unsigned per- mutations, for computing the connected components of the cycle graph between signed permutations, when the orientation of the genes is known. An algorithm for computing the connected components of the cycle graph of the given two signed genomes is studied, which is more efficient than the primary algorithm.