TY  - THES
AB  - 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.
DA  - 2009
KW  - Kombinatorische Wahrscheinlichkeitstheorie
KW  - Markov-Prozess
KW  - Diskreter stochastischer Prozess
KW  - Longest common subsequence
KW  - Fluctuation of variance
KW  - Waterman conjecture
KW  - Percolation
KW  - Random modification
LA  - eng
PY  - 2009
TI  - On the probabilistic longest common subsequence problem for sequences of independent blocks
UR  - https://nbn-resolving.org/urn:nbn:de:hbz:361-14735
Y2  - 2024-11-22T01:59:23
ER  -