StringZilla v5

What is StringZilla v5?

StringZilla v5 is an open-source, high-performance string-processing library developed by Ash Vardanian. It accelerates search, hashing, sorting, edit distances, and biological sequence scoring by using hardware-specific SIMD, SWAR, and GPU backends across modern processor architectures.

ProteinIQ runs StringZilla's CPU-accelerated batch engines for Levenshtein distance, Needleman-Wunsch global scoring, and Smith-Waterman local scoring. These methods are designed for questions that need every comparison in a sequence set or every query-by-candidate combination, such as finding near-duplicate constructs, comparing variant libraries, or building a similarity matrix before clustering.

The result is a numeric matrix, not a set of aligned sequences. StringZilla does not return traceback paths, gap placement, percent identity, E-values, or statistical significance. For an inspectable multiple sequence alignment, use MAFFT or Clustal Omega. For searching a large database while reporting only meaningful hits, MMseqs2 avoids materializing the full cross-product matrix.

How to use StringZilla online

Run StringZilla online by submitting FASTA records as one self-comparison set or as separate query and candidate sets. Choose Levenshtein distance, Needleman-Wunsch global scoring, or Smith-Waterman local scoring. ProteinIQ returns every pair in a searchable table, a rectangular matrix CSV, a long-form CSV, and an execution log.

Inputs and comparison modes

FASTA headers become the sequence identifiers in the output. Sequence lines must be non-empty and cannot contain internal whitespace.

Mode	Input	Comparisons returned
All pairs within one sequence set	One FASTA set containing one or more records	A square $N \times N$ matrix, including the diagonal and both directions of each pair
Queries against candidates	One query FASTA set and one candidate FASTA set	A rectangular $Q \times C$ matrix containing every query-candidate combination

Accepted file extensions are .fasta, .fa, .fas, and .txt. A run may contain at most 100,000 sequence symbols across the active inputs and at most 100,000 matrix cells. A self comparison of 100 sequences therefore returns 10,000 rows, while 500 queries against 200 candidates reaches the 100,000-cell limit.

StringZilla treats the submitted sequence characters as symbols. Protein, DNA, and RNA records can be compared in the same tool, but molecule type is not inferred and biologically incompatible alphabets are not rejected. Mixed alphabets produce numeric results that usually have no useful biological interpretation.

Choosing an algorithm

Algorithm	What it measures	Best suited to	Direction
Levenshtein edit distance	Minimum cost of substitutions, insertions, and deletions needed to transform one sequence into another	Near-duplicate detection, construct verification, barcode comparison, and short variant sets	Lower is more similar
Needleman-Wunsch global score	Best end-to-end alignment score under the selected match, mismatch, and affine-gap values	Sequences expected to correspond across their full lengths	Higher is more similar
Smith-Waterman local score	Best-scoring pair of local subsequences	Shared motifs or domains within otherwise different sequences	Higher is more similar

Levenshtein distance is the easiest choice when each change should have a direct cost. Needleman-Wunsch is more appropriate when terminal differences and internal gaps must affect a full-length comparison. Smith-Waterman ignores poorly matching flanks by selecting the strongest local region, so a high score can reflect one shared segment rather than overall sequence similarity.

Levenshtein costs

Setting	Range	Default	Effect
Match cost	-128 to 127	0	Cost assigned when the two symbols are equal
Mismatch cost	-128 to 127	1	Cost of substituting one symbol for another
Gap-open cost	-128 to 127	1	Cost of starting an insertion or deletion run
Gap-extension cost	-128 to 127	1	Cost of extending an insertion or deletion run

All four costs must be integers because the StringZilla engine stores them as signed 8-bit values.

The defaults produce the familiar unit-cost edit distance: identical sequences have distance 0, and each substitution, insertion, or deletion increases the distance. Changing the four values creates a weighted edit cost. Negative costs are accepted by the engine, but the result no longer behaves like a conventional mathematical distance, so zero and lower values no longer have their usual interpretation.

Global and local alignment scoring

Setting	Range	Default	Effect
Match score	-128 to 127	1	Score on the diagonal of the identity-style substitution table
Mismatch score	-128 to 127	0	Score for every unequal symbol pair
Gap-open score	-128 to 127	-1	Penalty for starting a gap
Gap-extension score	-128 to 127	-1	Penalty for extending a gap

All four scores must be integers because the StringZilla engine stores them as signed 8-bit values.

These controls define a compact identity-style substitution table. Every exact symbol match receives the same score, and every mismatch receives the same score. Protein substitutions therefore do not receive BLOSUM or PAM values, and transitions and transversions in nucleotide sequences are not distinguished. Needleman-Wunsch and Smith-Waterman runs support at most 32 distinct encoded symbols across all submitted sequences.

