RNApuzzler: efficient outerplanar drawing of RNA-secondary structures

Motivation: RNA secondary structure is a useful representation for studying the function of RNA, which captures most of the free energy of RNA folding. Using empirically determined energy parameters, secondary structures of nucleic acids can be efficiently computed by recursive algorithms. Several software packages supporting this task are readily available. As RNA secondary structures are outerplanar graphs, they can be drawn without intersection in the plane. Interpretation by the practitioner is eased when these drawings conform to a series of additional constraints beyond outerplanarity. These constraints are the reason why RNA drawing is difficult. Many RNA drawing algorithms therefore do not always produce intersection-free (outerplanar) drawings. Results: To remedy this shortcoming we propose here the RNApuzzler algorithm which is guaranteed to produce intersection-free drawings. It is based on a drawing algorithm respecting constraints based on nucleotide distances (RNAturtle). We investigate relaxations of these constraints allowing for intersection-free drawings. Based on these relaxations, we implemented a fully automated, simple, and robust algorithm that produces aesthetic drawings adhering to previously established guidelines. We tested our algorithm using the RFAM database and found that we can compute intersection-free drawings of all RNAs therein efficiently. Availability and implementation: The software can be accessed freely at: https://github.com/dwiegreffe/RNApuzzler.