Exact Sketch-Based Read Mapping
Schulz T, Medvedev P (2023)
In: 23rd International Workshop on Algorithms in Bioinformatics. Belazzougui D, Ouangraoua A, Schloss Dagstuhl â Leibniz-Zentrum fĂźr Informatik GmbH (Eds); Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum fĂźr Informatik.
Konferenzbeitrag
| VerĂśffentlicht | Englisch
Download
Es wurden keine Dateien hochgeladen. Nur Publikationsnachweis!
Autor*in
Schulz, TizianUniBi
;
Medvedev, Paul
![](https://pub.uni-bielefeld.de/images/icon_orcid.png)
Herausgeber*in
Belazzougui, Djamal;
Ouangraoua, AĂŻda
herausgebende KĂśrperschaft
Schloss Dagstuhl â Leibniz-Zentrum fĂźr Informatik GmbH
Einrichtung
Abstract / Bemerkung
Given a sequencing read, the broad goal of read mapping is to find the location(s) in the reference genome that have a "similar sequence". Traditionally, "similar sequence" was defined as having a high alignment score and read mappers were viewed as heuristic solutions to this well-defined problem. For sketch-based mappers, however, there has not been a problem formulation to capture what problem an exact sketch-based mapping algorithm should solve. Moreover, there is no sketch-based method that can find all possible mapping positions for a read above a certain score threshold.
In this paper, we formulate the problem of read mapping at the level of sequence sketches. We give an exact dynamic programming algorithm that finds all hits above a given similarity threshold. It runs in {O}(|t| + |p| + đ²) time and Î(đ²) space, where |t| is the number of k-mers inside the sketch of the reference, |p| is the number of k-mers inside the readâs sketch and đ is the number of times that k-mers from the pattern sketch occur in the sketch of the text. We evaluate our algorithmâs performance in mapping long reads to the T2T assembly of human chromosome Y, where ampliconic regions make it desirable to find all good mapping positions. For an equivalent level of precision as minimap2, the recall of our algorithm is 0.88, compared to only 0.76 of minimap2.
Erscheinungsjahr
2023
Titel des Konferenzbandes
23rd International Workshop on Algorithms in Bioinformatics
Page URI
https://pub.uni-bielefeld.de/record/2982645
Zitieren
Schulz T, Medvedev P. Exact Sketch-Based Read Mapping. In: Belazzougui D, Ouangraoua A, Schloss Dagstuhl â Leibniz-Zentrum fĂźr Informatik GmbH, eds. 23rd International Workshop on Algorithms in Bioinformatics. Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum fĂźr Informatik; 2023.
Schulz, T., & Medvedev, P. (2023). Exact Sketch-Based Read Mapping. In D. Belazzougui, A. Ouangraoua, & Schloss Dagstuhl â Leibniz-Zentrum fĂźr Informatik GmbH (Eds.), 23rd International Workshop on Algorithms in Bioinformatics Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum fĂźr Informatik. https://doi.org/10.4230/LIPICS.WABI.2023.14
Schulz, Tizian, and Medvedev, Paul. 2023. âExact Sketch-Based Read Mappingâ. In 23rd International Workshop on Algorithms in Bioinformatics, ed. Djamal Belazzougui, AĂŻda Ouangraoua, and Schloss Dagstuhl â Leibniz-Zentrum fĂźr Informatik GmbH. Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum fĂźr Informatik.
Schulz, T., and Medvedev, P. (2023). âExact Sketch-Based Read Mappingâ in 23rd International Workshop on Algorithms in Bioinformatics, Belazzougui, D., Ouangraoua, A., and Schloss Dagstuhl â Leibniz-Zentrum fĂźr Informatik GmbH eds. (Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum fĂźr Informatik).
Schulz, T., & Medvedev, P., 2023. Exact Sketch-Based Read Mapping. In D. Belazzougui, A. Ouangraoua, & Schloss Dagstuhl â Leibniz-Zentrum fĂźr Informatik GmbH, eds. 23rd International Workshop on Algorithms in Bioinformatics. Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum fĂźr Informatik.
T. Schulz and P. Medvedev, âExact Sketch-Based Read Mappingâ, 23rd International Workshop on Algorithms in Bioinformatics, D. Belazzougui, A. Ouangraoua, and Schloss Dagstuhl â Leibniz-Zentrum fĂźr Informatik GmbH, eds., Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum fĂźr Informatik, 2023.
Schulz, T., Medvedev, P.: Exact Sketch-Based Read Mapping. In: Belazzougui, D., Ouangraoua, A., and Schloss Dagstuhl â Leibniz-Zentrum fĂźr Informatik GmbH (eds.) 23rd International Workshop on Algorithms in Bioinformatics. Schloss Dagstuhl - Leibniz-Zentrum fĂźr Informatik, Dagstuhl (2023).
Schulz, Tizian, and Medvedev, Paul. âExact Sketch-Based Read Mappingâ. 23rd International Workshop on Algorithms in Bioinformatics. Ed. Djamal Belazzougui, AĂŻda Ouangraoua, and Schloss Dagstuhl â Leibniz-Zentrum fĂźr Informatik GmbH. Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum fĂźr Informatik, 2023.
Link(s) zu Volltext(en)
Access Level
![Open access file OA](https://pub.uni-bielefeld.de/images/access_open.png)
Daten bereitgestellt von European Bioinformatics Institute (EBI)
Zitationen in Europe PMC
Daten bereitgestellt von Europe PubMed Central.
References
Daten bereitgestellt von Europe PubMed Central.
Export
Markieren/ Markierung lĂśschen
Markierte Publikationen
Quellen
PMID: 38831964
PubMed | Europe PMC
Suchen in