Brona Brejova, Daniel G. Brown, Ian M. Harrower, Alejandro Lopez-Ortiz, Tomas Vinar. Sharper Upper and Lower Bounds for an Approximation Scheme for CONSENSUS-PATTERN. In Alberto Apostolico, Maxime Crochemore, Kunsoo Park, ed., Combinatorial Pattern Matching, 16th Annual Symposium (CPM), 3537 volume of Lecture Notes in Computer Science, pp. 1-10, Jeju Island, Korea, June 19-22 2005. Springer.

Download preprint: 05ptas.pdf, 143Kb

Download from publisher: http://dx.doi.org/10.1007/11496656_1

Related www page: not available

Bibliography entry: BibTeX

See also: early version

Abstract:

We present sharper upper and lower bounds for a known polynomial-time 
approximation scheme due to Li, Ma and Wang 2002 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 by Liang 2001 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.

Last update: 10/01/2006