УПГМА

Метод агломеративной иерархической кластеризации

UPGMA ( невзвешенный парный групповой метод с арифметическим средним ) — это простой агломеративный (снизу вверх) иерархический метод кластеризации . Он также имеет взвешенный вариант, WPGMA , и они, как правило, приписываются Сокалу и Миченеру . ^[1]

Обратите внимание, что невзвешенный термин указывает на то, что все расстояния вносят одинаковый вклад в каждое вычисляемое среднее значение, и не относится к математике, с помощью которой оно достигается. Таким образом, простое усреднение в WPGMA дает взвешенный результат, а пропорциональное усреднение в UPGMA дает невзвешенный результат ( см. рабочий пример ). ^[2]

Алгоритм

Алгоритм UPGMA строит корневое дерево ( дендрограмму ), которое отражает структуру, представленную в матрице парного сходства (или матрице различий ). На каждом шаге ближайшие два кластера объединяются в кластер более высокого уровня. Расстояние между любыми двумя кластерами и , каждый из которых имеет размер ( т.е. мощность ) и , принимается равным среднему значению всех расстояний между парами объектов в и в , то есть среднему расстоянию между элементами каждого кластера: ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {B}}}$ ${\displaystyle {|{\mathcal {A}}|}}$ ${\displaystyle {|{\mathcal {B}}|}}$ ${\displaystyle d(x,y)}$ ${\displaystyle x}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle y}$ ${\displaystyle {\mathcal {B}}}$

${\displaystyle {1 \over {|{\mathcal {A}}|\cdot |{\mathcal {B}}|}}\sum _{x\in {\mathcal {A}}}\sum _{y\in {\mathcal {B}}}d(x,y)}$

Другими словами, на каждом шаге кластеризации обновленное расстояние между объединенными кластерами и новым кластером определяется пропорциональным усреднением расстояний и : ${\displaystyle {\mathcal {A}}\cup {\mathcal {B}}}$ ${\displaystyle X}$ ${\displaystyle d_{{\mathcal {A}},X}}$ ${\displaystyle d_{{\mathcal {B}},X}}$

${\displaystyle d_{({\mathcal {A}}\cup {\mathcal {B}}),X}={\frac {|{\mathcal {A}}|\cdot d_{{\mathcal {A}},X}+|{\mathcal {B}}|\cdot d_{{\mathcal {B}},X}}{|{\mathcal {A}}|+|{\mathcal {B}}|}}}$

Алгоритм UPGMA создает корневые дендрограммы и требует предположения о постоянной скорости, то есть он предполагает ультраметрическое дерево, в котором расстояния от корня до каждой верхушки ветви равны. Когда верхушки представляют собой молекулярные данные ( например , ДНК , РНК и белок ), отобранные в одно и то же время, предположение об ультраметричности становится эквивалентным предположению о молекулярных часах .

Рабочий пример

Этот рабочий пример основан на матрице генетических расстояний JC69 , вычисленной на основе выравнивания последовательностей рибосомной РНК 5S пяти бактерий: Bacillus subtilis ( ), Bacillus stearothermophilus ( ), Lactobacillus viridescens ( ), Acholeplasma modicum ( ) и Micrococcus luteus ( ). ^{[3] [4]} ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle d}$ ${\displaystyle e}$

Первый шаг

• Первая кластеризация

Предположим, что у нас есть пять элементов и следующая матрица попарных расстояний между ними: ${\displaystyle (a,b,c,d,e)}$ ${\displaystyle D_{1}}$

В этом примере — наименьшее значение , поэтому мы объединяем элементы и . ${\displaystyle D_{1}(a,b)=17}$ ${\displaystyle D_{1}}$ ${\displaystyle a}$ ${\displaystyle b}$

• Оценка длины первой ветви

Пусть обозначает узел, к которому теперь подключены и . Настройка гарантирует, что элементы и равноудалены от . Это соответствует ожиданию гипотезы ультраметричности . Ветви, соединяющие и , затем имеют длины ( см. окончательную дендрограмму ) ${\displaystyle u}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle \delta (a,u)=\delta (b,u)=D_{1}(a,b)/2}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle u}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle u}$ ${\displaystyle \delta (a,u)=\delta (b,u)=17/2=8.5}$

