Введение
Агломеративный иерархический метод кластеризации. UPGMA (невесомый метод группы пар с арифметическим средним) – это простой агломеративный (снизу вверх) иерархический метод кластеризации. Существует также его взвешенный вариант, WPGMA, и оба метода обычно связывают с Сокалом и Миченером. Важно отметить, что термин "невесомый" указывает на то, что все расстояния вносят равный вклад в вычисление каждой средней величины и не относится к математическим операциям, используемым для этого вычисления. Таким образом, простое усреднение в WPGMA приводит к взвешенному результату, а пропорциональное усреднение в UPGMA – к невесовому результату (см. пример).
UPGMA (unweighted pair group method with arithmetic mean) is a simple agglomerative (bottom up) hierarchical clustering method. It also has a weighted variant, WPGMA, and they are generally attributed to Sokal and Michener. Note that the unweighted term indicates that all distances contribute equally to each average that is computed and does not refer to the math by which it is achieved. Thus the simple averaging in WPGMA produces a weighted result and the proportional averaging in UPGMA produces an unweighted result (see the working example).
Рабочий пример
Этот рабочий пример основан на генетической матрице расстояний JC69, вычисленной на основе выравнивания последовательностей 5S рибосомальной РНК пяти бактерий: Bacillus subtilis, Bacillus stearothermophilus, Lactobacillus viridescens, Acholeplasma modicum и Micrococcus luteus.
Дендрограмма UPGMA
Дендрограмма завершена. Она ультраметрична, поскольку все терминальные ветви (до) равноудалены от :
Следовательно, дендрограмма укоренена в , её самой глубокой точке.
Применение
В экологии это один из самых популярных методов классификации единиц выборки (таких как растительные участки) на основе попарного сходства по релевантным описательным признакам (например, видового состава). Например, он использовался для изучения трофических взаимодействий между морскими бактериями и протистами. В биоинформатике UPGMA применяется для построения фенетических деревьев (фенограмм). UPGMA изначально разрабатывался для использования в исследованиях электрофореза белков, но в настоящее время чаще всего используется для создания вспомогательных деревьев для более сложных алгоритмов. Этот алгоритм, например, применяется в процедурах выравнивания последовательностей, поскольку он предлагает определенный порядок, в котором последовательности будут выравниваться. Фактически, вспомогательное дерево стремится группировать наиболее похожие последовательности, независимо от скорости их эволюции или филогенетического родства, и это как раз является целью UPGMA. В филогенетике UPGMA предполагает постоянную скорость эволюции (гипотезу молекулярных часов) и то, что все последовательности были получены одновременно, и не считается надежным методом для установления родственных связей, если это предположение не было проверено и обосновано для используемого набора данных. Следует отметить, что даже при условии «строгих часов» последовательности, полученные в разное время, не должны приводить к ультраметрическому дереву.
In phylogenetics, UPGMA assumes a constant rate of evolution (molecular clock hypothesis) and that all sequences were sampled at the same time, and is not a well regarded method for inferring relationships unless this assumption has been tested and justified for the data set being used. Notice that even under a 'strict clock', sequences sampled at different times should not lead to an ultrametric tree.
Временная сложность
Тривиальная реализация алгоритма построения дерева UPGMA имеет временную сложность, а использование кучи для каждого кластера для хранения расстояний до других кластеров снижает время работы до. Фионн Муртаг представил алгоритм со сложностью по времени и памяти.