RNA folding using quantum computers

Abstract

The 3-dimensional fold of an RNA molecule is largely determined by patterns of intramolecular hydrogen bonds between bases. Predicting the base pairing network from the sequence, also referred to as RNA secondary structure prediction or RNA folding, is a nondeterministic polynomial-time (NP)-complete computational problem. The structure of the molecule is strongly predictive of its functions and biochemical properties, and therefore the ability to accurately predict the structure is a crucial tool for biochemists. Many methods have been proposed to efficiently sample possible secondary structure patterns. Classic approaches employ dynamic programming, and recent studies have explored approaches inspired by evolutionary and machine learning algorithms. This work demonstrates leveraging quantum computing hardware to predict the secondary structure of RNA. A Hamiltonian written in the form of a Binary Quadratic Model (BQM) is derived to drive the system toward maximizing the number of consecutive base pairs while jointly maximizing the average length of the stems. A Quantum Annealer (QA) is compared to a Replica Exchange Monte Carlo (REMC) algorithm programmed with the same objective function, with the QA being shown to be highly competitive at rapidly identifying low energy solutions. The method proposed in this study was compared to three algorithms from literature and, despite its simplicity, was found to be competitive on a test set containing known structures with pseudoknots.

Fig 1

(a) Matrix representation of potential base pairs. Stems are highlighted in shades of gray and outlined in black or blue. The colors serve only to help distinguish the stems. (b) Structural representations of stems. Grey lines indicate covalent bonds, red lines indicate base pairing, and dashed purple lines represent base pairs in a pseudoknot configuration. The color of the boxes map to the stems identified in (a). (c) Each possible stem is assigned to a qubit on the quantum device. If the qubit returns “1”, then the associated stem is included in the RNA secondary structure. Otherwise, the stem is excluded.

Fig 2

(a) Example RNA sequence from simian retrovirus type-1 (SRV-1) with structure containing pseudoknot correctly predicted by algorithm (PDB code: 1E95). The phosphate backbone is colored white for unpaired bases. (b) Exact Enumeration (EE) was used to compute the sensitivity and specificity of the proposed Hamiltonian (Eq 13) for systems containing 45 stems or fewer. Replica Exchange Monte Carlo (REMC) and quantum computing (QC) methods were tested on the same sequences and were found to exactly recapitulate the lowest energy solutions found by exact enumeration.

Fig 3. Replica Exchange Monte Carlo (REMC) and Quantum Computing algorithms were tested on systems containing more than 45 stems, which exceeds the practical limit of what can be solved with exact enumeration.

The eigenvalues of the lowest energy systems are compared in (a). The dashed line represents y = x.

Fig 4. Comparison of methods on the datasets described in previous sections.

Exact Enumeration (EE) is not computed for systems containing more than 45 stems.