UPGMA (unweighted pair group method with arithmetic mean; českymetoda neváženého párování s aritmetickým průměrem) je jednoduchá aglomerativníhierarchická shluková metoda (jde o tzv. bottom-up metodu, kdy se nejprve shlukují páry sobě nejpodobnější, které se následně shlukují až do konečné sítě). Metodu představili Sokal a Michener.^[1]

Termínnevážená metoda nesouvisí s matematickým výpočtem, ale odkazuje na skutečnost, že všechny distance se podílejí stejnou měrou na výpočtu každého průměru. Metoda UPGMA má i alternativuváženého párování, která se nazýváWPGMA. WPGMA generuje výsledky na základně jednoduchého průměru vzdáleností (nebolidistancí), zatímco u nevážené metody UPGMA se používá k výpočtu proporcionální průměr (vizpracovní příklad).^[2]

Algoritmus UPGMA vytváří zakořeněný strom (tzv.dendrogram), který odráží strukturumatice podobností (nebomatice odlišností). V každém kroku jsou dva nejpodobnější klastry sloučeny do klastru vyšší úrovně. Vzdálenost mezi každými dvěma klastry${\displaystyle \mathcal{A}}$ a${\displaystyle \mathcal{B}}$ o velikosti (nebolimohutnosti)${\displaystyle |\mathcal{A}|}$ a${\displaystyle |\mathcal{B}|}$ je vypočítána jako průměr všech vzdáleností${\displaystyle d(x,y)}$ mezi páry prvků${\displaystyle x}$ v${\displaystyle \mathcal{A}}$ a${\displaystyle y}$ v${\displaystyle \mathcal{B}}$, tzn. jako střední vzdálenost mezi prvky každého klastru:

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

Jinými slovy, v každém kroku se aktualizuje vzdálenost mezi nově spojenými klastry${\displaystyle \mathcal{A}\cup \mathcal{B}}$ a novým clustrem${\displaystyle X}$. Aktualizovaná vzdálenost je dána proporcionálním průměrem vzdáleností${\displaystyle d_{\mathcal{A},X}}$ a${\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}|}}$

Algoritmus UPGMA vytváří zakořeněné dendrogramy, při jejichž tvorbě předpokládá konstantní podíly - to znamená, že předpokládá tzv.ultrametrický strom, ve kterém jsou vzdálenosti od kořene ke konci každé větve stejné. Pokud jsou základem pro tvorbu stromu molekulární data (tj.DNA,RNA neboproteiny) odebraná ve stejný čas,ultrametricita se stane ekvivalentemmolekulárních hodin.

Tento pracovní příklad je založen na matici genetických distancí JC69, která je odvozená z alignmentu sekvencí5S ribozomální RNA pěti bakterií:Bacillus subtilis (${\displaystyle a}$),Bacillus stearothermophilus (${\displaystyle b}$),Lactobacillus viridescens (${\displaystyle c}$),Acholeplasma modicum (${\displaystyle d}$) aMicrococcus luteus (${\displaystyle e}$).^[3][4]

• První shlukování (klastrování)

Předpokládejme, že máme pět prvků${\displaystyle (a,b,c,d,e)}$ uspořádaných v následující matici párových vzdáleností${\displaystyle D_1}$:

Protože je v této matici je nejmenší hodnotou${\displaystyle D_1(a,b)=17}$, v prvním kroku spojíme prvky${\displaystyle a}$ a${\displaystyle b}$.

• Odhad délky první větve

Písmenem${\displaystyle u}$ označme uzel, ve kterém se nyní spojují prvky${\displaystyle a}$ a${\displaystyle b}$. Díky rovnici${\displaystyle \delta (a,u)=\delta (b,u)=D_1(a,b)/2}$ je zajištěno, že prvky${\displaystyle a}$ a${\displaystyle b}$ jsou stejně vzdálené od${\displaystyle u}$. To odpovídá hypotézeultrametricity. Větve obou prvků${\displaystyle a}$ a${\displaystyle b}$ vedoucí k uzlu${\displaystyle u}$ tedy mají délku${\displaystyle \delta (a,u)=\delta (b,u)=17/2=8.5}$ (vizvýsledný dendrogram).

• První aktualizace matice vzdáleností

