Approximating the 2-interval pattern problem. (English) Zbl 1142.68070
Summary: We address the issue of approximating the 2-interval pattern problem over its various models and restrictions. This problem, motivated by RNA secondary structure prediction, asks to find a maximum cardinality subset of a 2-interval set with respect to some prespecified geometric constraints. We present several constant factor approximation algorithms whose performance guarantee depends on the different possible restrictions imposed on the input 2-interval set. In addition, we show that our results extend to the weighted variant of the problem.
MSC:
| 68W20 | Randomized algorithms |
References:
| [1] | Akutsu, T., Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots, Discrete Applied Mathematics, 104, 45-62 (2000) · Zbl 0956.92019 |
| [2] | Bar-Noy, A.; Bar-Yehuda, R.; Freund, A.; Naor, J.; Shieber, B., A unified approach to approximating resource allocation and schedualing, Journal of the ACM, 48, 5, 1069-1090 (2001) · Zbl 1323.68564 |
| [3] | Bar-Yehuda, R., One for the price of two: A unified approach for approximating covering problems, Algorithmica, 27, 2, 131-144 (2000) · Zbl 0951.68177 |
| [4] | Bar-Yehuda, R.; Even, S., A local-ratio theorem for approximating the weighted vertex cover problem, Annals of Discrete Mathematics, 25, 27-46 (1985) · Zbl 0557.90072 |
| [5] | R. Bar-Yehuda, M.M. Halldorsson, J. Naor, H. Shachnai, I. Shapira, Scheduling split intervals, in: Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002, pp. 732-741; R. Bar-Yehuda, M.M. Halldorsson, J. Naor, H. Shachnai, I. Shapira, Scheduling split intervals, in: Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002, pp. 732-741 · Zbl 1093.68548 |
| [6] | G. Blin, G. Fertin, S. Vialette, New results for the 2-interval pattern problem, in: Proceedings of the 15th Annual Symposium on Combinatorial Pattern Matching, CPM 2004, pp. 311-322; G. Blin, G. Fertin, S. Vialette, New results for the 2-interval pattern problem, in: Proceedings of the 15th Annual Symposium on Combinatorial Pattern Matching, CPM 2004, pp. 311-322 · Zbl 1103.68059 |
| [7] | Dagan, I.; Golumbic, M. C.; Pinter, R. Y., Trapezoid graphs and their coloring, Discrete Applied Mathematics, 21, 35-46 (1988) · Zbl 0658.05067 |
| [8] | P. Evans, Finding common subsequences with arcs and pseudoknots, in: Proceedings of the 10th Annual Symposium on Combinatorial Pattern Matching, CPM 1999, pp. 270-280; P. Evans, Finding common subsequences with arcs and pseudoknots, in: Proceedings of the 10th Annual Symposium on Combinatorial Pattern Matching, CPM 1999, pp. 270-280 · Zbl 1063.68616 |
| [9] | Felsner, S.; Müller, R.; Wernisch, L., Trapezoid graphs and generalizations: Geometry and algorithms, Discrete Applied Mathematics, 74, 13-32 (1997) · Zbl 0877.68093 |
| [10] | Gavril, F., Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph, SIAM Journal on Computing, 1, 180-187 (1972) · Zbl 0227.05116 |
| [11] | D. Goldman, S. Istrail, C.H. Papadimitriou, Algorithmic aspects of protein structure similarity, in: Proceedings of the 40th Annual Symposium of Foundations of Computer Science, FOCS 1999, pp. 512-522; D. Goldman, S. Istrail, C.H. Papadimitriou, Algorithmic aspects of protein structure similarity, in: Proceedings of the 40th Annual Symposium of Foundations of Computer Science, FOCS 1999, pp. 512-522 |
| [12] | Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press New York · Zbl 0541.05054 |
| [13] | J. Gramm, J. Guo, R. Niedermeier, Pattern matching for arc-annotated sequences, in: Proceedings of the 22th Conference on Foundations of Software Technology and Theoretical Computer Science, FCTTSC 1999, pp. 182-193; J. Gramm, J. Guo, R. Niedermeier, Pattern matching for arc-annotated sequences, in: Proceedings of the 22th Conference on Foundations of Software Technology and Theoretical Computer Science, FCTTSC 1999, pp. 182-193 · Zbl 1027.68653 |
| [14] | Griggs, J. R.; West, D. B., Extremal values of the interval number of a graph, SIAM Journal of Algebraic and Discrete Methods, 1, 1-7 (1979) · Zbl 0499.05033 |
| [15] | S. Ieong, M.Y. Kao, T.W. Lam, W.K. Sung, S.M. Yiu, Predicting RNA secondary structures with arbitrary pseudoknots by maximizing the number of stacking pairs, in: Proceedings of the 2nd Symposium on Bioinformatics and Bioengineering, BIBE 2002, pp. 183-190; S. Ieong, M.Y. Kao, T.W. Lam, W.K. Sung, S.M. Yiu, Predicting RNA secondary structures with arbitrary pseudoknots by maximizing the number of stacking pairs, in: Proceedings of the 2nd Symposium on Bioinformatics and Bioengineering, BIBE 2002, pp. 183-190 |
| [16] | Lyngsø, R. B.; Pedersen, C. N.S., RNA pseudoknot prediction in energy based models, Journal of Computational Biology, 7, 409-428 (2000) |
| [17] | McKee, T. A.; McMorris, F. R., Topics in intersection graph theory, SIAM Monographs on Discrete Mathematics and Applications (1999) · Zbl 0945.05003 |
| [18] | Moore, P. B., Structural motifs in RNA, Annual Review of Biochemistry, 68, 287-300 (1999) |
| [19] | Trotter, W. T.; Harary, F., On double and multiple interval graphs, Journal of Graph Theory, 3, 205-211 (1979) · Zbl 0417.05050 |
| [20] | Vialette, S., On the computational complexity of 2-interval pattern matching problems, Theoretical Computer Science, 312, 335-379 (2004) |
| [21] | Waterman, M. S., Introduction to Computational Biology. Maps, Sequences and Genomes (1995), Chapman and Hall: Chapman and Hall London · Zbl 0831.92011 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
