Searching Method of Structural Similar Subnets in Protein-protein Interaction Networks Based on Quantum Walks

2nd International Symposium on Application of Materials Science and Energy Materials

材料科学;能源学

Yang, Li-Ping^1^2 ; Lu, Song-Feng^2^3

College of Informatics, Huazhong Agricultural University, Wuhan

430070, China^1

School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan

430074, China^2

Shenzhen Research Institute, Huazhong University of Science and Technology, Shenzhen

518063, China^3

关键词: Biological functions;    Classical counterpart;    Computation algorithm;    Continuous-time quantum walks;    Protein-protein interaction networks;    Protein-protein interactions;    Quantum algorithms;    Searching methods;   

Others  :  https://iopscience.iop.org/article/10.1088/1757-899X/490/6/062021/pdf
DOI  :  10.1088/1757-899X/490/6/062021

学科分类：材料科学（综合）

来源: IOP

【 摘 要 】

Comparing and investigation into different protein-protein interaction networks (PPI networks) is significant for discovering new biological function and comprehending the evolution of the protein-protein interactions. Because general PPI networks are large in scale, existing classical computation algorithms of solving alignment and search in PPI networks possess too high time complexity. The time complexity is so high that it is impossible for the algorithm to align the whole network simultaneously. An effective quantum algorithm, Quantum-walks Algorithm for PPI-network Similar Subnets Searching (QPSS), is introduced to improve the situation mentioned above based on the continuous-time quantum-walks model in quantum computation. The process in detail of the QPSS algorithm is demonstrated. Moreover, we discuss the performance evaluation of this algorithm. After the time complexity of QPSS algorithm compares with its classical counterpart, it has been proved that the QMSM obtains a nearly quadratic speed-up.