A 2-approximation for the preceding-and-crossing structured 2-interval pattern problem

摘要

The 2-interval pattern problem over its various models and restrictions was proposed by Vialette (2004) for the application of RNA secondary structure prediction. We present an O(n 3logn)-time 2-approximation algorithm for the problem of finding a largest { < , ${<,between}$ -structured subset of 2-intervals given an input 2-interval set of size n. This greatly improves the previous best approximation ratio of 6 by Crochemore et al. (2005).