روش جفت گروه بدون وزن با میانگین حسابی

روش جفت گروه بدون وزن با میانگین حسابی (به انگلیسی: Unweighted Pair Group Method with Arithmetic Mean) یکی از روشهای ساده ای است که بر مبنای توده کردن داده‌ها یا خوشه بندی سلسله مراتبی مخصوصاً برای ساخت درخت فیلوژنتیک در بیوانفورماتیک به کار می‌رود (در حالی که نرخ تکامل را ثابت در نظر می‌گیرد(ساعت مولکولی)). این روش برای استنباط رابطه‌ها روش مناسبی نیست مگر اینکه فرض شود برای داده‌های مورد استفاده آزمایش شده و برای آنها توجیه شده‌است. روند کار آن به این شکل است که فاصلهٔ بین دو داده را از روی ماتریس فاصله بررسی می‌کند و به کمک آن درختی ریشه دار می‌سازد. این الگوریتم به Sokal و Michener نسبت داده می‌شود. Finon Murtagh و بعضی دیگر این الگوریتم را در زمان بهینه $O(n^{2})$

به کار برده‌اند.

کلیات

اگر یک ساعت مولکولی داشته باشیم و بخواهیم زمان تکامل را برای گونه‌های مختلف اندازه‌گیری کنیم، می‌توانیم به هر گره در درخت دودویی ریشه دار یک عدد نسبت دهیم که سن گونه را تعیین می‌کند. برای هر گره V سن آن را با (age(V نشان می‌دهیم. در این حالت تمام گره‌های ریشه سن ۰ دارند چون در حال حاضر موجود هستند. همچنین وزن یال (v,u) از طریق محاسبه (age(u)-age(v محاسبه می‌شود؛ بنابراین طول مسیر بین ریشه تا هر گره تفاوت سنی آن‌ها را نشان می‌دهد. چنین درختی که فاصله ریشه تا هر برگ آن برابر است فراشاخص(به انگلیسی: ultrametric) نامید می‌شود. این الگوریتم یک قدم بهتر از تبارزایش افزایشی است. اما با این حال همیشه جواب درست نمی‌دهد چراکه نزدیک‌ترین خوشه‌ها لزوماً در درخت، همسایه نیستند.

اهداف

قصد ما این است که از یک درخت فراشاخص برای شرح ماتریس فاصله استفاده کنیم. روش جفت گروه بدون وزن با میانگین حسابی (به انگلیسی: UPGMA) یک روش اکتشاف برای خوشه بندی است که در علم بیوانفورماتیک از یک ساعت مولکولی فرضی برای ساخت درخت تکاملی فراشاخص استفاده می‌کند.

الگوریتم

یک ماتریس به نام D با تعداد سطرها وستونهای برابر n در نظر می‌گیریم. برای ساخت درخت در هر گام دو خوشه نزدیک به یکدیگر باهم ترکیب شده و خوشه ایی در سطح بالاتر را می‌سازند. فاصله بین دو خوشه A و B برابر میانگین فاصله بین همه جفتهای x در A و y در B می‌باشد؛ که همان متوسط فاصله دو خوشه می‌باشد.

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

|{\mathcal {A}}|

اندازهٔ خوشه A را نشان می‌دهد؛ بنابراین برای ماتریس فاصلهٔ غیر افزایشی، در هر مرحله دو نزدیک‌ترین خوشه انتخاب شده و در یک خوشه ادغام می‌شوند. سن گرهٔ جدید برابر با نصف مقدار ماتریس در ستون A و سطر B می‌باشد:

DC1,C1 \over 2

این فرایند تا زمانی که تنها یک خوشه داشته باشیم ادامه می‌یابد.

شبه کد مربوط به این الگوریتم در ادامه آمده‌است:

UPGMA(D, n)
      Clusters ← n single-element clusters labeled 1, ... , n
      construct a graph T with n isolated nodes labeled by single elements 1, ... , n
    for every node v in T
        Age(v) ← 0
    while there is more than one cluster
        find the two closest clusters Ci and Cj
        merge Ci and Cj into a new cluster Cnew with |Ci| + |Cj| elements
        add a new node labeled by cluster Cnew to T
        connect node Cnew to Ci and Cj by directed edges
        Age(Cnew) ← DCi, Cj / 2
        remove the rows and columns of D corresponding to Ci and Cj
        remove Ci and Cj from Clusters
        add a row/column to D for Cnew by computing D(Cnew, C) for each C in Clusters
        add Cnew to Clusters
    root ← the node in T corresponding to the remaining cluster
    for each edge (v, w) in T
        length of (v, w) ← Age(v) - Age(w)
    return T

مثال

عکس زیر بازسازی درخت با UPGMA برای ماتریس فاصلهٔ افزایشی را نشان می‌دهد. همان‌طور که ذکر شد، الگوریتم UPGMA با تشکیل یک خوشه برای هر برگ شروع می‌شود. در هر مرحله، دو نزدیکترین خوشهٔ C1 و C2 شناسایی می‌شود، آنها را به یک گره جدید C متصل می‌کند و C به C1 و C2 را با یال جهت دار متصل می‌کند. سن C برابر با نصف مقدار ماتریس فاصله در سطر و ستون مربوط به C1 و C2 است. سپس این روند را تکرار می‌کنیم تا زمانی که تنها یک خوشه باقی بماند. در مثال زیر در مرحلهٔ اول، یک ماتریس فاصلهٔ افزایشی (به انگلیسی: additive) و ۴ خوشهٔ مجزا داریم. سپس دو نزدیک‌ترین خوشه که مقدارشان ۲ است انتخاب می‌شوند (در مرحلهٔ دوم با رنگ قرمز مشخص شده‌است). این دو خوشه به هم وصل می‌شوند و یک خوشهٔ جدید ایجاد می‌کنند. سن خوشهٔ جدید برابر با نصف مقدار ماتریس فاصلهٔ انتخاب شده، یعنی ۱ خواهد بود(۱=۲÷۲). وزن یال‌ها هم از تفاضل سن خوشه جدید و خوشه‌های قبلی پیدا می‌شود.

age(C)-age(C1)=1-0=1

در مرحله بعد سطر و ستون مربوط به خوشه‌های قبلی حذف شده و سطر و ستون مربوط به خوشهٔ جدید جایگزین آن‌ها خواهد شد. سپس مانند مرحلهٔ قبل دو نزدیک‌ترین خوشه که اینجا مقدار ۳ دارند انتخاب شده و با هم ترکیب می‌شوند. در مرحلهٔ بعد هم پس از اصلاح ماتریس، دو خوشهٔ باقی مانده در هم ادغام می‌شوند و درخت نهایی ساخته می‌شود.

مثال الگوریتم UPGMA

پیچیدگی زمانی

الگوریتم بدیهی UPGMA از پیچیدگی زمانی $O(n^{3})$

می‌باشد. اگر از هرم (علوم رایانه) برای نگهداری فاصله‌های هر خوشه از خوشهٔ دیگر استفاده کنیم، پیچیدگی زمانی به

O(n^{2}\log n)

کاهش خواهد یافت. روش‌های دیگری نظیر وجود دارند که دارای پیچیدگی زمانی

O(n^{2})

برای داده با تعداد ابعاد ثابت k می‌باشد. مقالهٔ هم روش دیگری برای پیچیدگی زمانی

O(n^{2})

ارائه داده‌است.

کاربردها

در علم بوم‌شناسی الگوریتم UPGMA یکی از پرکاربردترین روش‌ها برای دسته‌بند عناصر مختلف (مثلا نقشه‌های مربوط به زیست‌بوم گیاهی) است که در آن از شباهت دوتایی متغیرها توصیفی آن عناصر استفاده می‌شود. در علم بیوانفورماتیک از این الگوریتم برای ساخت درخت تبارزایی استفاده می‌شود. البته در ابتدا این روش برای الکتروفورز پروتئین‌ها مورد استفاده قرار می‌گرفته‌است ولی در حال حاضر بیشتر برای ساخت درخت راهنما برای سایر روشهای پیچیده‌تر دوباره سازی درخت فیلوژنتیک به کار می‌رود. برای مثال در به بررسی تنوع ژنتیکی شته‌های غالب نهالستان‌های مرکبات استان‌های گیلان و مازندران و نقش آنها در انتقال ویروس تریستزا با استفاده از UPGMA پرداخته شده‌است.

جستارهای وابسته

منابع

↑ Pavel Pevzner, Neil Jones (2004). An Introduction to Bioinformatics Algorithms. The MIT Press.
↑ Day, William H. E.; Edelsbrunner, Herbert (1984-12-01). "Efficient algorithms for agglomerative hierarchical clustering methods". Journal of Classification. 1 (1): 7–24. doi:10.1007/BF01890115. ISSN 0176-4268.
↑ Murtagh F (1984). "Complexities of Hierarchic Clustering Algorithms: the state of the art". Computational Statistics Quarterly. 1: 101–113.
↑ Gholamian, Esmaeil (2018). Genetic diversity of dominant aphids of citrus nurseries in Guilan and Mazandaran provinces and their role in citrus tristeza virus transmission (PhD). University of Mohaghegh Ardabili.

[1] Pavel Pevzner, Neil Jones (2004). An Introduction to Bioinformatics Algorithms. The MIT Press.

[2] Day, William H. E.; Edelsbrunner, Herbert (1984-12-01). "Efficient algorithms for agglomerative hierarchical clustering methods". Journal of Classification. 1 (1): 7–24. doi:10.1007/BF01890115. ISSN 0176-4268.

[3] Murtagh F (1984). "Complexities of Hierarchic Clustering Algorithms: the state of the art". Computational Statistics Quarterly. 1: 101–113.

[4] Gholamian, Esmaeil (2018). Genetic diversity of dominant aphids of citrus nurseries in Guilan and Mazandaran provinces and their role in citrus tristeza virus transmission (PhD). University of Mohaghegh Ardabili.