2026-07-20T05:38:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23933 2025-11-12T13:17:30Z ddc:004 open_access

Sequence Similarity Estimation by Random Subsequence Sketching Chen, Ke Pattar, Vinamratha Shao, Mingfu Alignment-free sequence comparison Phylogenetic clustering Nearest neighbor search Edit distance embedding Sequence similarity estimation is essential for many bioinformatics tasks, including functional annotation, phylogenetic analysis, and overlap graph construction. Alignment-free methods aim to solve large-scale sequence similarity estimation by mapping sequences to more easily comparable features that can approximate edit distances efficiently. Substrings or k-mers, as the dominant choice of features, face an unavoidable compromise between sensitivity and specificity when selecting the proper k-value. Recently, subsequence-based features have shown improved performance, but they are computationally demanding, and determining the ideal subsequence length remains an intricate art. In this work, we introduce SubseqSketch, a novel alignment-free scheme that maps a sequence to an integer vector, where the entries correspond to dynamic, rather than fixed, lengths of random subsequences. The cosine similarity between these vectors exhibits a strong correlation with the edit similarity between the original sequences. Through experiments on benchmark datasets, we demonstrate that SubseqSketch is both efficient and effective across various alignment-free tasks, including nearest neighbor search and phylogenetic clustering. A C++ implementation of SubseqSketch is openly available at https://github.com/Shao-Group/SubseqSketch. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ke Chen and Vinamratha Pattar and Mingfu Shao 2025 Is Part Of LIPIcs, Volume 344, 25th International Conference on Algorithms for Bioinformatics (WABI 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WABI.2025.7 urn:nbn:de:0030-drops-239332 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2025.7 eng https://creativecommons.org/licenses/by/4.0/legalcode