ارائه یک الگوریتم ژنتیک برای بازسازی شبکه‌های فیلوژنتیک

درخت فیلوژنتیک ساختار داده‌ای است که برای نمایش ارتباط تکاملی بین گونه‌ها استفاده می‌شود ولی از آنجا که، داده‌های تکاملی واقعی اغلب شامل سیگنال‌هایی متفاوت و بعضاً ناسازگار هستند، بنابراین همیشه نمی‌توان ارتباط تکاملی بین آن‌ها را در یک درخت واحد نشان داد. از آنجا که بازسازی فیلوژنی از روی داده‌های بین گونه‌ها (مثلاً از روی MitochonrialDNA) اغلب به دلیل بزرگ بودن اندازه‌های نمونه‌ها و همچنین کم بودن فاصله‌ی ژنتیکی بین گونه‌های نزدیک، اغلب کاری چالش برانگیز است، لذا همه‌ی درخت‌های فیلوژنتیک ممکن را تشکیل داده و آنها را در قالب یک شبکه‌ی فیلوژنتیک با هم ترکیب می‌کنیم. در یک شبکه‌ی فیلوژنتیک می‌توان مسیرهای تکاملی بالقوه‌ی جایگزین را به شکل دورهایی در شبکه نشان داد. در این پژوهش از الگوریتم ژنتیک برای تولید شبکه‌های فیلوژنتیک از روی سه‌تایی‌ها استفاده کرده‌ایم. علاوه بر آن، برای کد کردن هر شبکه از نسخه‌ی اصلاح شده‌ای از روش کد گذاری pr fer number که برای کد کردن درخت‌ها کاربرد دارد استفاده کرده‌ایم. در طی اجرای عملگر تقاطع بر روی یک شبکه کد شده ممکن است یک گره برگی در درخت والد به یک گره غیر‌برگی در شبکه فرزند تبدیل شود. برای اطمینان از حضور تمامی گونه‌ها در برگ‌ها الگوی مربوط به مکان برگ‌ها را حفظ کرده‌ایم. برازندگی هر عضو در جمعیت در طی پیشرفت مراحل الگوریتم با توجه به دو معیار سطح و کمترین مجموع طول یال‌های شبکه مشخص می‌شود. هدف از این پژوهش یافتن شبکه‌ای با کمترین مجموع طول یال‌ها در یک سطح ثابت است. زمان اجرای الگوریتم از مرتبه (( O(n(2 می‌باشد.

کلیدواژه ها:

شبکه‌های فیلوژنتیک ، الگوریتم ژنتیک ، pr fer number ، کمترین مجموع وزنی