Yuan, Hao; Yang, Linji; Chen, Erdong 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]. Cited in 1 Document MSC: 68W05 Nonnumerical algorithms 68W40 Analysis of algorithms 92C40 Biochemistry, molecular biology 92D20 Protein sequences, DNA sequences PDFBibTeX XMLCite \textit{H. Yuan} et al., Lect. Notes Comput. Sci. 3827, 412--421 (2005; Zbl 1173.68840) Full Text: DOI