A 2-approximation for the preceding-and-crossing structured 2-interval pattern problem |
| |
Authors: | Minghui Jiang |
| |
Institution: | (1) Department of Computer Science, Utah State University, Logan, Utah 84322-4205, USA |
| |
Abstract: | 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 { < , -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). |
| |
Keywords: | 2-Interval Approximation algorithms RNA secondary structure prediction |
本文献已被 SpringerLink 等数据库收录! |