LinearFold: linear-time approximate RNA folding by 5'-to-3' dynamic programming and beam search

“Widely used systems such as RNAstructure (Mathews and Turner, 2006), Vienna RNAfold (Lorenz etal.”

“8% of the optimal structure (Zuker et al., 1991; Mathews et al., 1999).”

“The dual nature of RNA as both a genetic material and functional molecule led to the RNA World hypothesis, that RNA was the first moleculeoflife(Gilbert,1986), andthisdualnaturehasalsobeenutilized to develop in vitro methods to evolve functional sequences (Joyce, 1994).”

“This is analogous to psycholinguistic evidence that humans incrementally parse a sentence before it is fully read or heard (Frazier and Rayner, 1982).”

“In particular, we demonstrate two versions of LinearFold, LinearFold-V using the thermodynamic free energy model (Mathews et al., 2004) from Vienna RNAfold (Lorenz et al.”

“Ribonucleicacid(RNA)isinvolvedinnumerouscellularprocesses(Eddy, 2001).”

“Since experimentally determining the structure is expensive and time comsuming, and given the overwhelming increase in genomic data (about 1021 base-pairs per year) (Stephens et al., 2015), computational methods have been widely used as an alternative to automatically predict the structure.”

“…function and base pair probabilities for natural RNA sequences with well-defined structures, since the classical method for that task, the McCaskill (1990) algorithm, is isomorphic in structure to the cubic-time algorithms that are used as baselines in this paper.”

“1965; Younger, 1967), has a running time of O ( n 3 ) that scales cubically with the sequence length n , which is too slow for long RNA sequences (Lange et al. , 2012).”

“,≤700nt) and predict structures within each segment only (Watts et al., 2009; Andronescu et al., 2007; Licon et al., 2010).”

“1, from the NONCODE database (Zhao et al., 2016)).”

“Individually, LinearFold-C (the LinearFold implementation of the CONTRAfold model) is significantly more accurate in sensitivity than CONTRAfold on one family (Group I Intron), and both PPV/sensitivity on two families (16S and 23S ribosomal RNAs), with the last two being the longest families in this dataset, where they…”

“, 2009), all use virtually the same dynamic programming (DP) algorithm (Nussinov et al. , 1978; Zuker and Stiegler, 1981) to find the best-scoring (lowest free energy, maximum expected accuracy, or best model score) structure (Mathews and Turner, 2006; Washietl et al. , 2012).”

“Widely used systems such as RNAstructure (Mathews and Turner, 2006), Vienna RNAfold (Lorenz etal.”

“, 2006) and CentroidFold (Sato et al., 2009), all use virtually the same dynamic programming (DP) algorithm (Nussinov et al.”

“…replacing the cubic-time McCaskill algorithm with a linear-time one in those heuristic pseudoknot-prediction programs (Bellaousov and Mathews, 2010; Sato et al. , 2011), or linearizing a supercubic-time dynamic program for direct prediction with pseudoknots (Dirks and Pierce, 2003; Reeder and…”

“Finally, our LinearFold algorithm resembles cotranscriptional folding where RNA molecules start to fold immediately before being fully transcribed (Gultyaev et al., 1995; Meyer and Miklos, 2004).”

“, 2015)tothedesignofoligonucleotidesforknockdownofmessage(Luand Mathews, 2008; Tafer et al. , 2008).”

“, 2011), or linearizing a supercubic-time dynamic program for direct prediction with pseudoknots (Dirks and Pierce, 2003; Reeder and Giegerich, 2004).”

“On top of beam search, we borrow k-best parsing (Huang and Chiang, 2005) to reduce the runtime to O(nb log b).”

“It is able to fold the longest sequence in RNAcentral (244 296nt) within 3 min, while neither CONTRAfold or RNAfold runs on anything longer than 32 767nt due to datastructure limitations.”

“ThereisacrucialdifferencebetweenourLinearFoldandlocalfolding algorithms (Kiryu et al. , 2008; Bernhart et al. , 2006; Lange et al. , 2012) that can only predict pairs up to a certain distance.”

