Optimal gap-affine alignment in O ( s ) space
Open accessPublished version of a preprint
Abstract
Motivation: Pairwise sequence alignment remains a fundamental problem in computational biology and bioinformatics. Recent advances in genomics and sequencing technologies demand faster and scalable algorithms that can cope with the ever-increasing sequence lengths. Classical pairwise alignment algorithms based on dynamic programming are strongly limited by quadratic requirements in time and memory. The recently proposed wavefront alignment algorithm (WFA) introduced an efficient algorithm to perform exact gap-affine alignment in O(ns) time, where s is the optimal score and n is the sequence length. Notwithstanding these bounds, WFA’s O(s2) memory requirements become computationally impractical for genome-scale alignments, leading to a need for further improvement. Results: In this article, we present the bidirectional WFA algorithm, the first gap-affine algorithm capable of computing optimal alignments in O(s) memory while retaining WFA’s time complexity of O(ns). As a result, this work improves the lowest known memory bound O(n) to compute gap-affine alignments. In practice, our implementation never requires more than a few hundred MBs aligning noisy Oxford Nanopore Technologies reads up to 1 Mbp long while maintaining competitive execution times. Availability and implementation: All code is publicly available at https://github.com/smarco/BiWFA-paper. Supplementary information: Supplementary data are available at Bioinformatics online.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Exact methods, including those based on dynamic programming, are often used for refining alignments or for aligning smaller regions of the genome.
“Such methods, including those based on dynamic programming, are often used for refining alignments or for aligning smaller regions of the genome [60,61].”
From Whole-Genome Alignment: Methods, Challenges, and Future Directions (2024) · cites this paper as [60]
The Introduction (page unavailable) describes dynamic programming as a classical way to obtain optimal alignments and says exact methods struggle to scale to long sequences, which supports their suitability for smaller regions. It does not say that exact methods are often used to refine alignments, or establish how often they are used for smaller genomic regions. (LLM, conf=0.78)
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
No references could be resolved yet.
Research works printed but not linked: 31
- Altschul S. et al (1990) Basic local alignment search tool. J. Mol. Biol., 215, 403– 410. 2231712
- Bowden R. et al (2019) Sequencing of human genomes with nanopore technology. Nat. Commun., 10, 1869. 31015479 PMC6478738
- Daily J. (2016) Parasail: SIMD C library for global, semi-global, and local pairwise sequence alignments. BMC Bioinf., 17, 1– 11. PMC4748600 26864881
- Durbin R. et al (1998) Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press, Cambridge.
- Eizenga J.M., Paten B. (2022) Improving the time and space complexity of the WFA algorithm and generalizing its scoring. bioRxiv.
- Farrar M. (2007) Striped Smith–Waterman speeds database searches six times over other SIMD implementations. Bioinformatics, 23, 156– 161. 17110365
- Garrison E., Marth G. (2012) Haplotype-based variant detection from short-read sequencing. arXiv preprint arXiv:1207.3907. · arXiv
- Gotoh O. (1982) An improved algorithm for matching biological sequences. J. Mol. Biol., 162, 705– 708. 7166760
- Jones N. et al (2004) An Introduction to Bioinformatics Algorithms. MIT Press, Cambridge.
- Kiełbasa S. et al (2011) Adaptive seeds tame genomic sequence comparison. Genome Res., 21, 487– 493. 21209072 PMC3044862
- Koren S. et al (2017) CANU: scalable and accurate long-read assembly via adaptive k-mer weighting and repeat separation. Genome Res., 27, 722– 736. 28298431 PMC5411767
- Li H. (2013) Aligning sequence reads, clone sequences and assembly contigs with bwa-mem. arXiv preprint arXiv:1303.3997. · arXiv
- Li H. (2018) Minimap2: pairwise alignment for nucleotide sequences. Bioinformatics, 34, 3094– 3100. 29750242 PMC6137996
- Loving J. et al (2014) BitPAl: a bit-parallel, general integer-scoring sequence alignment algorithm. Bioinformatics, 30, 3166– 3173. 25075119 PMC4221118
- Marco-Sola S. et al (2012) The gem mapper: fast, accurate and versatile alignment by filtration. Nat. Methods, 9, 1185– 1188. 23103880
- Marco-Sola S. et al (2021) Fast gap-affine pairwise alignment using the wavefront algorithm. Bioinformatics, 37, 456– 463. 32915952 PMC8355039
- McKenna A. et al (2010) The genome analysis toolkit: a mapreduce framework for analyzing next-generation DNA sequencing data. Genome Res., 20, 1297– 1303. 20644199 PMC2928508
- Miga K. H., Wang T. (2021) The need for a human pangenome reference sequence. Annu. Rev. Genomics Hum. Genet., 22, 81– 102. 33929893 PMC8410644
- Myers E. W., Miller W. (1988) Optimal alignments in linear space. Bioinformatics, 4, 11– 17. 3382986
- Needleman S. B., Wunsch C. D. (1970) A general method applicable to the search for similarities in the amino acid sequence of two proteins. J. Mol. Biol., 48, 443– 453. 5420325
- Rahn R. et al (2018) Generic accelerated sequence alignment in seqan using vectorization and multi-threading. Bioinformatics, 34, 3437– 3445. 29726911
- Rodríguez-Martín B. et al (2017) Chimpipe: accurate detection of fusion genes and transcription-induced chimeras from RNA-seq data. BMC Genomics, 18, 7– 17. 28049418 PMC5209911
- Rognes T., Seeberg E. (2000) Six-fold speed-up of Smith–Waterman sequence database searches using parallel processing on common microprocessors. Bioinformatics, 16, 699– 706. 11099256
- Simpson J. et al (2009) ABYSS: a parallel assembler for short read sequence data. Genome Res., 19, 1117– 1123. 19251739 PMC2694472
- Šošić M., Šikić M. (2017) EDLIB: a C/C++ library for fast, exact sequence alignment using edit distance. Bioinformatics, 33, 1394– 1395. 28453688 PMC5408825
- Suzuki H., Kasahara M. (2017) Acceleration of nucleotide semi-global alignment with adaptive banded dynamic programming. bioRxiv.
- Suzuki H., Kasahara M. (2018) Introducing difference recurrence relations for faster semi-global alignment of long sequences. BMC Bioinformatics, 19, 33– 47. 29504909 PMC5836832
- Wozniak A. (1997) Using video-oriented instructions to speed up sequence comparison. Bioinformatics, 13, 145– 150. 9146961
- Xia Z. et al (2021) A review of parallel implementations for the Smith–Waterman algorithm. In: Interdisciplinary Sciences: Computational Life Sciences, pp. 1– 14. PMC8419822 34487327
- Zhang Z. et al (2000) A greedy algorithm for aligning DNA sequences. J. Comput. Biol., 7, 203– 214. 10890397
- Zhao M. et al (2013) SSW library: an SIMD Smith–Waterman C/C++ library for use in genomic applications. PLoS ONE, 8, e82138. 24324759 PMC3852983
Cited by
Sorted by citations
A draft human pangenome reference.
Liao, W.-W., Asri, M., Ebler, J., Doerr, D., Haukness, M., Hickey, G., Lu, S., Lucas, J. K., Monlong, J., Abel, H. J., et al. (2023) · Nature · doi:10.1038/s41586-023-05896-x · Cited by 1,129 · see citing works
Self-citationRecombination between heterologous human acrocentric chromosomes
Guarracino, A., Buonaiuto, S., de Lima, L. G., Potapova, T., Rhie, A., Koren, S., Rubinstein, B., Fischer, C., Human Pangenome Reference Consortium, Abel, H. J., et al. (2023) · Nature · doi:10.1038/s41586-023-05976-y · Cited by 134 · see citing works
Self-citationWhole-Genome Alignment: Methods, Challenges, and Future Directions
Saada, B., Zhang, T., Siga, E., Zhang, J., & Magalhães Muniz, M. M. (2024) · Applied Sciences · doi:10.3390/app14114837 · Cited by 15 · see citing works
- Authors
- Marco-Sola, S., Eizenga, J. M., Guarracino, A., Paten, B., Garrison, E., & Moreto, M.
- Affiliations
- Computer Sciences Department, Barcelona Supercomputing Center , Barcelona 08034, Spain
- University of California, Santa Cruz (US)
- University of Tennessee Health Science Center (US)
- ORCID
- Venue
- Bioinformatics
- Publisher
- Oxford University Press (OUP)
- Published
- 2023-02-01
- Volume
- 39
- Issue
- 2
- ISSN
- 1367-4803 (ISSN-L)
- 1367-4811
- PMC
- PMC9940620
- OpenAlex
- W4319334382
- Cited by
- 66
- References
- 0
- Citations by year
- 2026: 15 · 2025: 24 · 2024: 16 · 2023: 10 · 2022: 1
- FWCI
- 5.60
- Type
- journal article
- Language
- en
- Open access
- gold
- doi.org
- Licence
- Locations
- Bioinformatics (publishedVersion, cc-by)
- bioRxiv (Cold Spring Harbor Laboratory) (acceptedVersion, cc-by)
- PubMed Central (publishedVersion, cc-by)
- PubMed (publishedVersion)
- Dipòsit Digital de Documents de la UAB (Universitat Autònoma de Barcelona) (submittedVersion, cc-by)
- eScholarship (California Digital Library) (submittedVersion, cc-by)
- Funders
- European Union
- Ministerio de Ciencia e Innovacion
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Algorithms and Data Compression
- Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Genomics and Phylogenetic Studies
- Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Fractal and DNA sequence analysis
- Keywords
- pairwise sequence alignment, space complexity, linear memory, long-read alignment
- MeSH terms
- Algorithms, Software, Genome, Sequence Analysis, DNA, Computational Biology, Genomics
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
