Approximate matching of structured motifs in DNA sequences

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Identifying RNA structures is crucial for understanding gene regulation and function.
• Existing methods often rely on conserved primary and secondary substructures.
• A need exists for efficient algorithms to detect complex RNA motifs within large genomes.

Purpose of the Study:

• To present a formal representation of RNA helices as constrained regular expressions.
• To develop a novel algorithm for approximate matching of helices in genomic sequences.
• To extend the algorithm for detecting pseudo-knots and complex secondary structures.

Main Methods:

• Formal representation of helices using constrained regular expressions.
• Development of an algorithm based on an alignment graph of pushdown automata.
• Analysis of worst-case time complexity: O(krpn).
• Extension of the algorithm to include pseudo-knots and multi-helix structures.

Main Results:

• A well-founded algorithm for approximate helix matching in genomes is established.
• The algorithm leverages pushdown automata for enhanced pattern matching.
• The computational complexity is formally defined, providing performance insights.
• The approach is extended to identify more complex RNA structures.

Conclusions:

• The proposed constrained regular expression and pushdown automaton approach offers an effective method for RNA structure identification.
• This work represents a significant step in applying automata theory to approximate RNA motif searching.
• The developed algorithm provides a foundation for more sophisticated RNA structure prediction tools.