مدل‌سازی پیشرفته ریاضی (Jun 2021)
ارائه الگوریتمی نوین برای حل مساله ساخت درخت فیلوژنتیک ریشه‌دار بر اساس سه‌تایی‌های ریشه‌دار ورودی
Abstract
فیلوژنتیک شاخه‌ای از دانش بیوانفورماتیک است که تاریخچه روابط تکاملی بین گونه‌های موجودات زنده را بررسی می‌کند و مدل‌هایی را ارائه می‌دهد و گونه‌ها را دسته‌بندی نیز می‌کند. فیلوژنتیک از شبکه‌ها برای بیان روابط تکاملی در یک مدل جامع استفاده می‌کند. ساده‌ترین مدل شبکه ای، یک درخت است که درخت فیلوژنتیک نامیده می‌شود. درختهای فیلوژنتیک به دو زیرمجموعه ریشه‌دار و بدون ریشه تقسیم می‌شوند. در این پژوهش علاقه ما، درختهای فیلوژنتیک ریشه‌دار است. ورودی‌های مختلفی برای ساخت درختهای فیلوژنتیک ریشه‌دار موجود است. سه‌تایی‌های ریشه‌دار یکی از انواع مهم ورودی‌ها در تحلیل روابط بین گونه‌ها و ساخت درخت فیلوژنتیک ریشه‌دارند که در این پژوهش از آن استفاده می‌کنیم. سه‌تایی ریشه‌دار یک درخت دودویی ریشه‌دار با سه برگ است. سه‌تایی ریشه‌دار ساده‌ترین مدل درختی ریشه‌دار است که حاوی اطلاعات است. مساله ساخت درخت فیلوژنتیک ریشه‌داری که دربرگیرنده بیش‌ترین سه‌تایی ورودی باشد، یک مساله بهینه سازی است و به مساله MRTC مشهور است. چالش مهم در فیلوژنتیک، -NP سخت بودن مساله MRTC است. از این‌رو در این مقاله، یک الگوریتم نوین برای مساله MRTC با هدف افزایش میزان سازگاری سه‌تایی‌های ریشه‌دار ورودی با درخت نهایی، معرفی می‌شود. با هدف بیان کارایی الگوریتم نوین، روش معرفی‌شده را با روش TRH و بر روی داده‌های واقعی مقایسه می‌کنیم. الگوریتم TRH یکی از بهترین روش‌ها برای حل مساله MRTC و بر روی سه‌تایی‌های ریشه‌داری است که از روی داده‌های واقعی به‌دست آمده‌اند. نتایج آزمایش‌ها نشان می‌دهد که با در نظر گرفتن زمان اجرا و سازگاری سه‌تایی‌ها با درخت نهایی، الگوریتم ما نتایج TRH را بهبود می‌بخشد.
Keywords
