30
$\begingroup$

A string has $2^n$ subsequences, but they are usually not all distinct. What is the complexity of finding the maximum frequency of any subsequence?

For example, the string "subsequence" contains 7 copies of the subsequence "sue" and this is the maximum.

Sample brute-force code at http://ideone.com/UIp3t

Are there related structural theorems? Both of these turn out to be false:

  • the longest of the maximum-frequency subsequences is unique
  • the maximum frequency of any length-$k$ subsequence is unimodal in $k$

Possibly related links:

Edit 10 days later: thanks for taking a look! I had wondered if this would make a nice polynomial-time solvable programming contest problem. I guess not, but I hope to think about it again later.

Improve this question
$\endgroup$
13
  • 5
    $\begingroup$ A possibly naive initial question: is it clear that this problem is even in NP? That is to say: for the problem of determining whether there is a subsequence with at least k occurances in an n-character string, what would a certificate look like? For instance, listing all tuples of indices indicating the instances of a given subsequence would fail to be polynomial sized for the string aaa...aa (which, while a boring input, nevertheless has a substring with roughly $n \mathbf C (n/2)$ occurances). $\endgroup$
    – Niel de Beaudrap
    Aug 15, 2012 at 0:56
  • 7
    $\begingroup$ @Niel de Beaudrap: I think that we can count the number of occurrences as subsequences in polynomial time by dynamic programming, making it possible to use the subsequence itself as a certificate. $\endgroup$
    – Tsuyoshi Ito
    Aug 15, 2012 at 2:21
  • 2
    $\begingroup$ I'm a little confused: is the question "given a string s, find the subsequence that occurs the maximum number of times?" $\endgroup$
    – Suresh Venkat
    Aug 25, 2012 at 0:13
  • 2
    $\begingroup$ @SureshVenkat: Yes, that's my understanding. For example, given a sequence of $n$ X's as input, the correct answer would be a sequence of $n/2$ X's. $\endgroup$
    – Jeffε
    Aug 25, 2012 at 2:39
  • 2
    $\begingroup$ @marzio-de-biasi: the question you linked to is different (and much easier): there you are given the subsequence. $\endgroup$
    – david
    Aug 26, 2012 at 11:55

2 Answers 2

Reset to default
5
+50
$\begingroup$

from a search, here is a paper with some research & findings for graduate level research but (caveat) no references. it has some heuristics, estimates, empirical results & commentary on the problem and some ideas on proving its (approximation) complexity etc.

Identification of Most Frequent Subsequences
CSE 549 Computational Biology Project Final Report
Mikhail Bautin 2006

(while there are some standard subsequence problems that are somewhat similar & studied eg in the Elzinga et al paper, is it possible this particular subsequence problem has not been studied too much?)

Improve this answer
$\endgroup$
5
  • 4
    $\begingroup$ I don't understand why this was downvoted. It may not be a very deep paper but it appears to be directly on topic. $\endgroup$
    – David Eppstein
    Aug 28, 2012 at 17:33
  • $\begingroup$ fyi/addendum Bautin also says at the end of paper he has 5K lines of C++ & Python code on the problem/paper for anyone interested $\endgroup$
    – vzn
    Aug 29, 2012 at 15:54
  • $\begingroup$ @David, I don't think the downvote is because of the linked paper, it is probably more to do with the fact that this answer looks like (essentially) a one line link answer (without explaining how the paper is related to the question and answers it). This might have been more appropriate as a comment. $\endgroup$
    – Kaveh
    Aug 29, 2012 at 16:14
  • 1
    $\begingroup$ ok kaveh, then, spelled out: the paper seems to reveal (unless anyone can find a better ref or come up with proof of this difficult problem themself) that the exact complexity of the problem is so far unknown/open (other than the obvious PSpace/ExpTime) and may contain the best known analysis/approaches to solving it so far $\endgroup$
    – vzn
    Aug 29, 2012 at 16:33
  • $\begingroup$ I did find this paper before and apologize for not linking to it above, which was since I didn't think it gave much concrete information. I sent the author an email some time ago asking if there was any more he could say about anything that happened since it was written, but got no reply yet. $\endgroup$
    – daveagp
    Aug 29, 2012 at 16:41
3
$\begingroup$

Not an answer, just a lemma.

So first of all one might wonder what the commonest subsequence of strings like 12..t12..t12..t.. is. After a little thinking one realizes that it must also have the form 12..t12..t12.., just obviously shorter. If the original string has length nt, and the subsequence of this special form has length k, then the number of its occurrences is exactly ${n+k-\lceil k/t\rceil \choose k}={n+k-\lceil k/t\rceil \choose n-\lceil k/t\rceil}$. This implies that the most common subsequence also ends with $t$ (i.e. $k$ has to be divisible by $t$). But where does this take its maximum and how much is it??? Quite embarassing, but I could not figure it out...

Improve this answer
$\endgroup$

Your Answer

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

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