ABSTRACT
Background
Current advances of the next-generation sequencing technology have revealed a large number of
un-annotated RNA transcripts. Comparative study of the RNA structurome is an important approach to assess their
biological functionalities. Due to the large sizes and abundance of the RNA transcripts, an efficient and accurate RNA
structure-structure alignment algorithm is in urgent need to facilitate the comparative study. Despite the importance
of the RNA secondary structure alignment problem, there are no computational tools available that provide high
computational efficiency and accuracy. In this case, designing and implementing such an efficient and accurate RNA
secondary structure alignment algorithm is highly desirable.
Results
In this work, through incorporating the sparse dynamic programming technique, we implemented an
algorithm that has an O(n^3) expected time complexity, where n is the average number of base pairs in the RNA
structures. This complexity, which can be shown assuming the polymer-zeta property, is confirmed by our
experiments. The resulting new RNA secondary structure alignment tool is called ERA. Benchmark results indicate
that ERA can significantly speedup RNA structure-structure alignments compared to other state-of-the-art RNA alignment tools, while maintaining high alignment accuracy.
Conclusions
Using the sparse dynamic programming technique, we are able to develop a new RNA secondary
structure alignment tool that is both efficient and accurate. We anticipate that the new alignment algorithm
ERA will significantly promote comparative RNA structure studies. The program, ERA, is freely available from this website.
Full Article
README
ERA: ERA is an RNA structure alignment tool that aims at fast comparison of RNA secondary structures. The input of RNA structures should contain explicitly annotated base pairs and be pseudo-knot free. The outputs of ERA are the structure similarity score and detailed alignment. The average time complexity is ERA is O(n^3) and the average space complexity is O(n^2).
Compilation: ERA has been developed and tested under Linux system (RedHat and Ubuntu). Type 'make' to compile.
Usage:
Input: The inputs of ERA are two RNA structures in Vienna format. Please see ./example for sample inputs.
Running ERA:
Try: "./ERA -i ./examples/tRNA1.vrna -j ./examples/tRNA2.vrna"
Other parameter options can be found using "./ERA -h"
Version: The current version of ERA is 1.0.
DOWNLOADS