Research On Solution Algorithms And Privacy-Preserving Models For The Double Digest Problem In Bioinformatics

With the advancement of technology,exploration of the material world has progressed from visible macroscopic objects to the microscopic world.Genome sequencing is an important branch of bioinformatics that can help people better understand the composition,function,and mechanisms of disease occurrence in genomes,which is of great significance for medical diagnosis and treatment.The double digest problem is a fundamental problem in sequencing technology and the focus of this study.The rapid development of sequencing technology has led to an explosion of biological data,which requires powerful computing capabilities and resources.Local computing resources are becoming increasingly inadequate to meet these data processing needs,and existing optimization algorithms also need to be improved in terms of efficiency.Therefore,it is necessary to seek new computing paradigms and design more efficient algorithms.Quantum computing,based on the characteristics of quantum superposition and entanglement,possesses powerful parallel computing capabilities and is expected to provide assistance in accelerating the solution of bioinformatics problems.Therefore,it is meaningful to design more efficient quantum-inspired optimization algorithms by combining the advantages of existing optimization algorithms and quantum computing.As the manufacturing and maintenance costs of quantum computers are very high and they have stringent requirements for the physical environment,quantum cloud platforms that provide quantum outsourcing computing services to the public have been well developed.Nevertheless,outsourcing computing brings the risk of privacy leaks while making full use of the powerful computing capabilities of cloud servers.This paper addresses several issues in bioinformatics,such as complex modeling and tedious computation of existing bioinformatics problems,limited computing and storage resources of classical computers,and the risk of privacy leakage in data outsourcing.Based on existing optimization algorithms and quantum computing,as well as their cloud computing technology architecture,we conduct a study on the solution algorithms and privacy-preserving models for the double digest problem in bioinformatics.The specific research contents are as follows:(1)Propose a classical multi-operator genetic algorithm for the double digest problemTo address the complexity,cumbersome computation,and low efficiency of existing bioinformatics problems,this study proposes a vector-based modeling for bioinformatics problems and a classical multioperator genetic algorithm with six genetic operators for the double digest problem.For complex instances,a scaling adjustment strategy is proposed,and the solution of the adjusted instance is used as an approximate solution to the original instance.Based on the above algorithm,an open-source MATLAB software package DDmap is developed.The performance of the proposed DDmap is tested by typical instances and random instances,and the experimental results are visualized in nested pie charts.The influence of the maximum length of the input fragment on the experimental results is explored.By comparative experiments,the overall effect of the six genetic operators in DDmap is compared with other genetic algorithms,and DDmap is found to be more efficient in solving the double digest problem.(2)Propose a quantum inspired genetic algorithm for the double digest problemTo address the problems of genetic algorithms easily falling into local optimal solutions,slow convergence speed,and low efficiency when dealing with large amounts of data,this study proposes a quantum inspired genetic algorithm,QIGA,for the double digest problem.QIGA uses the probability amplitude representation of quantum bits to encode the double digest problem,simulates the random observation of quantum collapse to enrich the population.Quantum selection,quantum crossover,and quantum mutation operators are designed using quantum rotation gates,quantum NOT gates,and other methods to improve the convergence speed of the algorithm.QIGA is tested on typical instances and random instances and is compared with SK05,GM12,and DDmap.The results show that QIGA is more efficient in solving the double digest problem than SK05 and GM12 and slightly better than DDmap.(3)Propose a secure outsourcing computing scheme for the double digest problemTo address the problems of large amounts of data in bioinformatics,limited local computing resources,and the risk of privacy leakage when outsourcing data,this study proposes a secure outsourcing computing model,PP-DDP,for the double digest problem.In this model,the complex double digest calculation is outsourced to the cloud server using the quantum inspired genetic algorithm.In order to ensure the privacy of the double digest data,an order-preserving homomorphic index scheme for the data owner is proposed.The data owner encrypts the data and then outsources the encrypted data to the cloud server,where the double digest calculation is performed in a ciphertext environment.To address untrusted cloud servers,a result verification scheme for the data owner is proposed to ensure the correctness of the results returned by the cloud server.PPDDP is compared with existing schemes from both performance and functionality perspectives.The experimental results show that PP-DDP consumes no more than 13%of the computing cost to protect the privacy of double digest data and is the only scheme that can achieve secure outsourcing computation of the double digest problem.