  We consider the general problem of the Longest Common Subsequence (LCS) on
weighted sequences. Weighted sequences are an extension of classical strings,
where in each position every letter of the alphabet may occur with some
probability. Previous results presented a PTAS and noticed that no FPTAS is
possible unless P=NP. In this paper we essentially close the gap between upper
and lower bounds by improving both. First of all, we provide an EPTAS for
bounded alphabets (which is the most natural case), and prove that there does
not exist any EPTAS for unbounded alphabets unless FPT=W[1]. Furthermore, under
the Exponential Time Hypothesis, we provide a lower bound which shows that no
significantly better PTAS can exist for unbounded alphabets. As a side note, we
prove that it is sufficient to work with only one threshold in the general
variant of the problem.
