| Abstract: | We consider the problem of lossless spaced seed design for approximate
pattern matching. We show that, using mathematical objects known as perfect
rulers, we can derive a family of spaced seeds for matching with up to two
errors. We analyze these seeds with respect to the trade-off they offer
between seed weight and the minimum length of the pattern to be matched. We
prove that for patterns of length up to a few hundreds our seeds have a
larger weight, hence a better filtration efficiency, than the ones known in
the literature. In this context, we study in depth the specific case of
Wichmann rulers and prove some preliminary results on the generalization of
our approach to the larger class of unrestricted rulers. |
