Phylogenetic Analysis

[xmkrohannon]

Setup

The existing upgma function is not an implementation of the UPGMA (Unweighted Pair Group Method with Arithmetic mean) method, it is an implementation of the WPGMA (Weighted Pair Group Method with Arithmetic mean).

When computing the distance matrix for the tree of internal nodes, it should not be equal to the average of the two merged clades, it should be the average of the total merged clades:

It currently reads:
# rebuild distance matrix,
# set the distances of new node at the index of min_j
for k in range(0, len(dm)):
if k != min_i and k != min_j:
dm[min_j, k] = (dm[min_i, k] + dm[min_j, k]) / 2

It should read:
size_clade1 = max(len(clades[min_i].clades), 1)
size_clade2 = max(len(clades[min_j].clades), 1)
# rebuild distance matrix,
# set the distances of new node at the index of min_j
for k in range(0, len(dm)):
if k != min_i and k != min_j:
dm[min_j, k] = (dm[min_i, k] * size_clade1 + dm[min_j, k] * size_clade2) / (size_clade1 + size_clade2)

Additional features should be added: single linkage, complete linkage, and Fitch–Margoliash methodologies, as well as some functionality to calculate goodness of fit.

import sys; print(sys.version)
import platform; print(platform.python_implementation()); print(platform.platform())
import Bio; print(Bio.__version__)

3.9.13 (main, Oct 13 2022, 21:15:33)
[GCC 11.2.0]
CPython
Linux-5.15.0-97-generic-x86_64-with-glibc2.35
1.78

(Please copy and run the above in your Python, and copy-and-paste the output)

Expected behaviour

{'A': 8.5, 'B': 8.5, 'Inner1': 2.5, 'E': 11, 'Inner2': 5.5, 'C': 14, 'D': 14, 'Inner3': 2.5, 'Inner4': 0}

Actual behaviour

{'A': 8.5, 'B': 8.5, 'Inner1': 2.5, 'E': 11, 'Inner2': 6.5, 'C': 14, 'D': 14, 'Inner3': 3.5, 'Inner4': 0}

Steps to reproduce

test = DistanceMatrix(names = ['A', 'B', 'C', 'D', 'E'], matrix = [[0], [17, 0], [21, 30, 0], [31, 34, 28, 0], [23, 21, 39, 43, 0]])
model = DistanceTreeConstructor()
tree = model.upgma(test)
Phylo.draw(tree, branch_labels = lambda c: (f'{c.branch_length: .3f}') if c.branch_length != 0 else 0)