2
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ veda.cs.uiuc.edu/courses/fa08/cs466/lectures/Lecture5.pdf page 4 shows a possible pseudocode of the greedy motif search algorithm that I´m talking about $\endgroup$
    – Y.y.y-a-ea-
    Commented May 8, 2019 at 16:37
  • 1
    $\begingroup$ @Evil sorry I forgot to mention your name so you probably couldn´t see my answer $\endgroup$
    – Y.y.y-a-ea-
    Commented May 8, 2019 at 16:44
  • $\begingroup$ It would help to edit the question to provide that information in the question. We want people to understand what you are asking, without needing to read the comments. $\endgroup$
    – D.W. ♦
    Commented May 8, 2019 at 16:54
  • $\begingroup$ Also, why do you think there is no approximation factor for that algorithm? What are your thoughts? Do you think there should be an approximation factor? Why? $\endgroup$
    – D.W. ♦
    Commented May 8, 2019 at 16:55
  • $\begingroup$ @D.W. I edited my thread/post a little bit now so it should provide a bit more information on my thoughts and my problem + the source that I´ve used. $\endgroup$
    – Y.y.y-a-ea-
    Commented May 8, 2019 at 17:09

1 Answer 1

Reset to default
1
$\begingroup$

Quoting Master’s Thesis in Computer Science by Finn Rosenbech Jensen0, Dec. 2010, Greedy Motif algorithm approximation factor, using common superstring1 and its linear approximation2, was proved it cannot be better then 2.
Using proof by Kaplan and Shafir3 author shows that $\mid t_{greedy}\mid = 3.5 * OPT(S)$.

[0]: Master thesis by Rosenbech Jensen
[1]: Tarhio, J. and E. Ukkonen (1988). A greedy approximation algorithm for constructing shortest common superstrings.Theor. Comput. Sci. 57(1),131–145.
[2]: Blum, A., T. Jiang, M. Li, J. Tromp, and M. Yannakakis (1994, May).Linear approximation of shortest superstrings. InProceedings of the23rd Annual ACM Symposium on Theory of Computing, pp. 328–336. [3]: Kaplan, H. and N. Shafrir (2005). The greedy algorithm for shortest su-perstrings.Inf. Process. Lett. 93(1), 13–17.

Improve this answer
$\endgroup$
6
  • $\begingroup$ The problem is that the algorithm used here, isn´t the same that I used for my question :/ $\endgroup$
    – Y.y.y-a-ea-
    Commented May 8, 2019 at 17:28
  • $\begingroup$ Sorry, at the time of writing there was no algorithm, so I took some, with pseudocode and proof. The two algorithms differ only by linear factor in runtime (still both are fast and polynomial instead of exponential like exhaustive search) and another difference is that your example looks carefully for first two matches, quoted one is a bit more meticulous, which slightly affects runtime and slightly affects approximation factor. $\endgroup$
    – Evil
    Commented May 8, 2019 at 17:39
  • $\begingroup$ Yeah I´m sorry I didn´t provided the exact algorithm earlier and I´m thankful that you found the approximation factor for a similiar algorithm, but now I´m even more confused to why the book and a few other sources I found say something in the lines of "this algorithm is an approximation algorithm with an unknown approximation ratio" $\endgroup$
    – Y.y.y-a-ea-
    Commented May 8, 2019 at 17:45
  • $\begingroup$ Explanation is simple: shown greedy algorithm in the book is not really good one, book is from 2004 year (and was started earlier as simple proofreading takes several months), nobody wanted to perform full analysis, presented partial result is from 2005 and thesis is from December 2010. So the book is slightly outdated. $\endgroup$
    – Evil
    Commented May 8, 2019 at 17:49
  • $\begingroup$ thank you that´s what I thought, I´m just still curious if it was too complicated to show it back then or if I´m missing out on something? $\endgroup$
    – Y.y.y-a-ea-
    Commented May 8, 2019 at 17:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.