Factorization Machine with Quadratic-Optimization Annealing for RNA Inverse Folding and Evaluation of Binary-Integer Encoding and Nucleotide Assignment
Authors: Shuta Kikuchi, Shu Tanaka
Organizations: Graduate School of Science and Technology, Keio University, Yokohama, Kanagawa 223-8522, Japan · Keio University Sustainable Quantum Artificial Intelligence Center (KSQAIC), Keio University, Minato-ku, Tokyo 108-8345, Japan · Department of Applied Physics and Physico-Informatics, Keio University, Yokohama, Kanagawa 223-8522, Japan · Human Biology-Microbiome-Quantum Research Center (WPI-Bio2Q), Keio University, Minato-ku, Tokyo 108-8345, Japan
The RNA inverse folding problem aims to identify nucleotide sequences that preferentially adopt a given target secondary structure. While various heuristic and machine learning-based approaches have been proposed, many require a large number of sequence evaluations, which limits their applicability when experimental validation is costly. We propose a method to solve the problem using a factorization machine with quadratic-optimization annealing (FMQA). FMQA is a discrete black-box optimization method reported to obtain high-quality solutions with a limited number of evaluations. Applying FMQA to the problem requires converting nucleotides into binary variables. However, the influence of integer-to-nucleotide assignments and binary-integer encoding on the performance of FMQA has not been thoroughly investigated, even though such choices determine the structure of the surrogate model and the search landscape, and thus can directly affect solution quality. Therefore, this study aims both to establish a novel FMQA framework for RNA inverse folding and to analyze the effects of these assignments and encoding methods. We evaluated all 24 possible assignments of the four nucleotides to the ordered integers (0-3), in combination with four binary-integer encoding methods. Our results demonstrated that one-hot and domain-wall encodings outperform binary and unary encodings in terms of the normalized ensemble defect value. In domain-wall encoding, nucleotides assigned to the boundary integers (0 and 3) appeared with higher frequency. In the RNA inverse folding problem, assigning guanine and cytosine to these boundary integers promoted their enrichment in stem regions, which led to more thermodynamically stable secondary structures than those obtained with one-hot encoding.
Figures & tables
Figure 1: Overview of the RNA inverse folding problem. White circles represent arbitrary nucleotides in target secondary structure, and black lines indicate base pairs formed through hydrogen bonding. A, U, G, and C denote adenine, uracil, guanine, and cytosine, respectively.
Figure 2: Schematic illustration of the proposed FMQA for the RNA inverse folding problem. As an example, the BB function is defined as the NED.
Integer
Binary variable sequence
One-hot encoding
Domain-wall encoding
Binary encoding
Unary encoding
0
1000
000
00
000
1
0100
100
10
100, 010, 001
2
0010
110
01
110, 101, 011
3
0001
111
11
111
Table 1: Binary variable sequence representing integers I∈{0,1,2,3} under different binary-integer encoding methods.
Figure 3: Normalized ensemble defect values obtained by FMQA under different combinations of binary-integer encoding methods and integer-to-nucleotide assignments. Crosses indicate the average NED over 10 runs. The upper and lower whiskers denote the maximum and minimum NED values, respectively. Black circle, red triangle, blue square, and green diamond represent outliers. Panels in the top row correspond to assignments in which A or U was assigned to integer 0 , whereas panels in the bottom row correspond to assignments in which G or C was assigned to integer 0 .
Figure 4: Success rate obtained by FMQA under different combinations of binary-integer encoding methods and integer-to-nucleotide assignments. Panels in the top row correspond to assignments in which A or U was assigned to integer 0 , whereas panels in the bottom row correspond to assignments in which G or C was assigned to integer 0 .
Figure 5: Minimum free energy values obtained by FMQA under different combinations of binary-integer encoding methods and integer-to-nucleotide assignments. Only success solutions are plotted. When two or more success solutions were obtained, their average MFE value is indicated by a cross marker. When three or more success solutions were obtained, the standard deviation is shown as error bars. Panels in the top row correspond to assignments in which A or U was assigned to integer 0 , whereas panels in the bottom row correspond to assignments in which G or C was assigned to integer 0 .
Figure 6: Relationship between the number of BB function evaluations and the best normalized ensemble defect value up to each evaluation.
Figure 7: Target secondary structures selected from the Eterna100 benchmark and evaluated in this study. White circles represent nucleotides, and black lines indicate base pairs formed by hydrogen bonding. The target structures are: (a) G-C Placement ( 12 nt), (b) Simple Hairpin ( 16 nt), (c) Shortie 4 ( 17 nt), (d) stickshift ( 26 nt), (e) Small and Easy 6 ( 30 nt), (f) Corner bulge training ( 31 nt), (g) Prion Pseudoknot – Difficulty Level 0 ( 36 nt), and (h) infoRNA test 16 ( 36 nt).
Figure 8: Performance metrics on multiple Eterna100 benchmark target structures. (a) Normalized ensemble defect values obtained by FMQA for each target structure. Crosses indicate the average NED over 10 independent runs. The upper and lower whiskers denote the maximum and minimum NED values, respectively. Black circle and red triangle represent outliers. (b) Success rate. (c) Minimum free energy values. Only success solutions are plotted. When two or more success solutions were obtained, their average MFE value is indicated by a cross marker. When three or more success solutions were obtained, the standard deviation is shown as error bars.
Figure 9: Nucleotide frequencies obtained from the success solutions across different integer-to-nucleotide assignments. (a) Nucleotide frequency in stem regions, (b) nucleotide frequency in non-stem regions, and (c) nucleotide frequency over the entire RNA sequence. The baseline value of 0.25 corresponds to the expected frequency under a random uniform nucleotide frequency. Red indicates frequencies higher than 0.25, whereas blue indicates frequencies lower than 0.25.
Figure 10: Performance metrics for different values of the hyperparameter K under each binary-integer encoding method. (a) Normalized ensemble defect values obtained by FMQA for each encoding method and value of K . Crosses indicate the average NED over 10 independent runs. The upper and lower whiskers denote the maximum and minimum NED values, respectively. Black circle, red triangle, blue square, and green diamond represent outliers. (b) Success rate. (c) Minimum free energy values of the success solutions. Only success solutions are plotted. When two or more success solutions were obtained, their average MFE value is indicated by a cross marker. When three or more success solutions were obtained, the standard deviation is shown as error bars.
Graduate School of Science and Technology, Keio University, Kanagawa 223-8522, Japan · Keio University Sustainable Quantum Artificial Intelligence Center (KSQAIC), Keio University, Tokyo 108-8345, Japan · Department of Applied Physics and Physico-Informatics, Keio University, Kanagawa 223-8522, Japan +2
State Key Laboratory for Novel Software Technology at Nanjing University, School of Computer Science, Nanjing University · The Chinese University of Hong Kong · Stanford University