Seed optimization for i.i.d. similarities is no easier than optimal Golomb ruler design

DOI10.1016/J.IPL.2009.07.008zbMATH Open1206.68148OpenAlexW1981666173MaRDI QIDQ990937FDOQ990937

Authors Bin Ma, Hongyi Yao

Publication date 1 September 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2009.07.008

zbMATH Keywords

computational complexityspaced seedsGolomb ruler

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On spaced seeds for similarity search
• Hardness of optimal spaced seed design
• Combinatorial Pattern Matching
• On the complexity of the spaced seeds
• Sensitivity analysis and efficient method for identifying optimal spaced seeds

Cites work

• scientific article; zbMATH DE number 1222377 (Why is no real title available?)
• scientific article; zbMATH DE number 1786448 (Why is no real title available?)
• scientific article; zbMATH DE number 867473 (Why is no real title available?)
• A class of binary recurrent codes with limited error propagation
• A new algorithm for Golomb ruler derivation and proof of the 19 mark ruler
• Combinatorial Pattern Matching
• Combinatorial Pattern Matching
• Multiple filtration and approximate pattern matching
• On spaced seeds for similarity search
• On the complexity of the spaced seeds
• Optimal spaced seeds for faster approximate string matching
• Sensitivity analysis and efficient method for identifying optimal spaced seeds
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• Superiority and complexity of the spaced seeds

Cited in

(1)

• Better spaced seeds using quadratic residues

Describes a project that uses

Uses Software

• PatternHunter

This page was built for publication: Seed optimization for i.i.d. similarities is no easier than optimal Golomb ruler design

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q990937)