Approximating the 2-interval pattern problem

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.

Authors

• Maxime Crochemore
• Danny Hermelin
• Gad M. Landau
• Dror Rawitz
• Stéphane Vialette

Keywords

• 2-interval
• RNA secondary structure prediction
• Combinatorial approximation algorithms