Poté přistoupíme k aktualizaci počáteční matice${\displaystyle D_1}$ na novou matici${\displaystyle D_2}$ (viz níže), která bude zmenšená o jeden řádek a jeden sloupec kvůli seskupování${\displaystyle a}$ s${\displaystyle b}$ v předchozím kroku. Nové hodnoty vzdáleností odpovídajíprůměru vzdáleností mezi každým prvkem prvního klastru${\displaystyle (a,b)}$ a každým ze zbývajících prvků:

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

Nově vypočtené hodnoty vzdáleností v matici${\displaystyle D_2}$ jsou vyznačeny tučně. Hodnoty psané kurzívou v matici${\displaystyle D_2}$ nebyly změněny oproti původní matici${\displaystyle D_1}$, protože jde o vzdálenosti mezi prvky, které nebyly zahrnuty do prvního klastru.

• Druhé shlukování

Nyní zopakujeme tři předchozí kroky, počínaje tvorbou nové matice vzdálenosti${\displaystyle D_2}$

V této matici je nejmenší hodnotou${\displaystyle D_2((a,b),e)=22}$, proto ke klastru${\displaystyle (a,b)}$ připojíme prvek${\displaystyle e}$.

• Odhad délky druhé větve

Označme uzel spojující klastr${\displaystyle (a,b)}$ a prvek${\displaystyle e}$ písmenem${\displaystyle v}$. Kvůli ultrametricitě musí mít větve spojující klastr (${\displaystyle a}$,${\displaystyle b}$) a${\displaystyle e}$ v uzlu${\displaystyle v}$ stejnou délku:${\displaystyle \delta (a,v)=\delta (b,v)=\delta (e,v)=22/2=11}$

Délku nové větve vypočteme následovně:${\displaystyle \delta (u,v)=\delta (e,v)-\delta (a,u)=\delta (e,v)-\delta (b,u)=11-8.5=2.5}$ (vizvýsledný dendrogram)

• Druhá aktualizace matice vzdáleností

Poté přistoupíme k aktualizaci matice${\displaystyle D_2}$ na novou distanční matici${\displaystyle D_3}$ (viz níže), zmenšenou o jeden řádek a jeden sloupec kvůli vzniku nového klastru${\displaystyle (a,b)}$ a${\displaystyle e}$. Tučně zvýrazněné hodnoty v${\displaystyle D_3}$ odpovídají novým vzdálenostem, vypočteným na základněproporcionálního průměru:

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

Výpočet nové vzdálenosti pomocí proporcionálního průměru umožňuje vzít v potaz větší velikost klastru${\displaystyle (a,b}$ - dva prvky) s ohledem na${\displaystyle e}$ (jeden prvek). Podobně vypočteme zbývající vzdálenost:

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

Proporcionální průměr tedy dává stejnou váhu všem počátečním vzdálenostem matice${\displaystyle D_1}$. To je důvod, proč je metodanevážená - ne s ohledem na matematický postup, ale s ohledem na počáteční vzdálenosti.

• Třetí shlukování

Znovu zopakujeme tři předchozí kroky, přičemž nejprve vytvoříme novou matici vzdáleností${\displaystyle D_3}$.

Nejmenší hodnotou této matice je${\displaystyle D_3(c,d)=28}$, takže spojíme prvky${\displaystyle c}$ a${\displaystyle d}$ .

• Odhad délky třetí větve

Písmenem${\displaystyle w}$ označme uzel, který spojuje prvky${\displaystyle c}$ a${\displaystyle d}$. Větve spojující${\displaystyle c}$ a${\displaystyle d}$ v uzlu${\displaystyle w}$ pak mají délku${\displaystyle \delta (c,w)=\delta (d,w)=28/2=14}$ (vizvýsledný dendrogram)

• Třetí aktualizace matice vzdáleností

Nyní je třeba aktualizovat jen jednu hodnotu, přičemž je třeba mít na paměti, že každý z prvků${\displaystyle c}$ a${\displaystyle d}$ přispívají kvýpočtu průměru hodnotou${\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}$

Finální matice${\displaystyle D_4}$ je následující:

Spojili jsme tudíž oba klastry${\displaystyle ((a,b),e)}$ a${\displaystyle (c,d)}$.

Písmenem${\displaystyle r}$ označme (kořenový) uzel, ve kterém spojíme klastry${\displaystyle ((a,b),e)}$ a${\displaystyle (c,d)}$. Větve klastrů${\displaystyle ((a,b),e)}$ a${\displaystyle (c,d)}$ vedoucí k uzlu${\displaystyle r}$ pak mají délky:

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

