Sharper Upper and Lower Bounds for an Approximation Scheme for CONSENSUS-PATTERN.
Brona Brejova, Daniel G. Brown, Ian M. Harrower, A. López-Ortiz, Tomas Vinar. To appear in Proceedings of
16th Annual Symposium on Combinatorial Pattern Matching, (CPM), 2005.
PostScript file.
Abstract.
We present sharper upper and lower bounds for a known polynomial-time
approximation scheme due to Li, Ma and Wang for the CONSENSUS-PATTERN problem.
This NP-hard problem is an abstraction of motif finding, a common bioinformatics
discovery task. The PTAS due to Li et al. is simple, and a preliminary
implementation gave reasonable results in practice. However, the previously
known bounds on its performance are useless when runtimes are
actually manageable. Here, we present much sharper lower and upper bounds on
the performance of this algorithm that partially explain why its behavior is so
much better in practice than what was previously predicted in theory. We also
give specific examples of instances of the problem for which the PTAS performs poorly
in practice, and show that the asymptotic performance bound given in the original
proof matches the behaviour of a simple variant of the algorithm on a
particularly bad instance of the problem.