• Первое обновление матрицы расстояний

Затем мы приступаем к обновлению исходной матрицы расстояний в новую матрицу расстояний (см. ниже), уменьшенную в размере на одну строку и один столбец из-за кластеризации с . Жирные значения в соответствуют новым расстояниям, рассчитанным путем усреднения расстояний между каждым элементом первого кластера и каждым из оставшихся элементов: ${\displaystyle D_{1}}$ ${\displaystyle D_{2}}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle D_{2}}$ ${\displaystyle (a,b)}$

${\displaystyle D_{2}((a,b),c)=(D_{1}(a,c)\times 1+D_{1}(b,c)\times 1)/(1+1)=(21+30)/2=25.5}$

${\displaystyle D_{2}((a,b),d)=(D_{1}(a,d)+D_{1}(b,d))/2=(31+34)/2=32.5}$

${\displaystyle D_{2}((a,b),e)=(D_{1}(a,e)+D_{1}(b,e))/2=(23+21)/2=22}$

Выделенные курсивом значения не затронуты обновлением матрицы, поскольку они соответствуют расстояниям между элементами, не входящими в первый кластер. ${\displaystyle D_{2}}$

Второй шаг

• Вторая кластеризация

Теперь повторим три предыдущих шага, начиная с новой матрицы расстояний ${\displaystyle D_{2}}$

Здесь — наименьшее значение , поэтому мы объединяем кластер и элемент . ${\displaystyle D_{2}((a,b),e)=22}$ ${\displaystyle D_{2}}$ ${\displaystyle (a,b)}$ ${\displaystyle e}$

• Оценка длины второй ветви

Пусть обозначает узел, к которому теперь подключены и . Из-за ограничения ультраметричности ветви, соединяющие или с , и с , равны и имеют следующую длину: ${\displaystyle v}$ ${\displaystyle (a,b)}$ ${\displaystyle e}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle v}$ ${\displaystyle e}$ ${\displaystyle v}$ ${\displaystyle \delta (a,v)=\delta (b,v)=\delta (e,v)=22/2=11}$

Вычисляем недостающую длину ветви: ( см. окончательную дендрограмму ) ${\displaystyle \delta (u,v)=\delta (e,v)-\delta (a,u)=\delta (e,v)-\delta (b,u)=11-8.5=2.5}$

• Второе обновление матрицы расстояний

Затем мы переходим к обновлению в новую матрицу расстояний (см. ниже), уменьшенную в размере на одну строку и один столбец из-за кластеризации с . Жирные значения в соответствуют новым расстояниям, рассчитанным путем пропорционального усреднения : ${\displaystyle D_{2}}$ ${\displaystyle D_{3}}$ ${\displaystyle (a,b)}$ ${\displaystyle e}$ ${\displaystyle D_{3}}$

${\displaystyle D_{3}(((a,b),e),c)=(D_{2}((a,b),c)\times 2+D_{2}(e,c)\times 1)/(2+1)=(25.5\times 2+39\times 1)/3=30}$

Благодаря этому пропорциональному среднему, расчет этого нового расстояния учитывает больший размер кластера (два элемента) по отношению к (одному элементу). Аналогично: ${\displaystyle (a,b)}$ ${\displaystyle e}$

${\displaystyle D_{3}(((a,b),e),d)=(D_{2}((a,b),d)\times 2+D_{2}(e,d)\times 1)/(2+1)=(32.5\times 2+43\times 1)/3=36}$

Пропорциональное усреднение, таким образом, дает равный вес начальным расстояниям матрицы . Это причина, по которой метод является невзвешенным , не по отношению к математической процедуре, а по отношению к начальным расстояниям. ${\displaystyle D_{1}}$

Третий шаг

• Третья кластеризация

Мы снова повторяем три предыдущих шага, начиная с обновленной матрицы расстояний . ${\displaystyle D_{3}}$

