Design and analysis of periodic multiple seeds

DOI10.1016/J.TCS.2013.12.007zbMath1279.05007OpenAlexW2018700999MaRDI QIDQ393900

Giovanni Manzini, Lavinia Egidi

Publication date: 24 January 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2013.12.007

zbMATH Keywords

Steiner systemdifference setdifference familyapproximate string matchinglossless filtrationspaced seed

Mathematics Subject Classification ID

Combinatorics on words (68R15) Other designs, configurations (05B30) Combinatorial aspects of difference sets (number-theoretic, group-theoretic, etc.) (05B10) Algorithms on strings (68W32)

Uses Software

• SHRiMP
• PatternHunter
• ZOOM
• PerM

Cites Work

• Unnamed Item
• Better spaced seeds using quadratic residues
• Hardness of optimal spaced seed design
• Constructions for strictly cyclic 3-designs and applications to optimal OOCs with \(\lambda =2\)
• On disjoint \((3t,3,1)\) cyclic difference families
• On the number of blocks in a generalized Steiner system
• Pairwise balanced designs from finite fields
• On spaced seeds for similarity search
• Constructions of \((q,k,1)\) difference families with \(q\) a prime power and \(k=4,5\)
• On the complexity of the spaced seeds
• Optimal spaced seeds for faster approximate string matching
• Constructions for cyclic 3-designs and improved results on cyclic Steiner quadruple systems
• Linear work suffix array construction
• Combinatorial Designs
• Existence of (q, 7, 1) difference families with q a prime power
• A Note on Restricted Difference Bases

This page was built for publication: Design and analysis of periodic multiple seeds