Premium
Algorithms for all‐pairs Hamming distance based similarity
Author(s) -
Grabowski Szymon,
Kowalski Tomasz M.
Publication year - 2021
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/spe.2978
Subject(s) - hamming distance , edit distance , computation , hamming graph , pigeonhole principle , computer science , pairwise comparison , similarity (geometry) , hamming weight , algorithm , hamming code , metric (unit) , mathematics , disjoint sets , theoretical computer science , discrete mathematics , artificial intelligence , decoding methods , economics , operations management , image (mathematics) , block code
All‐pairs distance computation for a collection of strings is a computation‐intensive task with important applications in bioinformatics, in particular, in distance‐based phylogenetic analysis techniques. Even if the computationally efficient Hamming distance is used for this purpose, the quadratic number of sequence pairs may be challenging. We propose a number of practical algorithms for efficient pairwise Hamming distance computation under a given distance threshold. The techniques are based on such concepts as pivot‐based similarity search in metric spaces, pigeonhole principle for approximate string matching, cache‐friendly data arrangement, bit‐parallelism, and others. We experimentally show that our solutions are often about an order of magnitude faster than the average‐case linear‐time LCP based clusters method proposed recently, both in real and synthetic benchmarks.