TY -
T1 - Applying the Positional Burrowsâ€“Wheeler Transform to All-Pairs Hamming distance
SN - /
UR - http://hdl.handle.net/10138/301747
T3 -
A1 - MĂ¤kinen, Veli; Norri, Tuukka
A2 -
PB -
Y1 - 2019
LA - eng
AB - Crochemore et al. gave in WABI 2017 an algorithm that from a set of input strings finds all pairs of strings that have Hamming distance at most a given threshold. The proposed algorithm first finds all long enough exact matches between the strings, and sorts these into pairs whose coordinates also match. Then the remaining pairs are verified for the Hamming distance threshold. The algorithm was shown to work in average linear time, under some constraints and assumptions.under some constraints an...
VO -
IS -
SP -
OP -
KW - Data structures; Hamming distance; Phylogenetic inference; Positional Burrows-Wheeler Transform; 114 Physical sciences
N1 -
PP -
ER -