1. A PTAS for the Weighted 2-Interval Pattern Problem over the Preceding-and-Crossing Model.
- Author
-
Hutchison, David, Kanade, Takeo, Kittler, Josef, Kleinberg, Jon M., Mattern, Friedemann, Mitchell, John C., Naor, Moni, Nierstrasz, Oscar, Pandu Rangan, C., Steffen, Bernhard, Sudan, Madhu, Terzopoulos, Demetri, Tygar, Doug, Vardi, Moshe Y., Weikum, Gerhard, Dress, Andreas, Xu, Yinfeng, Zhu, Binhai, and Jiang, Minghui
- 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]
- Published
- 2007
- Full Text
- View/download PDF