×

Improved algorithms for largest cardinality 2-interval pattern problem. (English) Zbl 1173.68840

Deng, Xiaotie (ed.) et al., Algorithms and computation. 16th international symposium, ISAAC 2005, Sanya, Hainan, China, December 19–21, 2005. Proceedings. Berlin: Springer (ISBN 3-540-30935-7/pbk). Lecture Notes in Computer Science 3827, 412-421 (2005).
Summary: The 2-Intervall 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 \(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. First, an \(O(n\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. Second, 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\log n+\mathcal L)\) algorithm for the case \(R = \{\sqsubset,\between\}\) with disjoint support(interval ground set), which improves the previous \(O(n^2\sqrt n)\) upper bound.
For the entire collection see [Zbl 1098.68001].

MSC:

68W05 Nonnumerical algorithms
68W40 Analysis of algorithms
92C40 Biochemistry, molecular biology
92D20 Protein sequences, DNA sequences
PDFBibTeX XMLCite
Full Text: DOI