فاطمه زارع - استاد یار دانشکده ریاضی و علوم کامپیوتر دانشگاه صنعتی امیرکبیر
فرهاد ملکی - دانشجوی دکتری دانشکده ریاضی و علوم کامپیوتر دانشگاه صنعتی امیرکبیرتهران ایران
مهسا ترکمان
شیوا شکیباپور

دادههای هاپلوتایپ بهواسطهی نقشی که در مطالعات ژنتیکی ایفامیکنند وهمچنین بهواسطهی توسعه سریع روشهای توالی یابی در سالهای اخیر توجه محققان حوزهی بیوانفورماتیک رابه خود جلب نموده اند استخراج دادههای هاپلوتایپ بااستفاده ازروشهای آزمایشگاهی گران وزمانبراست ازاین رومحققان حوزه محاسبات زیستی به استفاده از روشهای محاسباتی برای حل مساله استنتاج هاپلوتایپ که مسالهای NP-Hard است روی آورده اند این مقاله با رویکرپیشینه صرفه جویی به مساله استنتاج هاپلوتایپ میپردازد کارآمدبودن این رویکرد به وسیله مطالعات آزمایشگاهی ونظری مورد تایید قرارگرفته است همچنین الگوریتمهایی مبتنی براین رویکرد برای مساله استنتاج هاپلوتایپ ارائه شده است دراین مقاله الگوریتمی جدید برای حل مساله استنتاج هاپلوتایپ براساس الگوریتم جستجوی هارمونی وبارویکرد بیشینه صرفه جویی ارایه میشود اندازه فضایی که الگوریتمهای ارایه شده بر اساس روشهای فراابتکاری مورد جستجوقرارمیدهند به طول وتعداد توالیهای ژنوتایپ وابستهاست دراین تحقیق الگوریتمی پیشنهاد میشود که برخلاف روشها مذکور به جستجوی فضایجوابی میپردازد که اندازه آن تنهابستگی به تعداد جایگاههای هتروزیگوت برروی توالیهای ژنوتایپ دارد این خصوصیت الگوریتم راقادر میسازد که برای مجموعه توالیهای ژنوتایپی باطول وتعدادبیشتر به نحوی کاراعمل کند کیفیت روش پیشنهادی به وسیلهی مجموعهای ازدادههای واقعی ومصنوعی مورد بررسی قرارگرفته است ونتایج نشان از کاراییروش پیشنهادی درحل مساله استنتاج هاپلوتایپ دارد همچنین کیفیت توالیهای هاپلوتایپ پیش بینی شده به وسیله روش پیشنهادی بر خروجی برنامهای هاپلوتایپی مانند Phase ،Haplotyper ،HapinfreوcollHaps برتری دارد

استنتاج هاپلوتایپ بیشینه صرفه جویی جستجوی هارمونی