ارایه یک روش جدید انطباق چندگانه توالی های دی ان ای و پروتئین بر اساس الگوریتم های تکاملی

مطالعه حیات و آشکارسازی وظایف ژن‌ها یک مساله مهم در محاسبات زیستی است. در انطباق توالی‌های زیستی، برای شناسایی ژن‌ها، اندازه‌گیری شباهت بین توالی‌ها انجام می‌شود. وقتی با مساله اندازه ژنوم در انطباق‌های چندگانه مواجه می‌شویم، با مشکل کمبود حافظه و افزایش زمان روبه‌رو هستیم. بنابراین، روشی که بتواند سریع و بدون کاهش دقت، انطباق ژنوم‌ها را داشته باشد، تاثیر به‌سزایی در تحلیل توالی‌ها خصوصا توالی‌های بلند را همراه دارد.

ابتدا روشی را برای تقسیم هر توالی به زیر توالی‌های کوتاه معرفی می‌کنیم. سپس از الگوریتم‌های تکاملی برای انطباق زیر‌توالی‌ها استفاده می‌کنیم.

روش پیشنهادی در هفت مجموعه داده با تعداد نکلویتیدهای مختلف به‌ازای هر توالی دی‌ان‌ای و افزایش تدریجی از 18000 تا 14 میلیون نکلیوتید، ارزیابی شده و با پنج روش مشهور انطباق چندگانه مقایسه شده است. بالاترین میزان دقت برای باکتری variola با میزان 93/0 و بالاترین سرعت انطباق 6/0 بر حسب دقیقه برای این باکتری است.

اکثر روش‌های انطباق چندگانه در توالی‌های کوتاه یا تعداد کم، دقت مناسبی دارند اما برای دنباله‌های طولانی‌تر به قدرت محاسباتی بالایی نیاز دارند. الگوریتم پیشنهادی با انطباق توالی‌های بلند، در زمانی قابل قبول و حفظ دقت و همچنین استفاده بهینه از حافظه، بر این نقص غلبه می‌کند.