On the probabilistic longest common subsequence problem for sequences of independent blocks

Let X and Y be two binary random strings of length n independent of each other. Let Ln denote the length of the Longest Common Subsequence (LCS) of X and Y. In general the order of magnitude in n of VAR[Ln] is not known. So far, Matzinger and his collaborators had been able to prove that VAR[Ln] has order asymptotic n in few cases depending on the distribution of symbols in the sequences X and Y. In this thesis, we prove that VAR[Ln] has order asymptotic n considering a model which is not low entropy, in comparison with some previous cases which are low entropy models. The model for the distribution we consider here is i.i.d. sequences of blocks, where blocks are words consisting only of one symbol. In the present case all the blocks have length l-1, l or l+1 with probability 1/3 for a given integer parameter l>0. We reduce the problem of proving that VAR[Ln] has order asymptotic n to showing that a function under an entropy constraint does not go below zero. The method which we develop could be used for many other more complex cases wherever one pattern tends to influence the LCS score in a biased way. Also, a natural question is what happens if one has a more realistic situation than i.i.d, like Markov chains of words for instance (DNA models). This thesis partially answers this question since the model considered is a Markov chain, but the more general case where one can have blocks with different lengths (for instance, in the Bernoulli case a block of length j>0 has length 0.5j) is still open for future research though the techniques shown here give us new tools for approaching it.

Level thesis:degree_level

thesis.doctoral

Grantor dc:publisher

Universität Bielefeld

Year

2009

Author dc:creator

• Torres, Felipe

Repository record source_url

https://pub.uni-bielefeld.de/record/2304398

OAI identifier oai:identifier

oai:pub.uni-bielefeld.de:2304398