Spaced seed design using perfect rulers

Lavinia Egidi, Giovanni Manzini

Risultato della ricerca: Contributo su rivistaArticolo in rivistapeer review

Abstract

A widely used class of approximate pattern matching algorithms work in two stages, the first being a filtering stage that uses spaced seeds to quickly discards regions where a match is not likely to occur. The design of effective spaced seeds is known to be a hard problem. In this setting, we propose a family of lossless spaced seeds for matching with up to two errors based on mathematical objects known as perfect rulers. We analyze these seeds with respect to the tradeoff they offer between seed weight and the minimum length of the pattern to be matched. We identify a specific property of rulers, namely their skewness, which is closely related to the minimum pattern length of the derived seeds. In this context, we study in depth the specific case of Wichmann rulers and investigate the generalization of our approach to the larger class of unrestricted rulers. Although our analysis is mainly of theoretical interest, we show that for pattern lengths of practical relevance our seeds have a larger weight, hence a better filtration efficiency, than the ones known in the literature.

Lingua originaleInglese
pagine (da-a)187-203
Numero di pagine17
RivistaFundamenta Informaticae
Volume131
Numero di pubblicazione2
DOI
Stato di pubblicazionePubblicato - 2014

Fingerprint

Entra nei temi di ricerca di 'Spaced seed design using perfect rulers'. Insieme formano una fingerprint unica.

Cita questo