On the complexity of the spaced seeds

DOI10.1016/J.JCSS.2007.03.008MaRDI QIDQ2643726zbMATH OpenOpenAlexFDO

Authors Bin Ma, Ming Li

Publication date 27 August 2007

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2007.03.008

zbMATH Keywords

homology searchoptimal spaced seeds

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Protein sequences, DNA sequences (92D20)

Recommendations

• On spaced seeds for similarity search
• Sensitivity analysis and efficient method for identifying optimal spaced seeds
• New Algorithms for the Spaced Seeds
• Combinatorial Pattern Matching
• Optimal spaced seeds for hidden Markov models, with application to homologous coding regions

Cites work

• Combinatorial Pattern Matching
• Combinatorial Pattern Matching
• Extensions of Jentzsch's Theorem
• scientific article; zbMATH DE number 193132 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1405792 (Why is no real title available?)
• On spaced seeds for similarity search
• On the closest string and substring problems
• Sensitivity analysis and efficient method for identifying optimal spaced seeds
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis

Cited in

(11)

• Metagenomic reads binning with spaced seeds
• Sensitivity analysis and efficient method for identifying optimal spaced seeds
• Analytic combinatorics for computing seeding probabilities
• Optimal spaced seeds for hidden Markov models, with application to homologous coding regions
• New Algorithms for the Spaced Seeds
• Design and analysis of periodic multiple seeds
• Better spaced seeds using quadratic residues
• Fast spaced seed hashing
• Combinatorial Pattern Matching
• Hardness of optimal spaced seed design
• Seed optimization for i.i.d. similarities is no easier than optimal Golomb ruler design

Describes a project that uses

Uses Software

• PatternHunter

This page was built for publication: On the complexity of the spaced seeds

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