Back to Search
Start Over
A PTAS for the Weighted 2-Interval Pattern Problem over the Preceding-and-Crossing Model.
- Source :
- Combinatorial Optimization & Applications; 2007, p378-387, 10p
- Publication Year :
- 2007
-
Abstract
- The 2-Interval Pattern problem over its various models and restrictions was proposed by Vialette for RNA secondary structure prediction, and has attracted a lot of attention from the theoretical computer science community in recent years. In the framework of 2-intervals, the preceding-and-crossing model is an especially interesting model for RNA secondary structures with pseudoknots. In this paper, we present a polynomial time approximation scheme for the Weighted 2-Interval Pattern problem over the preceding-and-crossing model. Our algorithm improves the previous best 2-approximation algorithm, and closes this problem in terms of the approximation ratio. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISBNs :
- 9783540735557
- Database :
- Complementary Index
- Journal :
- Combinatorial Optimization & Applications
- Publication Type :
- Book
- Accession number :
- 33108618
- Full Text :
- https://doi.org/10.1007/978-3-540-73556-4_39