Send to

Choose Destination
J Comput Biol. 2015 Mar;22(3):205-17. doi: 10.1089/cmb.2014.0283.

Chaining sequence/structure seeds for computing RNA similarity.

Author information

1 LaBRI, Bordeaux University , Talence, France .


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.


RNA; algorithms; combinatorial optimization; dynamic programming; genomic rearrangements; secondary structure; sequence analysis; structures; suffix trees

Comment in

[Indexed for MEDLINE]

Supplemental Content

Full text links

Icon for Atypon
Loading ...
Support Center