Quantum algorithm for identifying RNA 3D motifs by processing RNA secondary structure graphs

Abstract

The identification of RNA motifs plays a crucial role in understanding biological functions, predicting RNA 3D structures, and designing RNA-based therapeutics. One of the efficient strategies approaches this task by analyzing secondary structure graphs annotated with non-canonical base interactions, effectively reframing the problem as a two-dimensional graph-theoretic challenge. However, both the graph isomorphism problem and the maximum common subgraph problem in this domain are classified as NP-complete. Classical computing architectures struggle to address these problems efficiently due to their substantial computational resource demands. In this work, we propose a quantum algorithm specifically designed for processing RNA secondary structure graphs. By encoding the adjacency matrix into a quantum circuit and incorporating base interaction families as edge weights, our approach achieves a resource efficiency of [O](log2 N) in terms of qubits. Numerical simulations demonstrate the algorithms capability to identify 15 distinct motifs across three structural categories: hairpin loops, internal loops, and three-way junction loops. Furthermore, the method successfully detects the common motif between two complete RNA chains. Finally, 29 high conserved RNA motifs were identified in four cell lines of a key lung cancer biomarker gene (MIF), and their potential roles as drug targets were explored. This work presents a highly promising quantum computing framework for addressing the RNA motif identification problem.