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

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. (paper)