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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

روش جفت گروه بدون وزن با میانگین حسابی (به انگلیسی: Unweighted Pair Group Method with Arithmetic Mean) یکی از روشهای ساده ایی است که بر مبنای توده کردن داده ها و یا خوشه بندی سلسله مراتبی برای ساخت درخت فیلوژنتیک در بیوانفورماتیک به کار می رود.این روش نرخ تکامل را ثابت در نظر می گیرد(ساعت مولکولی) و این روش برای استنباط رابطه ها روش مناسبی نیست مگر اینکه فرض شود برای داده های مورد استفاده آزمایش شده و برای آنها توجیه شده است. این روش در ابتدا برای الکتروفورز پروتئین ها مورد استفاده قرار می گرفته است ولی در حال حاضر بیشتر برای ساخت درخت راهنما برای سایر روشهای پیچیده تر دوباره سازی درخت فیلوژنتیک به کار می رود. الگوریتم فاصله بین دو داده را از روی ماتریس فاصله بررسی می کند و درختی که می سازد درخت ریشه دار است. در هر گام دو خوشه نزدیک به یکدیگر باهم ترکیب شده و خوشه ایی در سطح بالاتر را می سازند. فاصله بین دو خوشه 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)

این الگوریتم به Sokal و Michener نسبت داده می شود. Finon Murtagh این الگوریتم را در زمان بهینه O(n^2) به کار برده است.

منابع[ویرایش]

  • مشارکت‌کنندگان ویکی‌پدیا، «UPGMA»، ویکی‌پدیای انگلیسی، دانشنامهٔ آزاد (بازیابی در ۲۲ ژوئن ۲۰۱۲).