Vypočteme délky dvou zbývajících větví:

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

Dendrogram je nyní dokončen.^[5] Je ultrametrický, protože všechny konce větví (od${\displaystyle a}$ po${\displaystyle e}$) jsou stejně vzdálené od uzlu${\displaystyle r}$:

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

Dendrogram je proto zakořeněn nejhlubším uzlem${\displaystyle r}$, který je nazývánkořen.

Alternativní klastrovací schémata zahrnujísingle linkage clustering (metoda nejbližšího souseda, jednospojná metoda),complete linkage clustering (metoda nejvzdálenějšího souseda, všespojná metoda) aWPGMA. Jednotlivé algoritmy se mezi sebou liší použitím jiných postupů při výpočtu vzdáleností mezi klastry v rámci tvorby nové matice. Nevýhodou nejjednodušší metody single linkage clustering je tzv.chaining phenomenon, při kterém dochází ke shlukování klastrů na základě jediného společného charakteru přestože jsou si jednotlivé prvky v klastru obecně nepodobné. Algoritmus Complete linkage clustering dokáže tuto nevýhodu řešit a tvoří klastry o přibližně stejných diametrech.^[6]

Porovnání dendrogramů získaných různými shlukovacími metodami na základě stejné distanční matice .

Single-linkage clustering	Complete-linkage clustering	Average linkage clustering: WPGMA	Average linkage clustering: UPGMA

• Jde o jednu z nejpopulárnějších metod vekologii. Požívá se pro klasifikaci vzorků (jako jsou např. vegetační snímky) na základě párových podobností jejich vlastností (jako je např. druhové složení).^[7] Mimo vegetační data může sloužit také například k pochopení trofické interakce mezi mořskými bakteriemi a protisty.^[7]
• Vbioinformatice se UPGMA používá k tvorběfenetických stromů (fenogramů). Metoda UPGMA byla původně navržena pro studie založené naproteinové elektroforéze, ale v současné době se nejčastěji používá k výpočtu vodících stromů pro sofistikovanější algoritmy. Tento algoritmus se používá například při výpočtualignmentu sekvencí, kdy se na jeho základě tvoří pořadí, ve kterém budou sekvence alignovány. Vodící strom založený na UPGMA seskupuje nejpodobnějších sekvencí bez ohledu na jejich evoluční vývoj nebo fylogenetickou afinitu.^[8]
• Při použití metody UPGMA vefylogenetice se předpokládá konstantní rychlost evoluce (tzv.hypotéza molekulárních hodin) a že všechny vzorky byly odebrány současně. Nicméně se nepovažuje za vhodnou metodu pro odvozování fylogenetických vztahů. Metodu lze použít pouze pokud byly zmíněné předpoklady testovány a dobře zdůvodněny. Je důležité si uvědomit, že strom vytvořený na základě vzorků odebraných v různých časech by neměl vést k ultrametrickému stromu, dokonce i za podmínky „strict clock“.

Základní použití UPGMA algoritmu ke konstrukci stromu má časovou komplexitu${\displaystyle O(n^3)}$. Pokud použijeme pro každý klastrhaldu, abychom jednotlivé klastry udželi ve vzdálenosti od ostatních, redukujeme čas na${\displaystyle O(n^2\log n)}$. Fionn Murtagh představil nějaké další přístupy pro speciální případy: časový algoritmus${\displaystyle O(k{3}^k{n}^2)}$ podle Day a Edelsbrunner^[9] pro k-dimensionální data, kde je optimální${\displaystyle O(n^2)}$ pro konstantní k, a další algoritmus${\displaystyle O(n^2)}$ pro omezené vstupy, pokud „shlukovací strategie vyhovuje reducibilitě“.^[10]

V tomto článku byl použitpřeklad textu z článkuUPGMA na anglické Wikipedii.

• Shluková analýza
• Hierarchické seskupování
• Molekulární hodiny

• Implementace klastrovacího algoritmu UPGMA v Ruby (AI4R)
• Příklad výpočtu UPGMA pomocí matice podobnosti
• Příklad výpočtu UPGMA pomocí distanční matice

• Bioinformatika
• Shluková analýza

• Údržba:Články s dočasně použitou šablonou
• Údržba:Články obsahující odkazy na nedostupné zdroje
• Monitoring:Články přeložené z enwiki
• Monitoring:Autoritní kontrola s 0 identifikátory