Abstract
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, \mathtt{(\hspace{-3.5pt})} \}\). 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{log} n +L) algorithm is proposed for the case \(R= \{ \mathtt{(\hspace{-3.5pt})} \} \), where \({\cal 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 2log n) algorithm. Secondly, we use dynamic programming techniques to obtain an O(nlog n + dn) algorithm for the case R = { <, ⊏ }, which improves previous O(n 2) result. Finally, we present another\(O(n {\rm log} n +{\cal L})\) algorithm for the case \(R = \{\sqsubset, \mathtt{(\hspace{-3.5pt})} \}\) with disjoint support(interval ground set), which improves previous O(n 2□n) upper bound.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Alber J, Gramm J, Guo J, Niedermeier R (2004) Computing the similarity of two sequences with nested arc annotations. Theor Comput Sci 312(2–3):337–358
Bar-Yehuda R, Halldórsson MM, Naor J, Shachnai H, Shapira I (2002) Scheduling split intervals. In: Proceedings of the 13th annual ACM-SIAM symposium on discrete algorithms, pp 732–741
Blin G, Fertin G, Vialette S (2004) New results for the 2-interval pattern problem. In: Combinatorial pattern matching, 15th annual symposium, CPM 2004, proceedings, Springer, pp 311–322. ISBN 3-540-22341-X
Crochemore M, Hermelin D, Landau GM, Vialette S (2005) Approximating the 2-interval pattern problem. In: ESA, pp 426–437
Evans PA (1999) Finding common subsequences with arcs and pseudoknots. In: Crochemore M, Paterson M (eds) Combinatorial pattern matching, 10th annual symposium, CPM 99, proceedings, Springer, pp 270–280. ISBN 3-540-66278-2
Felsner S, Müller R, Wernisch L (1997) Trapezoid graphs and generalizations, geometry and algorithms. Discr Appl Math 74(1):13–32
Golumbic M (1980) Algorithmic graph theory and perfect graphs. Academic Press, New York, NY
Gramm J (2004) A polynomial-time algorithm for the matching of crossing contact-map patterns. In: Algorithms in bioinformatics, 4th international workshop, WABI 2004, proceedings, Springer, pp 38–49. ISBN 3-540-23018-1
Hopcroft JE, Karp RM (1973) An ún 5/2ú algorithm for maximum matchings in bipartite graphs. SIAM J Comput (4)
Jiang T, Lin G, Ma B, Zhang K (2004) The longest common subsequence problem for arc-annotated sequences. J. Discr Algor 2(2):257–270
Masuda S, Nakajima K, Kashiwabara T, Fujisawa T (1990) Efficient algorithms for finding maximum cliques of an overlap graph. Networks 20:157–171
Micali S, Vazirani V (1980) An úO(\(|{{\sqrt{V}||}}E|\))ú algorithm for finding maximum matching in general graphs. In: Proceedings of the 21st annual symposium on foundation of computer science, IEEE, pp 17–27
Valiente G (2003) A new simple algorithm for the maximum-weight independent set problem on circle graphs. In: Algorithms and computation, 14th international symposium, ISAAC 2003, proceedings, Springer, pp 129–137. ISBN 3-540-20695-7
Vialette S (2004) On the computational complexity of 2-interval pattern matching problems. Theor Comput Sci 312(2–3):223–249
Author information
Authors and Affiliations
Corresponding author
Additional information
A preliminary version of this article appears in Proceedings of the 16th Annual International Symposium on Algorithms and Computation, Springer LNCS, Vol. 3827, pp. 412–421, Hainan, China, December 19–21, 2005.
Rights and permissions
About this article
Cite this article
Chen, E., Yang, L. & Yuan, H. Improved algorithms for largest cardinality 2-interval pattern problem. J Comb Optim 13, 263–275 (2007). https://doi.org/10.1007/s10878-006-9030-8
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-006-9030-8