EBD(1,2)的参数化动态规划算法改进

An Improved Parameterized Dynamic Programming Algorithm for( 1,2)-Exemplar Breakpoint Distance

为了提高Z.Wei和D.Zhu的算法的计算效率,通过引入全局变量Map数组避免重复计算基因家族的邻接关系,将Z.Wei和D.Zhu的固定参数算法的时间复杂度改进为O(s^24~sn),空间复杂度保持O(s4~sn);当给定基因组是有向时,适当地修正之后,证明了Z.Wei和D.Zhu的固定参数动态规划算法适合求解有向(1,2)-范例断点距离.相关算法可使用C++来实现,仿真实验进一步验证了改进算法的有效性.

In order to improve the computational efficiency of Z .Wei and D.Zhu′s algorithm, this paper improves the time complexity of Z.Wei and D.Zhu′s algorithm to O(s24sn) by introducing an global array Map to avoid repeatedly computing of the adjacencies of gene families , while the space complexity keeps O( s4 s n) .If the given genomes is signed , we show that Z.Wei and D.Zhu′s fixed parameter dynamic programming algorithm is suitable to compute the signed (1, 2)-exemplar breakpoint distance after minor revision .The algorithms are implemented by using C ++language, and simulations indicate the proposed algorithms′effectiveness .