WPGMA - WPGMA

WPGMA (Wвосьмой пвоздуха граммгруппа Mэтод с Аrithmetic Mean) представляет собой простую агломерацию (снизу вверх) иерархическая кластеризация метод, обычно относящийся к Сокаль и Michener.^[1]

Метод WPGMA аналогичен его невзвешенный вариант, UPGMA метод.

Алгоритм

Алгоритм WPGMA строит корневое дерево (дендрограмма ), который отражает структуру, присутствующую в попарном матрица расстояний (или матрица сходства ). На каждом шаге ближайшие два кластера, скажем, ${\displaystyle i}$ и ${\displaystyle j}$, объединяются в кластер более высокого уровня ${\displaystyle i\cup j}$. Затем его расстояние до другого кластера ${\displaystyle k}$ это просто среднее арифметическое средних расстояний между членами ${\displaystyle k}$ и ${\displaystyle i}$ и ${\displaystyle k}$ и ${\displaystyle j}$ :

${\displaystyle d_{(i\cup j),k}={\frac {d_{i,k}+d_{j,k}}{2}}}$

Алгоритм WPGMA создает корневые дендрограммы и требует допущения о постоянной скорости: он дает ультраметрический дерево, в котором расстояния от корня до всех концов веток равны. Этот ультраметричность предположение называется молекулярные часы когда советы включают ДНК, РНК и белок данные.

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

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

Первый шаг

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

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

	а	б	c	d	е
а	0	17	21	31	23
б	17	0	30	34	21
c	21	30	0	28	39
d	31	34	28	0	43
е	23	21	39	43	0

В этом примере ${\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)+D_{1}(b,c))/2=(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}}$ :

	(а, б)	c	d	е
(а, б)	0	25.5	32.5	22
c	25.5	0	28	39
d	32.5	28	0	43
е	22	39	43	0

Здесь, ${\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}(((a,b),e),c)=(D_{2}((a,b),c)+D_{2}(e,c))/2=(25.5+39)/2=32.25}$

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

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

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

Третий шаг

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

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

	((а, б), д)	c	d
((а, б), д)	0	32.25	37.75
c	32.25	0	28
d	37.75	28	0

Здесь, ${\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 D_{4}((c,d),((a,b),e))=(D_{3}(c,((a,b),e))+D_{3}(d,((a,b),e)))/2=(32.25+37.75)/2=35}$

Заключительный этап

Финал ${\displaystyle D_{4}}$ матрица:

	((а, б), д)	(CD)
((а, б), д)	0	35
(CD)	35	0

Итак, мы присоединяемся к кластерам ${\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)=35/2=17.5}$

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

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

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

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

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

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

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

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

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

Сравнение дендрограмм, полученных разными методами кластеризации из одного и того же матрица расстояний.

Односвязная кластеризация.	Кластеризация с полной связью.	Средняя кластеризация связей: WPGMA.	Кластеризация средней связи: UPGMA.

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

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

Рекомендации

1. Сокаль, Michener (1958). «Статистический метод оценки систематических взаимосвязей». Бюллетень науки Канзасского университета. 38: 1409–1438.
2. Эрдманн В.А., Вольтерс Дж. (1986). «Коллекция опубликованных последовательностей рибосомных РНК 5S, 5.8S и 4.5S». Исследования нуклеиновых кислот. 14 Suppl (Suppl): r1–59. Дои:10.1093 / nar / 14.suppl.r1. ЧВК  341310. PMID  2422630.
3. Olsen GJ (1988). «Филогенетический анализ с использованием рибосомальной РНК». Методы в энзимологии. 164: 793–812. Дои:10.1016 / с0076-6879 (88) 64084-5. PMID  3241556.
4. Everitt, B.S .; Ландау, С .; Лиз, М. (2001). Кластерный анализ. 4-е издание. Лондон: Арнольд. п. 62–64.