Jul 20, 2023

Exact gap-affine algorithm using homology to accelerate alignment

The wavefront alignment WFA algorithm is an exact gap-affine algorithm that takes advantage of homologous regions between the sequences to accelerate the alignment process. Unlike traditional dynamic programming algorithms that run in quadratic time, the WFA runs in time Ons+s^2, proportional to the sequence length n and the alignment score s, using Os^2 memory or Os using the ultralow/BiWFA mode. Moreover, the WFA algorithm exhibits simple computational patterns that the modern compilers can automatically vectorize for different architectures without adapting the code.

Checkout these related ports:
  • Wise - Intelligent algorithms for DNA searches
  • Vt - Discovers short variants from Next Generation Sequencing data
  • Vsearch - Versatile open-source tool for metagenomics
  • Viennarna - Alignment tools for the structural analysis of RNA
  • Velvet - Sequence assembler for very short reads
  • Vcftools - Tools for working with VCF genomics files
  • Vcflib - C++ library and CLI tools for parsing and manipulating VCF files
  • Vcf2hap - Generate .hap file from VCF for haplohseq
  • Vcf-split - Split a multi-sample VCF into single-sample VCFs
  • Unikmer - Toolkit for nucleic acid k-mer analysis, set operations on k-mers
  • Unanimity - Pacific Biosciences consensus library and applications
  • Ugene - Integrated bioinformatics toolkit
  • Ucsc-userapps - Command line tools from the UCSC Genome Browser project
  • Trimmomatic - Flexible read trimming tool for Illumina NGS data
  • Trimadap - Trim adapter sequences from Illumina data using heuristic rules