A Survey of Mapping Algorithms in the Long-reads Era

Overview

Journal Genome Biol

Specialties Biology
Genetics

Date 2023 Jun 1

PMID 37264447

Authors

Kristoffer Sahlin

Thomas Baudeau

Bastien Cazaux

Camille Marchet

Affiliations

Soon will be listed here.

Abstract

It has been over a decade since the first publication of a method dedicated entirely to mapping long-reads. The distinctive characteristics of long reads resulted in methods moving from the seed-and-extend framework used for short reads to a seed-and-chain framework due to the seed abundance in each read. The main novelties are based on alternative seed constructs or chaining formulations. Dozens of tools now exist, whose heuristics have evolved considerably. We provide an overview of the methods used in long-read mappers. Since they are driven by implementation-specific parameters, we develop an original visualization tool to understand the parameter settings ( http://bcazaux.polytech-lille.net/Minimap2/ ).

Citing Articles

NAVIP: Unraveling the influence of neighboring small sequence variants on functional impact prediction.

Baasner J, Rempel A, Howard D, Pucker B PLoS Comput Biol. 2025; 21(2):e1012732.

PMID: 39964984 PMC: 11849982. DOI: 10.1371/journal.pcbi.1012732.

Taming large-scale genomic analyses via sparsified genomics.

Alser M, Eudine J, Mutlu O Nat Commun. 2025; 16(1):876.

PMID: 39837860 PMC: 11751491. DOI: 10.1038/s41467-024-55762-1.

GIN-TONIC: non-hierarchical full-text indexing for graph genomes.

Ozturk U, Mattavelli M, Ribeca P NAR Genom Bioinform. 2024; 6(4):lqae159.

PMID: 39664816 PMC: 11632618. DOI: 10.1093/nargab/lqae159.

When less is more: sketching with minimizers in genomics.

Ndiaye M, Prieto-Banos S, Fitzgerald L, Yazdizadeh Kharrazi A, Oreshkov S, Dessimoz C Genome Biol. 2024; 25(1):270.

PMID: 39402664 PMC: 11472564. DOI: 10.1186/s13059-024-03414-4.

Complete mitochondrial genome of Agropyron cristatum reveals gene transfer and RNA editing events.

Ou T, Wu Z, Tian C, Yang Y, Li Z BMC Plant Biol. 2024; 24(1):830.

PMID: 39232676 PMC: 11373303. DOI: 10.1186/s12870-024-05558-8.

References

Zhang H, Li H, Jain C, Cheng H, Au K, Li H . Real-time mapping of nanopore raw signals. Bioinformatics. 2021; 37(Suppl_1):i477-i483. PMC: 8336444. DOI: 10.1093/bioinformatics/btab264. View

Bzikadze A, Mikheenko A, Pevzner P . Fast and accurate mapping of long reads to complete genome assemblies with VerityMap. Genome Res. 2022; 32(11-12):2107-2118. PMC: 9808623. DOI: 10.1101/gr.276871.122. View

Sahlin K . Effective sequence similarity detection with strobemers. Genome Res. 2021; 31(11):2080-2094. PMC: 8559714. DOI: 10.1101/gr.275648.121. View

Suzuki H, Kasahara M . Introducing difference recurrence relations for faster semi-global alignment of long sequences. BMC Bioinformatics. 2018; 19(Suppl 1):45. PMC: 5836832. DOI: 10.1186/s12859-018-2014-8. View

Belbasi M, Blanca A, Harris R, Koslicki D, Medvedev P . The minimizer Jaccard estimator is biased and inconsistent. Bioinformatics. 2022; 38(Suppl 1):i169-i176. PMC: 9235516. DOI: 10.1093/bioinformatics/btac244. View

Li H . Minimap2: pairwise alignment for nucleotide sequences. Bioinformatics. 2018; 34(18):3094-3100. PMC: 6137996. DOI: 10.1093/bioinformatics/bty191. View

Shaw J, Yu Y . Proving sequence aligners can guarantee accuracy in almost ( log ) time through an average-case analysis of the seed-chain-extend heuristic. Genome Res. 2023; 33(7):1175-1187. PMC: 10538486. DOI: 10.1101/gr.277637.122. View

Frith M, Noe L, Kucherov G . Minimally overlapping words for sequence similarity search. Bioinformatics. 2020; 36(22-23):5344-5350. PMC: 8016470. DOI: 10.1093/bioinformatics/btaa1054. View

Liu B, Liu Y, Li J, Guo H, Zang T, Wang Y . deSALT: fast and accurate long transcriptomic read alignment with de Bruijn graph-based index. Genome Biol. 2019; 20(1):274. PMC: 6913027. DOI: 10.1186/s13059-019-1895-9. View

10.

Chakraborty A, Morgenstern B, Bandyopadhyay S . S-conLSH: alignment-free gapped mapping of noisy long reads. BMC Bioinformatics. 2021; 22(1):64. PMC: 7879691. DOI: 10.1186/s12859-020-03918-3. View

11.

Ren J, Chaisson M . lra: A long read aligner for sequences and contigs. PLoS Comput Biol. 2021; 17(6):e1009078. PMC: 8248648. DOI: 10.1371/journal.pcbi.1009078. View

12.

Liu B, Gao Y, Wang Y . LAMSA: fast split read alignment with long approximate matches. Bioinformatics. 2016; 33(2):192-201. DOI: 10.1093/bioinformatics/btw594. View

13.

Liu B, Guan D, Teng M, Wang Y . rHAT: fast alignment of noisy long reads with regional hashing. Bioinformatics. 2015; 32(11):1625-31. DOI: 10.1093/bioinformatics/btv662. View

14.

Berlin K, Koren S, Chin C, Drake J, Landolin J, Phillippy A . Assembling large genomes with single-molecule sequencing and locality-sensitive hashing. Nat Biotechnol. 2015; 33(6):623-30. DOI: 10.1038/nbt.3238. View

15.

Ilie S . Efficient computation of spaced seeds. BMC Res Notes. 2012; 5:123. PMC: 3392737. DOI: 10.1186/1756-0500-5-123. View

16.

Liao W, Asri M, Ebler J, Doerr D, Haukness M, Hickey G . A draft human pangenome reference. Nature. 2023; 617(7960):312-324. PMC: 10172123. DOI: 10.1038/s41586-023-05896-x. View

17.

Sibbesen J, Eizenga J, Novak A, Siren J, Chang X, Garrison E . Haplotype-aware pantranscriptome analyses using spliced pangenome graphs. Nat Methods. 2023; 20(2):239-247. DOI: 10.1038/s41592-022-01731-9. View

18.

Nurk S, Koren S, Rhie A, Rautiainen M, Bzikadze A, Mikheenko A . The complete sequence of a human genome. Science. 2022; 376(6588):44-53. PMC: 9186530. DOI: 10.1126/science.abj6987. View

19.

Jain C, Rhie A, Hansen N, Koren S, Phillippy A . Long-read mapping to repetitive reference sequences using Winnowmap2. Nat Methods. 2022; 19(6):705-710. PMC: 10510034. DOI: 10.1038/s41592-022-01457-8. View

20.

Sedlazeck F, Rescheneder P, Smolka M, Fang H, Nattestad M, von Haeseler A . Accurate detection of complex structural variations using single-molecule sequencing. Nat Methods. 2018; 15(6):461-468. PMC: 5990442. DOI: 10.1038/s41592-018-0001-7. View