doi:10.1093/bioinformatics/btl194BIOINFORMATICS ORIGINAL PAPER Structural bioinformatics INFO-RNA—a fast approach to inverse RNA folding

Motivation: The structure of RNA molecules is often crucial for their function. Therefore, secondary structure prediction has gained much interest. Here, we consider the inverse RNA folding problem, which means designing RNA sequences that fold into a given structure. Results:We introduce a new algorithm for the inverse folding problem (INFO-RNA) that consistsof twoparts; adynamicprogrammingmethod for good initial sequences and a following improved stochastic local search that uses an effective neighbor selection method. During the initialization, we design a sequence that among all sequences adopts the given structure with the lowest possible energy. For the selection of neighbors during the search, we use a kind of look-ahead of one selec-tion step applying an additional energy-based criterion. Afterwards, the pre-ordered neighbors are tested using the actual optimization criterion ofminimizing thestructuredistancebetweenthe targetstructureand the mfe structure of the considered neighbor. We compared our algorithm to RNAinverse and RNA-SSD for artificial and biological test sets. Using INFO-RNA, we performed better than RNAinverse and in most cases, we gained better results than RNA-SSD, the probably best inverse RNA folding tool on the market