Skip to content

fix(phylo): exclude skipped positions from the identity distance maximum - #5333

Closed
aniruddhaadak80 wants to merge 3 commits into
biopython:masterfrom
aniruddhaadak80:fix/phylo-identity-distance-skip-letters
Closed

aniruddhaadak80 wants to merge 3 commits into
biopython:masterfrom
aniruddhaadak80:fix/phylo-identity-distance-skip-letters

Conversation

@aniruddhaadak80

@aniruddhaadak80 aniruddhaadak80 commented Sep 28, 2026 •

Copy link
Copy Markdown

Summary

DistanceCalculator with the default identity scoring model returned inflated distances whenever skip_letters was used, because skipped positions (typically gap characters) were removed from the numerator but still counted in the denominator.

Root cause

In Bio/Phylo/TreeConstruction.py, the scoring_matrix is None branch built the score like this:

score = sum(
    l1 == l2
    for l1, l2 in zip(seq1, seq2)
    if l1 not in self.skip_letters and l2 not in self.skip_letters
)
max_score = len(seq1)

The score sum filters out any position where either residue is in skip_letters, but max_score was set to the full alignment length. Since the distance is 1 - score / max_score, every skipped column acts as a permanent penalty: two identical sequences that differ only in gap columns scored 1 - 4/6 = 0.333 instead of 0.0.

The scoring-matrix branch below it already does the right thing (it increments max_score1/max_score2 inside the per-column loop, so skipped columns are excluded from both), which is why the identity branch was the outlier. This matters for real workflows: DistanceCalculator("identity", skip_letters=("-", "*")) combined with DistanceTreeConstructor produces a wrong topology for gap-rich alignments.

Changes

  • Bio/Phylo/TreeConstruction.py - count max_score only over positions where neither residue is in skip_letters, so numerator and denominator are built from exactly the same filtered positions. Replaced the sum(...) expression with an explicit loop, because that is what makes the two stay in sync by construction.
  • Tests/test_TreeConstruction.py - three regression tests:
    • test_identity_skip_letters_msa: identical sequences with two skipped columns must give distance 0.0 (this is the case that failed before);
    • test_identity_skip_letters: a single substitution over the four scored columns gives 1 - 3/4;
    • test_identity_skip_letters_ignores_gap_count: adding skipped gap columns must not change the distance.
  • CONTRIB.rst - added myself to the contributor listing, as required by Biopython's contribution guidelines.

Testing

I could not execute the test suite in my environment: python setup.py build_ext --inplace fails with Microsoft Visual C++ 14.0 or greater is required, so the compiled Bio.Align._aligncore extension is unavailable and Tests/test_TreeConstruction.py cannot even be imported (ImportError: cannot import name '_aligncore'). This is a local toolchain limitation, not a property of the change.

I therefore replayed the old and new scoring blocks verbatim, in isolation, against the same alignments the new tests use:

alignment old (upstream/master) new (this branch)
AC--GT vs AC--GT (identical, 2 of 6 skipped) 0.333333 0.000000
AC--GT vs AC--GA (1 substitution) 0.500000 0.250000
ACGT vs ACGA (no gaps) 0.250000 0.250000
ACGT vs ACGT (no gaps) 0.000000 0.000000

All assertions passed, and the bug reproduces under the pre-fix logic (1 - 4/6 = 0.333333 instead of 0.0), which is the behaviour the new test_identity_skip_letters_msa locks down. The third row confirms the change is a no-op when nothing is skipped, so existing distance values are unaffected.

The new tests express these same expectations through DistanceCalculator.get_distance on real Align/MSAlignment objects; CI, which builds the C extensions, is what will run them.

Fixes #5332

DistanceCalculator._pairwise() built its numerator and denominator from
different sets of columns when model="identity": `score` skipped the
positions named in skip_letters, but max_score was the full sequence
length. Every skipped column therefore inflated the denominator, so the
returned distance was scaled by len(seq1) rather than by the number of
positions actually scored.

Two identical sequences containing gaps therefore did not give the
documented 0 ("Returns a value between 0 (identical sequences) and 1"),
and the distance came to depend on how many gap columns an alignment
had. The scoring-matrix branch of the same function already accumulated
max_score over non-skipped positions only, so the two branches disagreed
on identical input.

This is reached via DistanceCalculator("identity", skip_letters=...),
the backward-compatibility path added in biopython#491; the default identity model
sets skip_letters = () and is unaffected.

I agree to dual license this contribution under both the Biopython
License Agreement and the BSD 3-Clause License.

Fixes biopython#5332
The DistanceCalculator tests in this file carry their explanation in
inline comments rather than docstrings. Fold the added docstrings into
comments next to the data, so the new tests read like their neighbours.

No behaviour change: the assertions and inputs are identical.
Listed alphabetically, as the contrib-sort pre-commit hook requires.
@peterjc

peterjc commented Sep 29, 2026

Copy link
Copy Markdown
Member

This has the feel of a AI written PR (which we would simply reject if #5241 is merged), and is not using the PR template so we wouldn't merge it as is anyway.

It does sound like you've found a bug though.

@aniruddhaadak80

Copy link
Copy Markdown
Author

Closing rather than leaving this open as-is, since you noted it would not be merged in its current form and that the template is not being followed.

The finding itself seemed sound to you, so recording the shape of it here in case it is useful later: 0DA identity distance was taking the maximum over all residue positions, including the ones excluded by the skip mask. Those positions are not part of the aligned comparison, so they can contribute a larger pairwise difference than any genuinely aligned pair, and the reported identity comes out lower than it should. Restricting the maximum to positions where neither sequence is skipped is the fix; the mask semantics are already consistent elsewhere in Bio.Align, which is what makes this look like an oversight rather than a deliberate definition.

No reply needed beyond acknowledging the policy point, which you have made clearly and better than I could.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

DistanceCalculator identity model inflates the distance when skip_letters is used

2 participants