Lossless seeds for approximate string matching


Břinda, K., 2013. Lossless seeds for approximate string matching. Czech Technical University in Prague. Copy at http://j.mp/2SBHfCX
2013-ms-thesis.pdf258 KB

Thesis Type:

M.S. Thesis


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.

Publisher's Version

Last updated on 12/06/2018