Здесь — наименьшее значение , поэтому мы объединяем элементы и . ${\displaystyle D_{3}(c,d)=28}$ ${\displaystyle D_{3}}$ ${\displaystyle c}$ ${\displaystyle d}$

• Оценка длины третьей ветви

Пусть обозначает узел, к которому теперь присоединены и . Ветви, соединяющие и , тогда имеют длины ( см. окончательную дендрограмму ) ${\displaystyle w}$ ${\displaystyle c}$ ${\displaystyle d}$ ${\displaystyle c}$ ${\displaystyle d}$ ${\displaystyle w}$ ${\displaystyle \delta (c,w)=\delta (d,w)=28/2=14}$

• Третье обновление матрицы расстояний

Необходимо обновить одну запись, учитывая, что два элемента и каждый из них вносит вклад в среднее вычисление : ${\displaystyle c}$ ${\displaystyle d}$ ${\displaystyle 1}$

${\displaystyle D_{4}((c,d),((a,b),e))=(D_{3}(c,((a,b),e))\times 1+D_{3}(d,((a,b),e))\times 1)/(1+1)=(30\times 1+36\times 1)/2=33}$

Последний шаг

Окончательная матрица: ${\displaystyle D_{4}}$

Итак, мы объединяем кластеры и . ${\displaystyle ((a,b),e)}$ ${\displaystyle (c,d)}$

Пусть обозначает (корневой) узел, к которому теперь присоединены и . Ветви, соединяющие и , тогда имеют длины: ${\displaystyle r}$ ${\displaystyle ((a,b),e)}$ ${\displaystyle (c,d)}$ ${\displaystyle ((a,b),e)}$ ${\displaystyle (c,d)}$ ${\displaystyle r}$

${\displaystyle \delta (((a,b),e),r)=\delta ((c,d),r)=33/2=16.5}$

Выводим две оставшиеся длины ветвей:

${\displaystyle \delta (v,r)=\delta (((a,b),e),r)-\delta (e,v)=16.5-11=5.5}$

${\displaystyle \delta (w,r)=\delta ((c,d),r)-\delta (c,w)=16.5-14=2.5}$

Дендрограмма UPGMA

Дендрограмма теперь завершена. ^[5] Она является ультраметрической, поскольку все кончики ( от до ) равноудалены от  : ${\displaystyle a}$ ${\displaystyle e}$ ${\displaystyle r}$

${\displaystyle \delta (a,r)=\delta (b,r)=\delta (e,r)=\delta (c,r)=\delta (d,r)=16.5}$

Таким образом, дендрограмма имеет корневую точку — самый глубокий узел. ${\displaystyle r}$

Сравнение с другими связями

Альтернативные схемы связей включают кластеризацию с одинарной связью , кластеризацию с полной связью и кластеризацию со средней связью WPGMA . Реализация другой связи — это просто вопрос использования другой формулы для расчета межкластерных расстояний во время шагов обновления матрицы расстояний вышеуказанного алгоритма. Кластеризация с полной связью позволяет избежать недостатка альтернативного метода кластеризации с одинарной связью — так называемого феномена сцепления , когда кластеры, сформированные с помощью кластеризации с одинарной связью, могут быть вынуждены объединиться из-за того, что отдельные элементы находятся близко друг к другу, даже если многие элементы в каждом кластере могут быть очень далеки друг от друга. Полная связь имеет тенденцию находить компактные кластеры примерно одинакового диаметра. ^[6]

Использует

