TY - GEN
T1 - Spaced seeds design using perfect rulers
AU - Egidi, Lavinia
AU - Manzini, Giovanni
PY - 2011
Y1 - 2011
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=80053958855&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-24583-1_5
DO - 10.1007/978-3-642-24583-1_5
M3 - Conference contribution
AN - SCOPUS:80053958855
SN - 9783642245824
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 32
EP - 43
BT - String Processing and Information Retrieval - 18th International Symposium, SPIRE 2011, Proceedings
T2 - 18th International Symposium on String Processing and Information Retrieval, SPIRE 2011
Y2 - 17 October 2011 through 21 October 2011
ER -