We present a general setting for structure-sequence comparison in a large class of RNA structures, that unifies and generalizes a number of recent works on specific families of structures. Our approach is based on a {em tree decomposition} of structures, and gives rise to a general parameterized algorithm having complexity in O(N m^t)$, where N (resp. m) is the structure (resp. sequence) length, and the exponent t depends on the family of structures. For each family considered by previous approaches, our contribution specializes into an algorithm whose complexity either matches or outperforms previous solutions.



Keyword
  ° Algorithms
  ° Bioinformatics

Group
  ° Bioinformatics

Contact
  ° DENISE Alain