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

Näytä kaikki kuvailutiedot



Pysyväisosoite

http://hdl.handle.net/10138/301747

Lähdeviite

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 . https://doi.org/10.1016/j.ipl.2019.02.003

Julkaisun nimi: Applying the Positional Burrows–Wheeler Transform to All-Pairs Hamming distance
Tekijä: Mäkinen, Veli; Norri, Tuukka
Tekijän organisaatio: Department of Computer Science
Helsinki Institute for Information Technology
Genome-scale Algorithmics research group / Veli Mäkinen
Bioinformatics
Algorithmic Bioinformatics
Päiväys: 2019-06
Kieli: eng
Sivumäärä: 3
Kuuluu julkaisusarjaan: Information Processing Letters
ISSN: 0020-0190
DOI-tunniste: https://doi.org/10.1016/j.ipl.2019.02.003
URI: http://hdl.handle.net/10138/301747
Tiivistelmä: 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.
Avainsanat: Data structures
Hamming distance
Phylogenetic inference
Positional Burrows-Wheeler Transform
114 Physical sciences
Vertaisarvioitu: Kyllä
Tekijänoikeustiedot: cc_by_nc_nd
Pääsyrajoitteet: openAccess
Rinnakkaistallennettu versio: publishedVersion


Tiedostot

Latausmäärä yhteensä: Ladataan...

Tiedosto(t) Koko Formaatti Näytä
1_s2.0_S0020019019300262_main_2_.pdf 188.6KB PDF Avaa tiedosto

Viite kuuluu kokoelmiin:

Näytä kaikki kuvailutiedot