Commonest Subsequence
from a search, here is a paper with some research &amp; findings for graduate level research but (caveat) no references. it has some heuristics, estimates, empirical results &amp; 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 &amp; studied eg in the Elzinga et al paper, is it possible this particular subsequence problem has not been studied too much?)