Fast gap-affine pairwise alignment using the wavefront algorithm.

ABSTRACT:

Motivation

Pairwise alignment of sequences is a fundamental method in modern molecular biology, implemented within multiple bioinformatics tools and libraries. Current advances in sequencing technologies press for the development of faster pairwise alignment algorithms that can scale with increasing read lengths and production yields.

Results

In this article, we present the wavefront alignment algorithm (WFA), an exact gap-affine algorithm that takes advantage of homologous regions between the sequences to accelerate the alignment process. As opposed to traditional dynamic programming algorithms that run in quadratic time, the WFA runs in time O(ns), proportional to the read length n and the alignment score s, using O(s2) memory. Furthermore, our algorithm exhibits simple da

SUBMITTER: Marco-Sola S 

PROVIDER: S-EPMC8355039 | biostudies-literature | 2021 May

REPOSITORIES: biostudies-literature