• В экологии это один из самых популярных методов классификации единиц выборки (например, участков растительности) на основе их парного сходства в соответствующих дескрипторных переменных (например, видовом составе). ^[7] Например, он использовался для понимания трофического взаимодействия между морскими бактериями и простейшими. ^[8]
• В биоинформатике UPGMA используется для создания фенетических деревьев (фенограмм). Первоначально UPGMA был разработан для использования в исследованиях электрофореза белков , но в настоящее время чаще всего используется для создания направляющих деревьев для более сложных алгоритмов. Этот алгоритм, например, используется в процедурах выравнивания последовательностей , поскольку он предлагает один порядок, в котором последовательности будут выровнены. Действительно, направляющее дерево направлено на группировку наиболее похожих последовательностей, независимо от их эволюционной скорости или филогенетического сродства, и это как раз и есть цель UPGMA ^[9]
• В филогенетике UPGMA предполагает постоянную скорость эволюции ( гипотеза молекулярных часов ) и то, что все последовательности были отобраны в одно и то же время, и не является общепризнанным методом для вывода взаимосвязей, если это предположение не было проверено и обосновано для используемого набора данных. Обратите внимание, что даже при «строгих часах» последовательности, отобранные в разное время, не должны приводить к ультраметрическому дереву.

Сложность времени

Тривиальная реализация алгоритма построения дерева UPGMA имеет временную сложность, а использование кучи для каждого кластера для сохранения его расстояний от других кластеров сокращает его время до . Фионн Муртаг представил временной и пространственный алгоритм. ^[10] ${\displaystyle O(n^{3})}$ ${\displaystyle O(n^{2}\log n)}$ ${\displaystyle O(n^{2})}$

Смотрите также

• Присоединение соседей
• Кластерный анализ
• Кластеризация с одинарной связью
• Кластеризация с полной связью
• Иерархическая кластеризация
• Модели эволюции ДНК
• Молекулярные часы

Ссылки

1. Сокал , Миченер (1958). «Статистический метод оценки систематических связей». Научный бюллетень Канзасского университета . 38 : 1409–1438.
2. Гарсия С., Пуигбо П. «DendroUPGMA: утилита для построения дендрограмм» (PDF) . п. 4.
3. Erdmann VA, Wolters J (1986). «Сборник опубликованных последовательностей рибосомальной РНК 5S, 5.8S и 4.5S». Nucleic Acids Research . 14 Suppl (Suppl): r1–59. doi :10.1093/nar/14.suppl.r1. PMC 341310. PMID  2422630 . 
4. Olsen GJ (1988). "Филогенетический анализ с использованием рибосомальной РНК". Рибосомы . Методы в энзимологии. Т. 164. С. 793–812. doi :10.1016/s0076-6879(88)64084-5. ISBN 978-0-12-182065-7. PMID  3241556.
5. Swofford DL, Olsen GJ, Waddell PJ, Hillis DM (1996). «Филогенетический вывод». В Hillis DM, Moritz C, Mable BK (ред.). Молекулярная систематика, 2-е издание . Sunderland, MA: Sinauer. стр. 407–514. ISBN 9780878932825.
6. Эверитт, Б.С.; Ландау, С.; Лиз, М. (2001). Кластерный анализ. 4-е издание . Лондон: Arnold. С. 62–64.
7. Лежандр П., Лежандр Л. (1998). Численная экология . Развитие экологического моделирования. Т. 20 (Второе английское издание). Амстердам: Elsevier.
8. Васкес-Домингес Э., Касамайор Э.О., Катала П., Лебарон П. (апрель 2005 г.). «Различные морские гетеротрофные нанофлагелляты по-разному влияют на состав обогащенных бактериальных сообществ». Микробная экология . 49 (3): 474–85. Бибкод : 2005MicEc..49..474V. дои : 10.1007/s00248-004-0035-5. JSTOR  25153200. PMID  16003474. S2CID  22300174.
9. Wheeler TJ, Kececioglu JD (июль 2007 г.). «Множественное выравнивание путем выравнивания выравниваний». Биоинформатика . 23 (13): i559–68. doi : 10.1093/bioinformatics/btm226 . PMID  17646343.
10. Муртаг Ф. (1984). «Сложности иерархических алгоритмов кластеризации: современное состояние». Computational Statistics Quarterly . 1 : 101–113.

Внешние ссылки

• Реализация алгоритма кластеризации UPGMA на языке Ruby (AI4R)
• Пример расчета UPGMA с использованием матрицы подобия
• Пример расчета UPGMA с использованием матрицы расстояний