On the computational complexity of 2-interval pattern matching problems Export

@article{2-interval, abstract = {The focus of this paper is on the computational complexity of pattern matching problems over set of 2-intervals. These problems occur in the context of molecular biology when a structured pattern, i.e., a RNA secondary structure given in the form of a 2-interval pattern, has to be found in a sequence database. We show that finding a 2-interval pattern in a set of 2-intervals is a NP-complete problem even if no 2-interval of the pattern precedes the other, but can be solved in polynomial time for several interesting special cases. In particular, it is shown that the pseudo-knot free RNA secondary structure case is polynomial time solvable in our 2-interval formalism. Also, we investigate the computational complexity of finding the longest 2-interval pattern in a set of 2-intervals and prove several NP-completeness results as well as polynomial time solvable special cases.}, address = {Essex, UK}, author = {Vialette, St\'ephane}, citeulike-article-id = {4014531}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=980021}, citeulike-linkout-1 = {http://dx.doi.org/10.1016/j.tcs.2003.08.010}, doi = {10.1016/j.tcs.2003.08.010}, issn = {0304-3975}, journal = {Theor. Comput. Sci.}, keywords = {2-interval}, number = {2-3}, pages = {223--249}, posted-at = {2009-02-06 03:41:38}, priority = {2}, publisher = {Elsevier Science Publishers Ltd.}, title = {On the computational complexity of 2-interval pattern matching problems}, url = {http://dx.doi.org/10.1016/j.tcs.2003.08.010}, volume = {312}, year = {2004} }

TY - JOUR ID - 2-interval L3 - citeulike-article-id:4014531 N2 - The focus of this paper is on the computational complexity of pattern matching problems over set of 2-intervals. These problems occur in the context of molecular biology when a structured pattern, i.e., a RNA secondary structure given in the form of a 2-interval pattern, has to be found in a sequence database. We show that finding a 2-interval pattern in a set of 2-intervals is a NP-complete problem even if no 2-interval of the pattern precedes the other, but can be solved in polynomial time for several interesting special cases. In particular, it is shown that the pseudo-knot free RNA secondary structure case is polynomial time solvable in our 2-interval formalism. Also, we investigate the computational complexity of finding the longest 2-interval pattern in a set of 2-intervals and prove several NP-completeness results as well as polynomial time solvable special cases. IS - 2-3 JF - Theor. Comput. Sci. SN - 0304-3975 AD - Essex, UK EP - 249 TI - On the computational complexity of 2-interval pattern matching problems PB - Elsevier Science Publishers Ltd. VL - 312 SP - 223 KW - 2-interval AU - Vialette, St\'ephane PY - 2004/// UR - http://dx.doi.org/10.1016/j.tcs.2003.08.010 ER -