What is approximation factor for the Greedy Motif Search algorithm?
I couldn't find an answer to my question except for the fact that the algorithm has a unknown aproximation factor. I'm not a native speaker and there is almost nothing about it available in my first language which makes it really hard to even understand the definition of the "approximation factor" which may lead to this question that could be rather obvious to answer.
A possible algorithm is shown on page 4: http://veda.cs.uiuc.edu/courses/fa08/cs466/lectures/Lecture5.pdf
I know that there isn't a known approximation factor because sources like the book "An Introduction to Bioinformatics Algorithms" are stating it.
I haven't really formed thoughts on it, because I'm not certainly sure what the definition of approximation factor is in a case like this. What I mean is: "The approximation ratio, or performance guarantee of algorithm A is defined as its maximum approximation ratio over all inputs of size n".
I would've thought that it may be unknown due to the fact that we could have a input of infinite, which is probably not the right thought in this regard. Another thought I had was that the algorithm has no lower bound for the optimal solution.