Repository navigation
fix(phylo): exclude skipped positions from the identity distance maximum - #5333
aniruddhaadak80 wants to merge 3 commits into
Conversation
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.
|
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. |
|
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: No reply needed beyond acknowledging the policy point, which you have made clearly and better than I could. |
Summary
DistanceCalculatorwith the defaultidentityscoring model returned inflated distances wheneverskip_letterswas 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, thescoring_matrix is Nonebranch built the score like this:The
scoresum filters out any position where either residue is inskip_letters, butmax_scorewas set to the full alignment length. Since the distance is1 - score / max_score, every skipped column acts as a permanent penalty: two identical sequences that differ only in gap columns scored1 - 4/6 = 0.333instead of0.0.The scoring-matrix branch below it already does the right thing (it increments
max_score1/max_score2inside 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 withDistanceTreeConstructorproduces a wrong topology for gap-rich alignments.Changes
Bio/Phylo/TreeConstruction.py- countmax_scoreonly over positions where neither residue is inskip_letters, so numerator and denominator are built from exactly the same filtered positions. Replaced thesum(...)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 distance0.0(this is the case that failed before);test_identity_skip_letters: a single substitution over the four scored columns gives1 - 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 --inplacefails withMicrosoft Visual C++ 14.0 or greater is required, so the compiledBio.Align._aligncoreextension is unavailable andTests/test_TreeConstruction.pycannot 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:
upstream/master)AC--GTvsAC--GT(identical, 2 of 6 skipped)AC--GTvsAC--GA(1 substitution)ACGTvsACGA(no gaps)ACGTvsACGT(no gaps)All assertions passed, and the bug reproduces under the pre-fix logic (
1 - 4/6 = 0.333333instead of0.0), which is the behaviour the newtest_identity_skip_letters_msalocks 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_distanceon realAlign/MSAlignmentobjects; CI, which builds the C extensions, is what will run them.Fixes #5332