pynw 0.1.0

Rust-accelerated Needleman-Wunsch global sequence alignment for precomputed score matrices.

pynw

Rust-accelerated Needleman-Wunsch global sequence alignment for precomputed score matrices.

Inspired by scipy.optimize.linear_sum_assignment: the same goal of robust, high-performance global matching from a NumPy-first interface, but specialized for ordered sequence alignment where gaps (insertions/deletions) are modeled.

Installation

pip install pynw

Requires Python 3.12+ and NumPy 1.26+.

Quick start

import numpy as np
from pynw import needleman_wunsch

# Build a score matrix for aligning "ab" against "abc"
# Rows = elements of seq1, Columns = elements of seq2
seq1, seq2 = "ab", "abc"
score_matrix = np.array(
    [[1 if a == b else -1 for b in seq2] for a in seq1],
    dtype=np.float64,
)

score, seq1_idx, seq2_idx = needleman_wunsch(
    score_matrix,
    gap_penalty_seq1=-1.0,
    gap_penalty_seq2=-1.0,
)

# score = 1.0
# seq1_idx = array([ 0,  1, -1])   (-1 = gap in seq1)
# seq2_idx = array([ 0,  1,  2])

for i, j in zip(seq1_idx, seq2_idx):
    s1 = seq1[i] if i >= 0 else "-"
    s2 = seq2[j] if j >= 0 else "-"
    print(f"{s1} <-> {s2}")
# a <-> a
# b <-> b
# - <-> c

API

needleman_wunsch(
    score_matrix: np.ndarray,
    gap_penalty_seq1: float = -1.0,
    gap_penalty_seq2: float = -1.0,
) -> tuple[float, np.ndarray, np.ndarray]

Parameters:

• score_matrix -- 2D array of shape (n, m) where score_matrix[i, j] is the similarity score for aligning element i of sequence 1 with element j of sequence 2. Non-2D inputs raise ValueError. Non-float inputs are cast to float64 automatically.
• gap_penalty_seq1 -- Penalty when a gap is inserted in sequence 1 (sequence 2 advances). Typically negative.
• gap_penalty_seq2 -- Penalty when a gap is inserted in sequence 2 (sequence 1 advances). Typically negative.

Returns:

• score -- The optimal alignment score.
• seq1_idx -- np.intp array of indices into sequence 1 at each alignment position. -1 indicates a gap.
• seq2_idx -- np.intp array of indices into sequence 2 at each alignment position. -1 indicates a gap.

The match-score component is composable, like linear_sum_assignment:

matched = (seq1_idx >= 0) & (seq2_idx >= 0)
score_matrix[seq1_idx[matched], seq2_idx[matched]].sum()  # match contribution

Empty matrices are supported and return a score of 0.0 with empty index arrays.

Why use this instead of linear_sum_assignment?

linear_sum_assignment solves unconstrained bipartite matching where order does not matter. Use needleman_wunsch when alignment must preserve order and model gaps (insertions/deletions), e.g. for strings, time series, or token sequences.

Why a precomputed score matrix?

Computing pairwise scores can be just as expensive as the alignment itself. By accepting a precomputed matrix, pynw lets you build scores in a vectorized fashion (e.g. with NumPy or a domain-specific library) outside of the Python-level loop, keeping the hot path fast. This design also makes the interface agnostic to the scoring function: any metric -- edit costs, embedding similarities, log-likelihoods -- works as long as you can fill an (n, m) array.

The trade-off is that you must allocate the full score matrix up front, which uses O(nm) memory even when the scoring rule could be expressed more compactly.

Scoring convention

• Matrix entries are added to the total score on diagonal moves.
• Gap penalties are added on gap moves, so they are typically negative.

Deterministic tie-breaking

When multiple moves are co-optimal, pynw uses:

DIAG > UP > LEFT

This affects which optimal path is returned, not the optimal score.

Edit-distance parameterizations

Needleman-Wunsch can reproduce common metrics with the right matrix/gap settings:

Metric	match	mismatch	gap	NW score equals
Levenshtein distance	0	-1	-1	-distance
Indel distance	0	-2	-1	-distance
LCS length	1	0	0	lcs_length
Hamming distance	0	-1	-(n+1)	-distance

For Hamming, strings must have equal length.

Non-goals

• Local alignment (Smith-Waterman)
• Affine gaps (gap-open + gap-extend)
• Heuristic / approximate alignment

Typing

pynw is a PEP 561 typed package. Type stubs are included, and the library is tested with mypy --strict.

Development

This repository uses pixi for development:

pixi install
pixi run build          # build the Rust extension
pixi run test           # run deterministic tests
pixi run test-hypothesis  # run property-based tests
pixi run lint           # run ruff linter
pixi run typecheck      # run mypy

License

MIT