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  -