title: Approximate matching of structured motifs in DNA sequences.
abstract: Several methods have been developed for identifying more or less complex RNA structures in a genome. All these methods are based on the search for conserved primary and secondary sub-structures. In this paper, we present a simple formal representation of a helix, which is a combination of sequence and folding constraints, as a constrained regular expression. This representation allows us to develop a well-founded algorithm that searches for all approximate matches of a helix in a genome. The algorithm is based on an alignment graph constructed from several copies of a pushdown automaton, arranged one on top of another. This is a first attempt to take advantage of the possibilities of pushdown automata in the context of approximate matching. The worst time complexity is O(krpn), where k is the error threshold, n the size of the genome, p the size of the secondary expression, and r its number of union symbols. We then extend the algorithm to search for pseudo-knots and secondary structures containing an arbitrary number of helices.
authors.affiliation: Département d'informatique et de recherche opérationnelle, Université de Montréal, CP 6128 Succursale Centre-ville, Montréal, Québec H3C 3J7. mabrouk@iro.umontreal.ca
authors.forename: Nadia
authors.initials: N
authors.lastname: El-Mabrouk
authors.forename: Mathieu
authors.initials: M
authors.lastname: Raffinot
authors.forename: Jean-Eudes
authors.initials: JE
authors.lastname: Duchesne
authors.forename: Mathieu
authors.initials: M
authors.lastname: Lajoie
authors.forename: Nicolas
authors.initials: N
authors.lastname: Luc
mesh_terms: D000465:Algorithms; D001185:Artificial Intelligence; D016384:Consensus Sequence; D010363:Pattern Recognition, Automated / Q000379:methods*; D012343:RNA, Transfer / Q000235:genetics*; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*; D017423:Sequence Analysis, RNA / Q000379:methods*; D017386:Sequence Homology, Amino Acid
chemical_list: D012343:RNA, Transfer