Multiple seeds sensitivity using a single seed with threshold.

Area of Science:

• Bioinformatics
• Computational Biology
• Genomic Data Analysis

Background:

• Spaced seeds are crucial for biosequence similarity search, with multiple seed approaches offering optimal sensitivity/selectivity.
• Current multiple seed methods face practical memory limitations, restricting the number of seeds usable simultaneously.

Purpose of the Study:

• To develop a memory-efficient single spaced seed approach for biosequence similarity search.
• To achieve sensitivity/selectivity trade-offs comparable to multiple seed methods using a single seed strategy.

Main Methods:

• Revisiting the single spaced seed approach, defining homology based on clustered seed hits (threshold t).
• Designing seeds by strategically placing 'don't care' symbols using quadratic residues modulo a prime number.
• Evaluating seed performance with a threshold t > 1 for sensitivity and selectivity.

Main Results:

• The proposed single spaced seeds, with t > 1, demonstrate sensitivity/selectivity trade-offs competitive with leading multiple seed methods.
• The threshold 't' allows for adjustable sensitivity and selectivity, enabling tailored searches.
• The derived seeds exhibit robustness and flexible usage characteristics.

Conclusions:

• A novel single spaced seed design using quadratic residues offers a memory-efficient alternative to multiple seed approaches.
• This method achieves high performance in biosequence similarity searches and allows for post-search parameter tuning.
• The approach provides a robust and flexible tool for bioinformatics applications.