Chaining Sequence/Structure Seeds for Computing RNA Similarity

Laetitia Bourgeade, Julien Allali and Cédric Chauve
Reference. Laetitia Bourgeade, Julien Allali and Cédric Chauve. 2014. Chaining Sequence/Structure Seeds for Computing RNA Similarity. Proceedings of 1st workshop on Computational Methods for Structural RNAs (CMSR'14). isbn:978-2-9550187-0-5. pp. 1-12. doi:10.15455/CMSR.2014.0001
Abstract. Motivation: The increasing understanding of the important roles played by non-coding RNAs in many cellular processes has motivated an intensive research on the accurate and efficient comparison of large sets of RNA genes using both sequence and secondary structure information.
Results: 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, then (iii) completing the alignment using an anchor-based exact alignment algorithm. We apply our method on the benchmark Bralibase 2.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 computes constraints that greatly improve computation time of LocaRNA and is comparable to the one of ExpLoc-P, while improving the overall accuracy of the final alignments.
Availability: RNA-unchained is available at
Presented at CMSR'14 (Strasbourg, France) on September 7th 2014 at 10:00 by Laetitia Bourgeade.

License information

Creative Commons LicenseThe proceedings of CMSR'14 are distributed under the terms of a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License. Ownership of the copyright for the articles is retained by their authors. They allow anyone to download, reuse, reprint, distribute, and/or copy articles for any non-commercial purposes, provided that the original authors and source are appropriately cited.