We describe a new method to compare a query RNA with a static set of target RNAs. Our method is based on (i) a static indexing of the sequence/structure seeds of the target RNAs; (ii) searching the target RNAs by detecting seeds of the query present in the target, chaining these seeds in promising candidate homologs; and then (iii) completing the alignment using an anchor-based exact alignment algorithm. We apply our method on the benchmark Bralibase2.1 and compare its accuracy and efficiency with the exact method LocARNA and its recent seeds-based speed-up ExpLoc-P. Our pipeline RNA-unchained greatly improves computation time of LocARNA and is comparable to the one of ExpLoc-P, while improving the overall accuracy of the final alignments.
Get full access to this article
View all access options for this article.
References
1.
AllaliJ., and SagotM.F.2008. A multiple layer model to compare RNA secondary structures. Softw. Pract. Exp. 38, 775–792.
AllaliJ., ChauveC., FerraroP., and GaillardA.L.2011. Efficient chaining of seeds in ordered trees. J. Discrete Algo., 14, 107–118.
4.
BlinG., DeniseA., DulucqS., et al.2010. Alignment of RNA structures. IEEE/ACM Trans. Comput. Biol. Bioinform., 7, 309–322.
5.
BrownD.G.2008. Chapter A: Survey of seeding for sequence alignment. In Bioinformatics Algorithms: Techniques and Applications. Wiley-Interscience, New York.
6.
EvansP.A.1999. Finding common subsequences with arcs and pseudoknots, 270–280. In Combinatorial Pattern Matching. Springer, New York.
7.
Griffiths-JonesS., BatemanA., MarshallM., et al.2003. Rfam: An RNA family database. Nucleic Acids Res. 31, 439–441.
8.
HochsmannM., TollerT., GiegerichR., and KurtzS.2003. Local similarity in RNA secondary structures. Proc. Comput. Syst. Bioinf, 2003, 159–168.
9.
JanssenS., ReederJ., and GiegerichR.2008. Shape based indexing for faster search of RNA family databases. BMC Bioinform., 9, 131.
10.
KerteszM., WanY., MazorE., et al.2010. Genome-wide measurement of RNA secondary structure in yeast. Nature, 467, 103–107.
11.
LorenzR., BernhartS.H., zu SiederdissenC.H., et al.2011. ViennaRNA Package 2.0. Algo. Mol. Biol., 6, 26.
SchmiedlC., MöhlM., HeyneS., et al.2012. Exact pattern matching for RNA structure ensembles, 245–260. In Proceedings of the 16th International Conference on Research in Computational Molecular Biology (RECOMB 2012). LNCS, volume 7262. Springer, Berlin.
14.
SteffenP., VoB., RehmsmeierM., et al.2006. RNAshapes: An integrated RNA analysis package based on abstract shapes. Bioinformatics, 22, 500–503.
15.
ThomasC.R., BennettD., JasnyB., et al.1992. The molecule of the year. Science, 258, 1861.
16.
ThompsonJ.D., PlewniakF., and PochO.1999. A comprehensive comparison of multiple sequence alignment programs. Nucleic Acids Res., 27, 2682–2690.
17.
WanY., KerteszM., SpitaleR.C., et al.2011. Understanding the transcriptome through RNA structure. Nat. Rev. Genet., 12, 641–655.
18.
WillS., ReicheK., HofackerI.L., et al.2007. Inferring non-coding RNA families and classes by means of genome-scale structure-based clustering. PLOS Comput. Biol., 3, e65.
19.
WilmA., MainzI., and StegerG.2006. An enhanced RNA alignment benchmark for sequence alignment programs. Algorithms Mol. Biol., 1, 19.
20.
ZhangK., and ShashaD.1989. Simple fast algorithms for the editing distance between trees and related problems. SIAM J. Comput. 18, 1245–1262.
21.
ZhongC., and ZhangS.2013. Efficient alignment of RNA secondary structures using sparse dynamic programming. BMC Bioinform., 14, 269.
22.
ZukerM., and StieglerP.1981. Optimal computer folding of large RNA sequences using thermodynamic and auxiliary information. Nucleic Acids Res., 9, 133–148.
