Improved Algorithms for Largest Cardinality 2-Interval Pattern Problem

The 2-

Interval Pattern problem

is to find the largest constrained pattern in a set of 2-intervals. The constrained pattern is a subset of the given 2-intervals such that any pair of them are

R

-comparable, where model

$R \subseteq \{<, \sqsubset, \between \}$

. The problem stems from the study of general representation of RNA secondary structures. In this paper, we give three improved algorithms for different models. Firstly, an

$O(n {\rm log} n+\mathcal{L})$

algorithm is proposed for the case

$R = \{\between\}$

, where

$\mathcal{L}$

=

O

(

dn

)=

O

(

n

2

) is the total length of all 2-intervals (density

d

is the maximum number of 2-intervals over any point). This improves previous

O

(

n

2

log

n

) algorithm. Secondly, we use dynamic programming techniques to obtain an

O

(

n

log

n

+

dn

) algorithm for the case

$R = \{ <, \sqsubset\}$

, which improves previous

O

(

n

2

) result. Finally, we present another

$O(n {\rm log} n + \mathcal{L})$

algorithm for the case

$R = \{\sqsubset, \between\}$

with disjoint support(interval ground set), which improves previous

$O(n^{2}\sqrt{n})$

upper bound.