Кіріспе
Агломеративтік иерархиялық кластерлеу әдісі. 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).
Жұмыс үлгісі
Бұл жұмыс үлгісі Bacillus subtilis, Bacillus stearothermophilus, Lactobacillus viridescens, Acholeplasma modicum және Micrococcus luteus бактерияларының 5S рибосомалық РНК тізбегінің салыстырылуынан есептелген JC69 генетикалық қашықтық матрицасына негізделген.
UPGMA дендрограммасы
Дендрограмма енді толық. Ол ультраметрлік, себебі барлық ұштары (to) -дан бірдей қашықтықта орналасқан:
Дендрограмма, демек, оның ең терең түйінімен тамырланған.
Қолданылуы
Экологияда бұл іріктеу бірліктерін (мысалы, өсімдіктер алқаптарын) тиісті сипаттамалық айнымалылар (мысалы, түрлер құрамы) бойынша жұптық ұқсастықтары негізінде жіктеудің ең танымал әдістерінің бірі. Мысалы, теңіз бактериялары мен протоидтар арасындағы трофикалық өзара әрекеттесуді түсіну үшін қолданылған. Биоинформатикада 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 ағашын құру алгоритмінің қарапайым іске асырылуы уақыт күрделілігіне ие, ал әр кластер үшін басқа кластерлерге дейінгі қашықтықтарын сақтау үшін қалыптық үйіндіні қолдану оның уақытын қысқартады. Фионн Муртаг уақыт және кеңістік бойынша тиімді алгоритм ұсынды.