Optimal gap-affine alignment in O(s) space.

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

SUBMITTER: Marco-Sola S 

PROVIDER: S-EPMC9940620 | biostudies-literature | 2023 Feb

REPOSITORIES: biostudies-literature