%0 Thesis
%D 2013
%T Lossless seeds for approximate string matching
%A Karel BÅ™inda
%X The thesis deals with lossless seeds, which were originally proposed for the purposes of the filtration phase in the DNA similarity search. The case of designing seeds for one error is studied first and sufficiently solved using the greedy algorithm. Obtained results are generalized for the case of two errors, nevertheless, it is shown that the same algorithm does not provide asymptotically optimal seeds in this case. Further on, an idea of seed design based on the so-called cyclic rulers is introduced. Possibilities of generalization for the case of more errors are mentioned. At the end the software created for the purposes of this thesis, which is given on the enclosed CD, is described.
%I Czech Technical University in Prague
%G eng
%U http://brinda.cz/publications/diplomka.pdf
%9 M.S. Thesis