Research On Kemelization Algorithm For Maximal Strip Recovery Problem In Genome

Many problems in computational genomics are NP-hard,and people can use approximate algorithms,heuristic algorithms and random algorithms to solve these problems.But,computational genomics is ultimately about contributing to biology,Pharmacology,and pathology,all areas of life,so the solution must be as precise as possible.Therefore,parameterized algorithm is a good method to solve the computational genomics problem.Before analyzing the genetic information,it is necessary to ensure that is no redundant data or interfering data in the gene map.Maximal Strip Recovery is the processing of data in a genetic map without errors or fuzzy interference.Its Complementary Maximal Strip Reccovery,is equivalent to it.This paper focuses on the specific research of the kernelization for the CMSR problem and proposes the improved kernel.The specific research contents include:Firstly,the development background of Parameterized Computation and Complexity Theory is briefly introduced.At the same time,relevant theories and technologies,such as parameterized algorithm and kernelization technology,are introduced for the CMSR problem we studied.Second,based on the current kemelization idea of best results for CMSR problem,further analysis of the problems of CMSR structure features,puts forward a new more help to the analysis of the auxiliary figure,we generate the edge between each a synchronized block not each super-block generation side directly,so the figure structure more meticulous,help to analysis the special circumstances of CMSR,and makes a simplified rules,the design more simple and easy to understand.We proposed a 42k kernel based on seven simplified rules.Then,the results of the CMSR problem are optimized and a new concept gap is proposed.Using the concept of gap,two simplified rules are proposed,the definition of the rules is simple and easy to operate,and the kernel of the CMSR problem is optimized to 26k according to the two simplified rules.The results of this paper provide reference for solving CMSR problems accurately and provide theoretical support for the application of kernelization technology.