موضوع مقاله: روش گروه جفتی بی‌وزن با میانگین حسابی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # روش گروه جفتی بی‌وزن با میانگین حسابی | مقدمه: روش گروه جفتی بی‌وزن با میانگین حسابی یکی از روش‌های ساده ای است که بر مبنای توده کردن داده‌ها یا خوشه بندی سلسله مراتبی مخصوصاً برای ساخت درخت فیلوژنتیک در بیوانفورماتیک به کار می‌رود (در حالی که نرخ تکامل را ثابت در نظر می‌گیرد(ساعت مولکولی . | ## بخش 1: روش گروه جفتی بی‌وزن با میانگین حسابی | این روش برای استنباط رابطه‌ها روش مناسبی نیست مگر اینکه فرض شود برای داده‌های مورد استفاده آزمایش شده و برای آنها توجیه شده‌است. روند کار آن به این شکل است که فاصلهٔ بین دو داده را از روی ماتریس فاصله بررسی می‌کند و به کمک آن درختی ریشه‌دار می‌سازد. کلیات اگر یک ساعت مولکولی داشته باشیم و بخواهیم زمان تکامل را برای گونه‌های مختلف اندازه‌گیری کنیم، می‌توانیم به هر گره در درخت دودویی ریشه دار یک عدد نسبت دهیم که سن گونه را تعیین می‌کند. همچنین وزن یال (v,u) از طریق محاسبه (age(u)-age(v محاسبه می‌شود؛ بنابراین طول مسیر بین ریشه تا هر گره تفاوت سنی آن‌ها را نشان می‌دهد. اما با این حال همیشه جواب درست نمی‌دهد چراکه نزدیک‌ترین خوشه‌ها لزوماً در درخت، همسایه نیستند. روش جفت گروه بدون وزن با میانگین حسابی یک روش اکتشاف برای خوشه بندی است که در علم بیوانفورماتیک از یک ساعت مولکولی فرضی برای ساخت درخت تکاملی فراشاخص استفاده می‌کند. برای ساخت درخت در هر گام دو خوشه نزدیک به یکدیگر باهم ترکیب شده و خوشه ایی در سطح بالاتر را می‌سازند. | ## بخش 2: روش گروه جفتی بی‌وزن با میانگین حسابی | فاصله بین دو خوشه A و B برابر میانگین فاصله بین همه جفتهای x در A و y در B می‌باشد؛ که همان متوسط فاصله دو خوشه می‌باشد. اندازهٔ خوشه A را نشان می‌دهد؛ بنابراین برای ماتریس فاصلهٔ غیر افزایشی، در هر مرحله دو نزدیک‌ترین خوشه انتخاب شده و در یک خوشه ادغام می‌شوند. سن گرهٔ جدید برابر با نصف مقدار ماتریس در ستون A و سطر B می‌باشد: این فرایند تا زمانی که تنها یک خوشه داشته باشیم ادامه می‌یابد. در هر مرحله، دو نزدیکترین خوشهٔ C1 و C2 شناسایی می‌شود، آنها را به یک گره جدید C متصل می‌کند و C به C1 و C2 را با یال جهت دار متصل می‌کند. سپس دو نزدیک‌ترین خوشه که مقدارشان ۲ است انتخاب می‌شوند (در مرحلهٔ دوم با رنگ قرمز مشخص شده‌است). سن خوشهٔ جدید برابر با نصف مقدار ماتریس فاصلهٔ انتخاب شده، یعنی ۱ خواهد بود(۱=۲÷۲). در مرحله بعد سطر و ستون مربوط به خوشه‌های قبلی حذف شده و سطر و ستون مربوط به خوشهٔ جدید جایگزین آن‌ها خواهد شد. | ## بخش 3: روش گروه جفتی بی‌وزن با میانگین حسابی | سپس مانند مرحلهٔ قبل دو نزدیک‌ترین خوشه که اینجا مقدار ۳ دارند انتخاب شده و با هم ترکیب می‌شوند. در مرحلهٔ بعد هم پس از اصلاح ماتریس، دو خوشهٔ باقی مانده در هم ادغام می‌شوند و درخت نهایی ساخته می‌شود. اگر از هرم (علوم رایانه) برای نگهداری فاصله‌های هر خوشه از خوشهٔ دیگر استفاده کنیم، پیچیدگی زمانی به کاهش خواهد یافت. روش‌های دیگری نظیر وجود دارند که دارای پیچیدگی زمانی برای داده با تعداد ابعاد ثابت k می‌باشد. کاربردها در علم بوم‌شناسی الگوریتم UPGMA یکی از پرکاربردترین روش‌ها برای دسته‌بند عناصر مختلف (مثلا نقشه‌های مربوط به زیست‌بوم گیاهی) است که در آن از شباهت دوتایی متغیرها توصیفی آن عناصر استفاده می‌شود. البته در ابتدا این روش برای الکتروفورز پروتئین‌ها مورد استفاده قرار می‌گرفته‌است ولی در حال حاضر بیشتر برای ساخت درخت راهنما برای سایر روشهای پیچیده‌تر دوباره سازی درخت فیلوژنتیک به کار می‌رود. | ## جمع‌بندی | برای مثال در به بررسی تنوع ژنتیکی شته‌های غالب نهالستان‌های مرکبات استان‌های گیلان و مازندران و نقش آنها در انتقال ویروس تریستزا با استفاده از UPGMA پرداخته شده‌است.