RNA folding pathways and kinetics using 2D energy landscapes (Q2512926)

The authors introduce a novel algorithm for determining the 2D projection of the energy landscape, which has the potential to facilitate the identification of RNA folding pathways. The paper commences with a description of the role and importance of RNA folding pathways and introduces, in the preliminary section, the basic concepts used throughout the paper. The presentation of the algorithm starts with the detailed description of the polynomial interpolation using the fast Fourier transform, which includes the recursions for computing the polynomial \(Z_{i,j}(x)\), the actual polynomial interpolation and the complexity reduction achieved by the precomputation of powers of the complex roots of unity. This improvement leads to a reduction of runtime complexity from \(O(n^7)\) to \(O(n^5)\) and space complexity from \(O(n^4)\) to \(O(n^2)\). The authors also include a benchmarking between RNA2Dfold and FFTbor2D and a detailed description of the folding kinetics along the 2D energy grid.