“…of pseudoknots, by either replacing the cubic-time McCaskill algorithm with a linear-time one in those heuristic pseudoknot-prediction programs (Bellaousov and Mathews, 2010; Sato et al. , 2011), or linearizing a supercubic-time dynamic program for direct prediction with pseudoknots (Dirks and…”

“For example, it was well studied that while the lowest free energy structure contains only 72.9%oftheactualbasepairs(givenadataset), astructurecontaining 86.1% of them can be found with a free energy within 4.8% of the optimal structure (Zuker et al. , 1991; Mathews et al. , 1999).”

“,2007; Gareiss et al. , 2008; Castanotto and Rossi, 2009; Palde et al. , 2010).”

“We will test the hypothesis that our beams potentially capture cotranscriptional folding with empirical data on cotranscriptional folding (Watters et al., 2016).”

“1A), is an important and challenging problem (Seetin and Mathews, 2012; Hofacker and Lorenz, 2014).”

“ThereisacrucialdifferencebetweenourLinearFoldandlocalfolding algorithms (Kiryu et al. , 2008; Bernhart et al. , 2006; Lange et al. , 2012) that can only predict pairs up to a certain distance.”

“The dual nature of RNA as both a genetic material and functional molecule led to the RNA World hypothesis, that RNA was the first moleculeoflife(Gilbert,1986), andthisdualnaturehasalsobeenutilized to develop in vitro methods to evolve functional sequences (Joyce, 1994).”

“Furthermore, RNA is an important drug target and agent (Angelbello et al., 2018; Sazani et al., 2002; Crooke, 2004; Childs-Disney et al., 2007; Gareiss et al., 2008; Castanotto and Rossi, 2009; Palde et al., 2010).”

“…sensitivity (the fraction of known pairs predicted) oneachRNAfamilyintheArchiveIIdataset, allowingcorrectlypredicted pairs to be offset by one position for one nucleotide as compared to the known structure (Sloma and Mathews, 2016); we also report exact match accuracies in Supplementary Table SI2.”

“All these local methods omit long-range base pairs, which theoretical and experimental studies have demonstrated to be common in naturalRNAs, especiallybetweenthe5’and3’ends(SeetinandMathews, 2012; Lai et al. , 2018; Li and Reidys, 2018).”

“We hypothesize that some RNA sequences have evolved to fold co-transcriptionally (Meyer and Miklós, 2004), thus making our 50-to-30 incremental approach more accurate than bottom-up baselines.”

“, 2009), all use virtually the same dynamic programming (DP) algorithm (Nussinov et al. , 1978; Zuker and Stiegler, 1981) to find the best-scoring (lowest free energy, maximum expected accuracy, or best model score) structure (Mathews and Turner, 2006; Washietl et al. , 2012).”

“While this naive version runsintheexponentialtimeof O (3 n ) ,weborrowanefficientpackingidea from computational linguistic (Tomita, 1988) that reduces the runtime back to O ( n 3 ) .”

“Furthermore, RNA is an important drug target and agent (Angelbello et al., 2018; Sazani et al., 2002; Crooke, 2004; Childs-Disney et al., 2007; Gareiss et al., 2008; Castanotto and Rossi, 2009; Palde et al., 2010).”

“Theoretical and empirical studies found several evidences that unboundedly long-distance pairs are actually quite common in natural RNA structures: (a) the length of the longest base pair grows nearly linearly with sequence length n (Li and Reidys, 2018); (b) the physical distance between the 5’–3’ ends in folded stru…”

“We test statistical significance using a paired, one-sided permutation test, following (Aghaeepour and Hoos, 2013).”

“1A), is an important and challenging problem (Seetin and Mathews, 2012; Hofacker and Lorenz, 2014).”

“There are other algorithmic efforts to speed up RNA folding, including an O n3= log n algorithm using the Four-Russians method (Venkatachalam et al., 2014), and two other sub-cubic algorithms inspired by fast matrix multiplication and context-free parsing (Bringmann et al., 2016; Zakov et al.,…”

“, 2014), and two other sub-cubic algorithms inspired by fast matrix multiplication and context-free parsing (Zakov et al., 2011; Bringmann et al., 2016).”

“There also exists a linear-time algorithm (Rastegari and Condon, 2005) to analyze a given structure, but not to predict one de novo.”

“All these local methods omit long-range base pairs, which theoretical and experimental studies have demonstrated to be common in natural RNAs, especially between the 50 and 30 ends (Lai et al., 2018; Li and Reidys, 2018; Seetin and Mathews, 2012).”

“In terms of RNA secondary structure prediction, RNA-FM outperforms LinearFold by up to 30% and SPOT-RNA by up to 20% in terms of F1 score on cross-dataset validation.”