title: Chaining sequence/structure seeds for computing RNA similarity.
abstract: 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.
authors.affiliation: 1 LaBRI, Bordeaux University , Talence, France .
authors.forename: Laetitia
authors.initials: L
authors.lastname: Bourgeade
authors.forename: Cédric
authors.initials: C
authors.lastname: Chauve
authors.forename: Julien
authors.initials: J
authors.lastname: Allali
mesh_terms: D000465:Algorithms; D001483:Base Sequence; D003198:Computer Simulation; D008958:Models, Molecular; D009690:Nucleic Acid Conformation; D012313:RNA / Q000737:chemistry; D017423:Sequence Analysis, RNA
chemical_list: D012313:RNA
keywords: RNA; algorithms; combinatorial optimization; dynamic programming; genomic rearrangements; secondary structure; sequence analysis; structures; suffix trees