We study the computational complexity of pattern matching problems over 2-interval sets. These problems occur in the context of molecular biology when a structured pattern, i.e., a RNA secondary structure, has to be found in a sequence. We show that the Pattern
Matching
Over 2-Interval
Set problem is NP-complete for structured patterns where no pair precedes the other, but can be solved in polynomial time for several interesting
special cases.