Detecting common regions and overlaps between DNA sequences is crucial in many Bioinformatics tasks. One of them is genome assembly based on the use of the overlap graph which is constructed by detecting the overlap between genomic reads. When dealing with long reads this task is further complicated by the length of the reads and the high sequencing error rate. This paper proposes a novel alignment-free method for detecting the overlaps in a set of long reads which exploits a signature (called fingerprint) of reads built from a factorization of the read based on the notion of Lyndon words. The method has been implemented in the tool KFinger and tested over a simulated and a real PacBio HiFi dataset of genomic reads; its results have been compared with the well-known aligner Minimap2. KFinger is available at https://github.com/AlgoLab/kfinger.

Bonizzoni, P., Petescia, A., Pirola, Y., Rizzi, R., Zaccagnino, R., Zizza, R. (2022). KFinger: Capturing Overlaps Between Long Reads by Using Lyndon Fingerprints. In Bioinformatics and Biomedical Engineering - 9th International Work-Conference, IWBBIO 2022, Maspalomas, Gran Canaria, Spain, June 27-30, 2022, Proceedings, Part II (pp.436-449). Cham : Springer Science and Business Media Deutschland GmbH [10.1007/978-3-031-07802-6_37].

KFinger: Capturing Overlaps Between Long Reads by Using Lyndon Fingerprints

Bonizzoni, P;Petescia, A;Pirola, Y;Rizzi, R
;
2022

Abstract

Detecting common regions and overlaps between DNA sequences is crucial in many Bioinformatics tasks. One of them is genome assembly based on the use of the overlap graph which is constructed by detecting the overlap between genomic reads. When dealing with long reads this task is further complicated by the length of the reads and the high sequencing error rate. This paper proposes a novel alignment-free method for detecting the overlaps in a set of long reads which exploits a signature (called fingerprint) of reads built from a factorization of the read based on the notion of Lyndon words. The method has been implemented in the tool KFinger and tested over a simulated and a real PacBio HiFi dataset of genomic reads; its results have been compared with the well-known aligner Minimap2. KFinger is available at https://github.com/AlgoLab/kfinger.
No
slide + paper
Scientifica
Factorization; Fingerprint; Long reads; Lyndon word; Overlap graph
English
International Work-Conference on Bioinformatics and Biomedical Engineering, IWBBIO 2022
978-3-031-07801-9
Bonizzoni, P., Petescia, A., Pirola, Y., Rizzi, R., Zaccagnino, R., Zizza, R. (2022). KFinger: Capturing Overlaps Between Long Reads by Using Lyndon Fingerprints. In Bioinformatics and Biomedical Engineering - 9th International Work-Conference, IWBBIO 2022, Maspalomas, Gran Canaria, Spain, June 27-30, 2022, Proceedings, Part II (pp.436-449). Cham : Springer Science and Business Media Deutschland GmbH [10.1007/978-3-031-07802-6_37].
Bonizzoni, P; Petescia, A; Pirola, Y; Rizzi, R; Zaccagnino, R; Zizza, R
File in questo prodotto:
File Dimensione Formato  
kfinger_preprint.pdf

accesso aperto

Tipologia di allegato: Submitted Version (Pre-print)
Dimensione 399.65 kB
Formato Adobe PDF
399.65 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/388145
Citazioni
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
Social impact