Instead of looking at the entire sequence, the Smith–Waterman algorithm compares segments of all possible lengths and optimizes the similarity measure.

As such, it has the desirable property that it is guaranteed to find the optimal local alignment with respect to the scoring system being used (which includes the substitution matrix and the gap-scoring scheme).

Because of its cubic time complexity, it often cannot be practically applied to large-scale problems and is replaced in favor of computationally more efficient alternatives such as (Gotoh, 1982),[2] (Altschul and Erickson, 1986),[3] and (Myers and Miller, 1988).

In the following decade, Sankoff,[6] Reichert,[7] Beyer[8] and others formulated alternative heuristic algorithms for analyzing gene sequences.

Chowdhury, Le, and Ramachandran[11] later optimized the cache performance of the algorithm while keeping the space usage linear in the total length of the input sequences.

In recent years, genome projects conducted on a variety of organisms generated massive amounts of sequence data for genes and proteins, which requires computational analysis.

Sequence alignment shows the relations between genes or between proteins, leading to a better understanding of their homology and functionality.

Local alignment avoids such regions altogether and focuses on those with a positive score, i.e. those with an evolutionarily conserved signal of similarity.

This property allows programs to produce an expectation value for the optimal local alignment of two sequences, which is a measure of how often two unrelated sequences would produce an optimal local alignment whose score is greater than or equal to the observed score.

Very low expectation values indicate that the two sequences in question might be homologous, meaning they might share a common ancestor.

In Needleman–Wunsch algorithm, however, end gap penalty also needs to be considered in order to align the full sequences.

[3] Altschul modified Gotoh's algorithm to find all optimal alignments while maintaining the computational complexity.

Chowdhury, Le, and Ramachandran[11] later showed how to run Gotoh's algorithm cache-efficiently in linear space using a different recursive divide-and-conquer strategy than the one used by Hirschberg.

When linear gap penalty function is used, the result is (Alignments performed by EMBOSS Water.

The function of the scoring matrix is to conduct one-to-one comparisons between all components in two sequences and record the optimal alignment results.

This implementation includes Altivec accelerated code for PowerPC G4 and G5 processors that speeds up comparisons 10–20-fold, using a modification of the Wozniak, 1997 approach,[13] and an SSE2 vectorization developed by Farrar[14] making optimal protein sequence database searches quite practical.

A library, SSW, extends Farrar's implementation to return alignment information in addition to the optimal Smith–Waterman score.

[15] Cray demonstrated acceleration of the Smith–Waterman algorithm using a reconfigurable computing platform based on FPGA chips, with results showing up to 28x speed-up over standard microprocessor-based solutions.

Another FPGA-based version of the Smith–Waterman algorithm shows FPGA (Virtex-4) speedups up to 100x[16] over a 2.2 GHz Opteron processor.

In a 2016 publication OpenCL code compiled with Xilinx SDAccel accelerates genome sequencing, beats CPU/GPU performance/W by 12-21x, a very efficient implementation was presented.

Lawrence Livermore National Laboratory and the United States (US) Department of Energy's Joint Genome Institute implemented an accelerated version of Smith–Waterman local sequence alignment searches using graphics processing units (GPUs) with preliminary results showing a 2x speed-up over software implementations.

A newer GPU CUDA implementation of SW is now available that is faster than previous versions and also removes limitations on query lengths.

The SSEARCH is included in the European Bioinformatics Institute's suite of similarity searching programs.

Danish bioinformatics company CLC bio has achieved speed-ups of close to 200 over standard software implementations with SSE2 on an Intel 2.17 GHz Core 2 Duo CPU, according to a publicly available white paper.

Accelerated version of the Smith–Waterman algorithm, on Intel and Advanced Micro Devices (AMD) based Linux servers, is supported by the GenCore 6 package, offered by Biocceleration.

[citation needed] The fastest implementation of the algorithm on CPUs with SSSE3 can be found the SWIPE software (Rognes, 2011),[25] which is available under the GNU Affero General Public License.

Using a 375 residue query sequence a speed of 106 billion cell updates per second (GCUPS) was achieved on a dual Intel Xeon X5650 six-core processor system, which is over six times more rapid than software based on Farrar's 'striped' approach.

In 2008, Farrar[26] described a port of the Striped Smith–Waterman[14] to the Cell Broadband Engine and reported speeds of 32 and 12 GCUPS on an IBM QS20 blade and a Sony PlayStation 3, respectively.

Fast expansion of genetic data challenges speed of current DNA sequence alignment algorithms.

Essential needs for an efficient and accurate method for DNA variant discovery demand innovative approaches for parallel processing in real time.