Applying the Positional Burrows–Wheeler Transform to All-Pairs Hamming distance

Show simple item record Mäkinen, Veli Norri, Tuukka 2019-05-15T12:53:01Z 2019-05-15T12:53:01Z 2019-06
dc.identifier.citation Mäkinen , V & Norri , T 2019 , ' Applying the Positional Burrows–Wheeler Transform to All-Pairs Hamming distance ' , Information Processing Letters , vol. 146 , pp. 17-19 .
dc.identifier.other PURE: 122542500
dc.identifier.other PURE UUID: cbc26c2c-d2a8-44ae-ad6c-87ce22961f11
dc.identifier.other Scopus: 85061334727
dc.identifier.other WOS: 000464091000003
dc.identifier.other ORCID: /0000-0003-4454-1493/work/57544667
dc.identifier.other ORCID: /0000-0002-8276-0585/work/105287118
dc.description.abstract 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 and assumptions. We show that one can use the Positional Burrows-Wheeler Transform (PBWT) by Durbin (Bioinformatics, 2014) to directly find all exact matches whose coordinates also match. The same structure also extends to verifying the pairs for the Hamming distance threshold. The same analysis as for the algorithm of Crochemore et al. applies. As a side result, we show how to extend PBWT for non-binary alphabets. The new operations provided by PBWT find other applications in similar tasks as those considered here. (C) 2019 The Authors. Published by Elsevier B.V. en
dc.format.extent 3
dc.language.iso eng
dc.relation.ispartof Information Processing Letters
dc.rights cc_by_nc_nd
dc.rights.uri info:eu-repo/semantics/openAccess
dc.subject Data structures
dc.subject Hamming distance
dc.subject Phylogenetic inference
dc.subject Positional Burrows-Wheeler Transform
dc.subject 114 Physical sciences
dc.title Applying the Positional Burrows–Wheeler Transform to All-Pairs Hamming distance en
dc.type Article
dc.contributor.organization Department of Computer Science
dc.contributor.organization Helsinki Institute for Information Technology
dc.contributor.organization Genome-scale Algorithmics research group / Veli Mäkinen
dc.contributor.organization Bioinformatics
dc.contributor.organization Algorithmic Bioinformatics
dc.description.reviewstatus Peer reviewed
dc.relation.issn 0020-0190
dc.rights.accesslevel openAccess
dc.type.version publishedVersion

Files in this item

Total number of downloads: Loading...

Files Size Format View
1_s2.0_S0020019019300262_main_2_.pdf 188.6Kb PDF View/Open

This item appears in the following Collection(s)

Show simple item record