Строим дерево: UPGMA

UPGMA строит дерево из матрицы расстояний, шаг за шагом объединяя ближайшие группы. Простой и наглядный алгоритм — реализуем его целиком.

UPGMA (Unweighted Pair Group Method with Arithmetic mean) — кластерный метод: на каждом шаге объединяет два ближайших кластера и пересчитывает расстояния как среднее.

Это самый понятный способ построить дерево. Он берёт матрицу попарных расстояний (например, по Хэммингу) и жадно склеивает ближайшие узлы, пока не останется один корень. По духу это иерархическая кластеризация — та же, что в машинном обучении.

Шаг 1: расстояния из последовательностей

Сначала превратим последовательности в матрицу расстояний. Возьмём долю/число различий (расстояние Хэмминга из раздела про паттерны).

def hamming(a, b):
    return sum(1 for x, y in zip(a, b) if x != y)

seqs = {
    'Человек':  'ACGTACGTAA',
    'Шимпанзе': 'ACGTACGTAA',
    'Мышь':     'ACGTTCGTAA',
    'Курица':   'TCGTACGAAC',
}
labels = list(seqs)
vals = list(seqs.values())
n = len(labels)
dist = [[hamming(vals[i], vals[j]) for j in range(n)] for i in range(n)]
print('     ' + ' '.join(f'{l[:4]:>4}' for l in labels))
for i in range(n):
    print(f'{labels[i][:4]:>4} ' + ' '.join(f'{dist[i][j]:>4}' for j in range(n)))

Вывод:

     Чело Шимп Мышь Кури
Чело    0    0    1    3
Шимп    0    0    1    3
Мышь    1    1    0    4
Кури    3    3    4    0

Видно: человек и шимпанзе идентичны (расстояние 0), мышь чуть дальше, курица — самая далёкая. UPGMA должен собрать это в дерево.

Шаг 2: алгоритм UPGMA

Повторяем: найти пару кластеров с минимальным расстоянием, объединить их, пересчитать расстояния от нового кластера до остальных как взвешенное среднее (по размерам). Так до единственного корня.

def hamming(a, b):
    return sum(1 for x, y in zip(a, b) if x != y)

def upgma(labels, dist):
    n = len(labels)
    tree = {i: labels[i] for i in range(n)}
    sizes = {i: 1 for i in range(n)}
    D = {}
    for i in range(n):
        for j in range(i + 1, n):
            D[(i, j)] = dist[i][j]
    active = set(range(n))
    nxt = n
    while len(active) > 1:
        (i, j), d = min(
            ((p, v) for p, v in D.items() if p[0] in active and p[1] in active),
            key=lambda kv: kv[1],
        )
        new = nxt
        nxt += 1
        tree[new] = '(' + tree[i] + ',' + tree[j] + ')'
        si, sj = sizes[i], sizes[j]
        sizes[new] = si + sj
        for k in list(active):
            if k in (i, j):
                continue
            di = D[(min(i, k), max(i, k))]
            dj = D[(min(j, k), max(j, k))]
            D[(min(new, k), max(new, k))] = (di * si + dj * sj) / (si + sj)
        active.discard(i)
        active.discard(j)
        active.add(new)
        print(f'объединяем: {tree[i]} + {tree[j]} (d={d:.2f})')
    return tree[active.pop()]

seqs = {'Человек': 'ACGTACGTAA', 'Шимпанзе': 'ACGTACGTAA',
        'Мышь': 'ACGTTCGTAA', 'Курица': 'TCGTACGAAC'}
labels = list(seqs); vals = list(seqs.values()); n = len(labels)
dist = [[hamming(vals[i], vals[j]) for j in range(n)] for i in range(n)]
print('Дерево:', upgma(labels, dist))

Вывод:

объединяем: Человек + Шимпанзе (d=0.00)
объединяем: Мышь + (Человек,Шимпанзе) (d=1.00)
объединяем: Курица + (Мышь,(Человек,Шимпанзе)) (d=3.33)
Дерево: (Курица,(Мышь,(Человек,Шимпанзе)))

Алгоритм восстановил осмысленное дерево: сначала склеил идентичных человека и шимпанзе, затем добавил мышь, и последней — далёкую курицу. В скобочной (Newick) записи это (Курица,(Мышь,(Человек,Шимпанзе))).

Как работает под капотом: допущение молекулярных часов

UPGMA прост, но делает сильное допущение — молекулярные часы: что все линии эволюционируют с одинаковой скоростью. Если одна линия мутирует быстрее (например, у вирусов или мелких животных с быстрым обменом), UPGMA может ошибиться в топологии — «притянуть» быстро меняющуюся линию ближе к корню. Метод neighbor-joining (NJ) снимает это допущение и потому популярнее для реальных данных. Но как первый и самый наглядный алгоритм UPGMA незаменим.

Частые ошибки

• Применять UPGMA при неравных скоростях эволюции. Нарушение молекулярных часов искажает дерево; берите neighbor-joining.
• Неверно пересчитывать расстояния. Новое расстояние — взвешенное по размерам кластеров среднее, а не простое.
• Строить дерево на мусорной матрице. Плохие расстояния (без выравнивания, с шумом) дают бессмысленное дерево.

Итог

• UPGMA строит дерево из матрицы расстояний, жадно объединяя ближайшие кластеры.
• Расстояния берут из выравнивания (например, число различий по Хэммингу).
• Новое расстояние — среднее, взвешенное по размерам объединённых кластеров.
• UPGMA предполагает молекулярные часы; при неравных скоростях лучше neighbor-joining.