Spaced seeds design using perfect rulers

Lavinia Egidi, Giovanni Manzini

Risultato della ricerca: Capitolo in libro/report/atti di convegnoContributo a conferenzapeer review

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.

Lingua originaleInglese
Titolo della pubblicazione ospiteString Processing and Information Retrieval - 18th International Symposium, SPIRE 2011, Proceedings
Pagine32-43
Numero di pagine12
DOI
Stato di pubblicazionePubblicato - 2011
Evento18th International Symposium on String Processing and Information Retrieval, SPIRE 2011 - Pisa, Italy
Durata: 17 ott 201121 ott 2011

Serie di pubblicazioni

NomeLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7024 LNCS
ISSN (stampa)0302-9743
ISSN (elettronico)1611-3349

???event.eventtypes.event.conference???

???event.eventtypes.event.conference???18th International Symposium on String Processing and Information Retrieval, SPIRE 2011
Paese/TerritorioItaly
CittàPisa
Periodo17/10/1121/10/11

Fingerprint

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

Cita questo