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

Torres F (2009)
Bielefeld (Germany): Bielefeld University.

Bielefelder E-Dissertation | Englisch
 
Download
OA
Autor*in
Torres, Felipe
Gutachter*in / Betreuer*in
Götze, Friedrich
Abstract / Bemerkung
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.
Stichworte
Kombinatorische Wahrscheinlichkeitstheorie; Markov-Prozess; Diskreter stochastischer Prozess; Longest common subsequence; Fluctuation of variance; Waterman conjecture; Percolation; Random modification
Jahr
2009
Page URI
https://pub.uni-bielefeld.de/record/2304398

Zitieren

Torres F. On the probabilistic longest common subsequence problem for sequences of independent blocks. Bielefeld (Germany): Bielefeld University; 2009.
Torres, F. (2009). On the probabilistic longest common subsequence problem for sequences of independent blocks. Bielefeld (Germany): Bielefeld University.
Torres, Felipe. 2009. On the probabilistic longest common subsequence problem for sequences of independent blocks. Bielefeld (Germany): Bielefeld University.
Torres, F. (2009). On the probabilistic longest common subsequence problem for sequences of independent blocks. Bielefeld (Germany): Bielefeld University.
Torres, F., 2009. On the probabilistic longest common subsequence problem for sequences of independent blocks, Bielefeld (Germany): Bielefeld University.
F. Torres, On the probabilistic longest common subsequence problem for sequences of independent blocks, Bielefeld (Germany): Bielefeld University, 2009.
Torres, F.: On the probabilistic longest common subsequence problem for sequences of independent blocks. Bielefeld University, Bielefeld (Germany) (2009).
Torres, Felipe. On the probabilistic longest common subsequence problem for sequences of independent blocks. Bielefeld (Germany): Bielefeld University, 2009.
Alle Dateien verfügbar unter der/den folgenden Lizenz(en):
Copyright Statement:
Dieses Objekt ist durch das Urheberrecht und/oder verwandte Schutzrechte geschützt. [...]
Volltext(e)
Access Level
OA Open Access
Zuletzt Hochgeladen
2019-09-25T06:20:56Z
MD5 Prüfsumme
39971e485a5b8eb81ce1806f7a140acc


Export

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Suchen in

Google Scholar