| Genome rearrangement problem is a hot topic in the field of computational biology in recent 20 years,which has applications in the reconstruction of phylogenetic tree,biomedical technology and exploring the relationship between organisms.Results of genome rearrangement can be used to measure the difference of organisms and infer their evolution process.Fast computations of genome rearrangement has become an important tool to exploring the evolutionary rule in the study and practice of molecular biology and medical science.The main content of this dissertation is(1,2)-exemplar breakpoint distance problem.In the research of exemplar breakpoint distance problem,D.Bryant proved that(1,2)-exemplar breakpoint distance problem is NP-hard.Unless P=NP,there is no polynomial time algorithm for EBD(1,2).Z.Wei and D.Zhu have concluded that in practice two genes of the same gene family usually occur within a small physical distance in a genome.On this basis,they proposed the first fixed parameter algorithm for unsigned EBD(1,2)problem.Thereafter,they came to the algorithm's time complexity O(s4sn2)and space complexity O(s4sn)through detailed analysis.This dissertation 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(s4sn)constantly.If the given genomes is signed,this dissertation 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 modifications and extensions.Combined Map array,the algorithm can be achieved within the time complexity O(s24sn).This dissertation improves the space complexity of the unsigned and signed fixed parameter dynamic programming algorithm from O(s4sn)to O(4sn)by introducing adjacency list.The algorithms are implemented by using C++ language,and simulations indicate the proposed algorithm's effectiveness. |
PDF Full Text Request