УПГМА

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

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}$

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

Пусть обозначает узел, к которому и сейчас подключены. Из-за ограничения ультраметричности ветви, соединяющие или to и to , равны и имеют следующую длину: ${\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. Эрдманн В.А., Уолтерс Дж (1986). «Коллекция опубликованных последовательностей рибосомальных РНК 5S, 5,8S и 4,5S». Исследования нуклеиновых кислот . 14 Дополнение (Suppl): r1–59. дои : 10.1093/nar/14.suppl.r1. ПМК 341310 . ПМИД  2422630. 
4. Олсен Г.Дж. (1988). «Филогенетический анализ с использованием рибосомальной РНК». Рибосомы . Методы энзимологии. Том. 164. стр. 793–812. дои : 10.1016/s0076-6879(88)64084-5. ISBN 978-0-12-182065-7. ПМИД  3241556.
5. Суоффорд Д.Л., Олсен Г.Дж., Уодделл П.Дж., Хиллис Д.М. (1996). «Филогенетический вывод». В Hillis DM, Moritz C, Mable BK (ред.). Молекулярная систематика, 2-е издание . Сандерленд, Массачусетс: Синауэр. стр. 407–514. ISBN 9780878932825.
6. Эверитт, Б.С.; Ландау, С.; Лиз, М. (2001). Кластерный анализ. 4-е издание . Лондон: Арнольд. стр. 62–64.
7. Лежандр П., Лежандр Л. (1998). Численная экология . Развитие экологического моделирования. Том. 20 (Второе английское изд.). Амстердам: Эльзевир.
8. Васкес-Домингес Э., Касамайор Э.О., Катала П., Лебарон П. (апрель 2005 г.). «Различные морские гетеротрофные нанофлагелляты по-разному влияют на состав обогащенных бактериальных сообществ». Микробная экология . 49 (3): 474–85. Бибкод : 2005MicEc..49..474V. дои : 10.1007/s00248-004-0035-5. JSTOR  25153200. PMID  16003474. S2CID  22300174.
9. Уиллер Т.Дж., Кечечиоглу Дж.Д. (июль 2007 г.). «Множественное выравнивание путем выравнивания выравниваний». Биоинформатика . 23 (13): i559–68. doi : 10.1093/биоинформатика/btm226 . ПМИД  17646343.
10. Мурта Ф (1984). «Сложности алгоритмов иерархической кластеризации: современное состояние». Вычислительная статистика Ежеквартальный . 1 : 101–113.

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

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