Research Of Linear Programming-Round Correlation Algorithm For Maximum Stacking Base Pairs

Ribonucleic acid(RNA)is a biological macromolecule with long chain structure,and has the function of storing and transmitting genetic information.RNA plays an important role in regulating genetic and metabolic activities,and is a class of biological macromolecules with important biological functions and clinical values.The structure of RNA can be divided into three levels.The primary structure of RNA is mainly formed by sequences composed of four types of bases:A,G,C,and U,while the secondary structure of RNA refers to the planar structure formed by folding due to the mutual influence and interaction between non-adjacent bases.The tertiary structure of RNA is a three-dimensional structure formed by folding the secondary structure.The prediction of the secondary structure of RNA is based on the relevant theories of bioinformatics,using the primary sequence of RNA as input to predict the secondary structure of RNA.The secondary structure of RNA plays a crucial role in regulating the tertiary structure of RNA,so determining the optimal secondary structure of RNA is crucial for analyzing and understanding the transmission mechanism of genetic information.In the process of research on RNA secondary structure prediction,many related issues.have been raised and many related algorithms have been designed.Among them,the maximum stacking base pair problem is a fundamental combinatorial problem for RNA secondary structure prediction under the energy model.The two adjacent and parallel base pairs in the RNA structure are called stacks,and the negative energy contained in the stack contributes to the stability of the RNA secondary structure.The research on the problem of maximum stacked base pairs is to find the structure that can form a stack or participate in the formation of the largest number of base pairs in the stack.Regardless of whether the candidate base pairs follow biological principles or are explicitly used as inputs,the maximum stack base pair problem is an NP-hard problem.Whether the candidate base pairs follow the biological principles or are explicitly used as input,the problem of maximum stacking base pairs is an NP-hard problem.Even if each base is limited to be related to k(a constant)bases at most,that is,each base can only form a base pair with one of the k bases associated with it,even if the base is weighted,the restricted version of the maximum stacking base pair problem has proved to be still an APXhard problem.In the continuous research on the problem of maximum stacking base pairs,many different approximation algorithms have been proposed,among them,Liu et al.proposed a approximation algorithm based on nonlinear linear programming-rounding method to solve the problem of the maximum number of bases participating in the formation of the stack,which has good approximation ratio and time performance in simulation data.This paper studies this approximation algorithm and proposes an approximation algorithm based on linear programming-rounding with a theoretical approximation ratio of[(2k-2)e]2 for the maximum number of stackings in the secondary structure.This algorithm can obtain an approximate solution to the problem of maximum stacking base pairs,making the stackings formed by base pairs as many as possible,that is,obtaining an approximate solution to the maximum number of stacking formed when multiple parallel and adjacent base pairs are selected at the same time.And this paper uses the actual RNA sequence as the input data to verify the actual performance of the algorithm.The approximation ratio obtained in actual testing and verification is much better than the theoretical approximation ratio,and has good time performance.In addition,this paper also uses the existing linear programming-rounding approximation algorithm to calculate and solve the related problems studied in this paper,and verifies the performance of the existing algorithm on the actual RNA sequences.Comparing the experimental results,it is found that although the existing algorithm can solve the problems studied in this article,using the algorithm proposed in this article will have better approximation ratio and time performance both in theory and in practical verification.