Sequence similarity estimation by random subsequence sketching.

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Sequence similarity estimation is crucial for bioinformatics tasks like functional annotation and phylogenetic analysis.
• Alignment-free methods offer efficient large-scale sequence comparison by approximating edit distances.
• Existing methods like k-mers face trade-offs, while subsequence methods are computationally intensive.

Purpose of the Study:

• To introduce SubseqSketch, a novel alignment-free scheme for sequence similarity estimation.
• To develop a method that overcomes the limitations of fixed-length k-mers and computationally demanding subsequence methods.
• To demonstrate the efficiency and effectiveness of SubseqSketch in various bioinformatics applications.

Main Methods:

• SubseqSketch maps sequences to integer vectors representing dynamic lengths of random subsequences.
• Cosine similarity is used to compare these vectors, correlating strongly with edit similarity.
• The method was evaluated on benchmark datasets for alignment-free tasks.

Main Results:

• SubseqSketch demonstrates strong correlation between vector cosine similarity and original sequence edit similarity.
• The method proved efficient and effective in nearest neighbor search and phylogenetic clustering.
• Experimental results validate SubseqSketch's performance across diverse alignment-free applications.

Conclusions:

• SubseqSketch offers an efficient and effective alignment-free approach for sequence similarity estimation.
• The dynamic subsequence mapping overcomes limitations of traditional k-mer and fixed-length subsequence methods.
• The open-source implementation facilitates broader adoption in bioinformatics research.