Ribonucleic acid (RNA) is a very special organic molecule. Understanding the structural repertoire of RNA secondary motifs is a very hot and active research area. Many people have come up with different novel representations for RNA secondary structures, and they have used them to classify or to find missing motifs.

The authors have used based pairing to introduce the idea of 2-intervals. If we consider RNA as a line consisting of contiguous bases A, C, G, and U, then an interval is a contiguous base on this line, and a 2-interval is the disjoint union of two intervals on this line. Given a collection of 2-intervals D, for which two 2-intervals that do not intersect at any point can be in precedence order (<), allowed to nest, or allowed to cross, the authors define a model R based on the above three. The problem of finding the largest 2-interval pattern in a set of 2-intervals D, with respect to a given abstract model R, is called the 2-interval pattern problem (2-IPP).

In this paper, the authors focus on the three special cases of the 2-IPP: the 2-intervals of the solution subset need to be pairwise nested; the 2-intervals in a solution can only be nested or crossing, and all the intervals involved in the 2-interval set D are disjoint; and the 2-intervals in a solution can only be nested or in precedence, and all the intervals involved in the 2-interval set D have the same length. The 2-IPP complexity results are summarized in Table 1 of the paper.

I think this is a very good paper for pattern matching over RNA secondary structures.