Approximate matching of structured motifs in DNA sequences.
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.
El-Mabrouk
Nadia
N
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
Raffinot
Mathieu
M
Duchesne
Jean-Eudes
JE
Lajoie
Mathieu
M
Luc
Nicolas
N
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
D012343:RNA, Transfer