The default scoring rewards exact matches, leaves mismatches neutral, and penalizes gaps. Raising Match score increases the influence of exact identity. Making Mismatch score more negative discourages mismatched regions, while stronger negative gap values make insertions and deletions less favorable. The current tool does not accept a custom substitution matrix.

Results and downloads

The Pairwise results table preserves query-major, candidate-minor order. It is not sorted by similarity, because every cell in the matrix is returned.

Column	Description
Query #	One-based position of the query record in the submitted FASTA
Query ID	Text following the query FASTA header marker
Candidate #	One-based position of the candidate record
Candidate ID	Candidate FASTA identifier
Edit distance	Weighted Levenshtein distance, present for Levenshtein runs
Alignment score	Global or local alignment score, present for Needleman-Wunsch and Smith-Waterman runs

Three files accompany the table:

• stringzilla-distances.csv or stringzilla-scores.csv: Long-form rows matching the displayed results table
• stringzilla-matrix.csv: The same values arranged with queries as rows and candidates as columns
• stringzilla-run.log: Algorithm, comparison mode, sequence counts, matrix size, runtime, and detected CPU capabilities

Interpreting StringZilla results

Levenshtein distance

With the default costs, a distance of 0 means the two sequences are identical. A distance of 1 means that one substitution, insertion, or deletion separates them. Raw distance grows with sequence length, so distance 5 is a much larger difference for a 20-residue peptide than for a 1,000-residue protein.

For default unit costs, a useful length-adjusted summary is:

$$\text{normalized edit similarity} = 1 - \frac{d}{\max(L_q, L_c)}$$

Here, $d$ is Edit distance, and $L_q$ and $L_c$ are the two sequence lengths. The value ranges from 0 to 1 for standard unit-cost comparisons, with 1 indicating identical sequences. It should not be applied unchanged after assigning unusual or negative costs.

Needleman-Wunsch score

Needleman-Wunsch compares both sequences end to end. A high score indicates that many symbols can be matched while paying relatively few mismatch and gap penalties. Length strongly affects the result, so raw scores are most useful when all sequences have similar lengths and every run uses the same settings.

The diagonal of a self-comparison matrix gives each sequence scored against itself. Comparing an off-diagonal score with the corresponding diagonal values can provide context, but it is not a calibrated probability or percent identity. A lower score can result from substitutions, terminal length differences, internal indels, or a combination of all three.

Smith-Waterman score

Smith-Waterman reports the best local score. Unrelated flanking regions do not need to participate, which makes the method useful for detecting a shared motif or domain. The score alone does not reveal where that region occurs or how long it is. Two pairs can receive the same score from very different local segments.

Because StringZilla returns no traceback, a promising pair should be aligned with a method that reports aligned residues before making positional or mechanistic claims. MAFFT is suitable when the selected sequences belong in a common multiple alignment; Clustal Omega is another scalable option for homologous sets.

How StringZilla works

StringZilla was developed by Ash Vardanian as a high-performance string-processing library. Its StringZillas batch engines calculate Levenshtein matrices and Needleman-Wunsch or Smith-Waterman score matrices across collections of sequences. ProteinIQ runs the CPU backend and lets the library select the available SIMD or SWAR capabilities automatically.

Dynamic-programming sequence comparison normally fills a matrix whose cells depend on neighboring cells. StringZilla traverses independent anti-diagonals so multiple cells can be evaluated together with vector instructions. The batch interface also parallelizes work across many sequence pairs, which is particularly useful for complete self and cross comparisons.

Acceleration changes how quickly the score matrix is computed, not what the score means. Levenshtein still minimizes edit cost, Needleman-Wunsch still scores a global comparison, and Smith-Waterman still selects a local one. The output contains the final value for every sequence pair rather than each algorithm's internal dynamic-programming matrix.

When to use StringZilla instead of an alignment or search tool

Goal	Better starting point	Reason
Compare every member of a moderate sequence set	StringZilla	Returns the complete pairwise matrix with no hit filtering
Find near-identical constructs or barcodes	StringZilla with Levenshtein	Edit counts have a direct interpretation under unit costs
Score full-length correspondence	StringZilla with Needleman-Wunsch	Both sequence ends participate in the global score
Detect a shared local segment	StringZilla with Smith-Waterman	Poorly matching flanks can be excluded from the score
Inspect residue correspondence and gap placement	MAFFT or Clustal Omega	These tools return aligned sequences rather than scores alone
Search a large sequence database for homologs	MMseqs2	Prefiltering avoids calculating and storing every possible pair and adds hit statistics

Complete matrices scale as $N^2$ in self mode and $Q \times C$ in cross mode. StringZilla is therefore most useful when every cell is genuinely needed. For a million-sequence database search, a filtered search method is both more practical and more informative than a full matrix.