روش گروه جفتی بی‌وزن با میانگین حسابی کیست؟ توضیح بده.
روش گروه جفتی بی‌وزن با میانگین حسابی یکی از روش‌های ساده ای است که بر مبنای توده کردن داده‌ها یا خوشه بندی سلسله مراتبی مخصوصاً برای ساخت درخت فیلوژنتیک در بیوانفورماتیک به کار می‌رود (در حالی که نرخ تکامل را ثابت در نظر می‌گیرد(ساعت مولکولی)). این روش برای استنباط رابطه‌ها روش مناسبی نیست مگر اینکه فرض شود برای داده‌های مورد استفاده آزمایش شده و برای آنها توجیه شده‌است.روند کار آن به این شکل است که فاصلهٔ بین دو داده را از روی ماتریس فاصله بررسی می‌کند و به کمک آن درختی ریشه‌دار می‌سازد.این الگوریتم به Sokal و Michener نسبت داده می‌شود. Finon Murtagh و بعضی دیگر این الگوریتم را در زمان بهینه formula_1 به کار برده‌اند.کلیات.اگر یک ساعت مولکولی داشته باشیم و بخواهیم زمان تکامل را برای گونه‌های مختلف اندازه‌گیری کنیم، می‌توانیم به هر گره در درخت دودویی ریشه دار یک عدد نسبت دهیم که سن گونه را تعیین می‌کند. برای هر گره V سن آن را با (age(V نشان می‌دهیم. در این حالت تمام گره‌های ریشه سن ۰ دارند چون در حال حاضر موجود هستند. همچنین وزن یال (v,u) از طریق محاسبه (age(u)-age(v محاسبه می‌شود؛ بنابراین طول مسیر بین ریشه تا هر گره تفاوت سنی آن‌ها را نشان می‌دهد. چنین درختی که فاصله ریشه تا هر برگ آن برابر است فراشاخص نامید می‌شود.این الگوریتم یک قدم بهتر از تبارزایش افزایشی است. اما با این حال همیشه جواب درست نمی‌دهد چراکه نزدیک‌ترین خوشه‌ها لزوماً در درخت، همسایه نیستند.اهداف.قصد ما این است که از یک درخت فراشاخص برای شرح ماتریس فاصله استفاده کنیم. روش جفت گروه بدون وزن با میانگین حسابی یک روش اکتشاف برای خوشه بندی است که در علم بیوانفورماتیک از یک ساعت مولکولی فرضی برای ساخت درخت تکاملی فراشاخص استفاده می‌کند.الگوریتم.یک ماتریس به نام D با تعداد سطرها وستونهای برابر n در نظر می‌گیریم. برای ساخت درخت در هر گام دو خوشه نزدیک به یکدیگر باهم ترکیب شده و خوشه ایی در سطح بالاتر را می‌سازند. فاصله بین دو خوشه A و B برابر میانگین فاصله بین همه جفتهای x در A و y در B می‌باشد؛ که همان متوسط فاصله دو خوشه می‌باشد.این فرایند تا زمانی که تنها یک خوشه داشته باشیم ادامه می‌یابد.شبه کد مربوط به این الگوریتم در ادامه آمده‌است: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) و ۴ خوشهٔ مجزا داریم. سپس دو نزدیک‌ترین خوشه که مقدارشان ۲ است انتخاب می‌شوند (در مرحلهٔ دوم با رنگ قرمز مشخص شده‌است). این دو خوشه به هم وصل می‌شوند و یک خوشهٔ جدید ایجاد می‌کنند. سن خوشهٔ جدید برابر با نصف مقدار ماتریس فاصلهٔ انتخاب شده، یعنی ۱ خواهد بود(۱=۲÷۲).وزن یال‌ها هم از تفاضل سن خوشه جدید و خوشه‌های قبلی پیدا می‌شود.در مرحله بعد سطر و ستون مربوط به خوشه‌های قبلی حذف شده و سطر و ستون مربوط به خوشهٔ جدید جایگزین آن‌ها خواهد شد. سپس مانند مرحلهٔ قبل دو نزدیک‌ترین خوشه که اینجا مقدار ۳ دارند انتخاب شده و با هم ترکیب می‌شوند. در مرحلهٔ بعد هم پس از اصلاح ماتریس، دو خوشهٔ باقی مانده در هم ادغام می‌شوند و درخت نهایی ساخته می‌شود.پیچیدگی زمانی.الگوریتم بدیهی UPGMA از پیچیدگی زمانی formula_6 می‌باشد. اگر از هرم (علوم رایانه) برای نگهداری فاصله‌های هر خوشه از خوشهٔ دیگر استفاده کنیم، پیچیدگی زمانی به formula_7 کاهش خواهد یافت. روش‌های دیگری نظیر وجود دارند که دارای پیچیدگی زمانی formula_1 برای داده با تعداد ابعاد ثابت k می‌باشد. مقالهٔ هم روش دیگری برای پیچیدگی زمانی formula_1 ارائه داده‌است.کاربردها.در علم بوم‌شناسی الگوریتم UPGMA یکی از پرکاربردترین روش‌ها برای دسته‌بند عناصر مختلف (مثلا نقشه‌های مربوط به زیست‌بوم گیاهی) است که در آن از شباهت دوتایی متغیرها توصیفی آن عناصر استفاده می‌شود.در علم بیوانفورماتیک از این الگوریتم برای ساخت درخت تبارزایی استفاده می‌شود. البته در ابتدا این روش برای الکتروفورز پروتئین‌ها مورد استفاده قرار می‌گرفته‌است ولی در حال حاضر بیشتر برای ساخت درخت راهنما برای سایر روشهای پیچیده‌تر دوباره سازی درخت فیلوژنتیک به کار می‌رود. برای مثال در به بررسی تنوع ژنتیکی شته‌های غالب نهالستان‌های مرکبات استان‌های گیلان و مازندران و نقش آنها در انتقال ویروس تریستزا با استفاده از UPGMA پرداخته شده‌است.