روش گروه جفتی بی وزن با میانگین حسابی ( به انگلیسی: 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 می باشد؛ که همان متوسط فاصله دو خوشه می باشد.
این فرایند تا زمانی که تنها یک خوشه داشته باشیم ادامه می یابد.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفاگر یک ساعت مولکولی داشته باشیم و بخواهیم زمان تکامل را برای گونه های مختلف اندازه گیری کنیم، می توانیم به هر گره در درخت دودویی ریشه دار یک عدد نسبت دهیم که سن گونه را تعیین می کند. برای هر گره V سن آن را با ( age ( V نشان می دهیم. در این حالت تمام گره های ریشه سن ۰ دارند چون در حال حاضر موجود هستند. همچنین وزن یال ( v, u ) از طریق محاسبه ( age ( u ) - age ( v محاسبه می شود؛ بنابراین طول مسیر بین ریشه تا هر گره تفاوت سنی آن ها را نشان می دهد. چنین درختی که فاصله ریشه تا هر برگ آن برابر است فراشاخص ( به انگلیسی: ultrametric ) نامید می شود. این الگوریتم یک قدم بهتر از تبارزایش افزایشی است. اما با این حال همیشه جواب درست نمی دهد چراکه نزدیک ترین خوشه ها لزوماً در درخت، همسایه نیستند.
قصد ما این است که از یک درخت فراشاخص برای شرح ماتریس فاصله استفاده کنیم. روش جفت گروه بدون وزن با میانگین حسابی ( به انگلیسی: UPGMA ) یک روش اکتشاف برای خوشه بندی است که در علم بیوانفورماتیک از یک ساعت مولکولی فرضی برای ساخت درخت تکاملی فراشاخص استفاده می کند.
یک ماتریس به نام D با تعداد سطرها وستونهای برابر n در نظر می گیریم. برای ساخت درخت در هر گام دو خوشه نزدیک به یکدیگر باهم ترکیب شده و خوشه ایی در سطح بالاتر را می سازند. فاصله بین دو خوشه A و B برابر میانگین فاصله بین همه جفتهای x در A و y در B می باشد؛ که همان متوسط فاصله دو خوشه می باشد.
این فرایند تا زمانی که تنها یک خوشه داشته باشیم ادامه می یابد.
