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

دادههای هاپلوتایپ نقش بسزایی در مطالعات ژنتیکی از جمله بیماریهای پیچیده ژنی و مطالعات تکاملی ایفا میکند. از آنجایی که برخلاف ژنوتایپها، تعیین هاپلوتایپها از طریق آزمایشگاهی هزینهبر و زمانبر میباشد، توجه زیادی به استنباط هاپلوتایپها از طریق دادههای ژنوتایپ با استفاده از روشهای محاسباتی شدهاست. برخی از الگوریتم های ارائه شده برای حل این مسئله براساس قانون پارسیمونیاست. این قانون بیان میکند که تعداد هاپلوتایپهای متمایز در طبیعت بسیار کمتر از تعداد ژنوتایپهای متمایز است بنابراین از میان مجموعه هاپلوتایپهای ممکن، مجموعهای بهینهتر است که دارای کمترین کاردینالیتی باشد. مسئله استنباط هاپلوتایپها بر اساس بیشترین پارسیمونی NP- سخت است که به موجب آن، الگوریتمهای قطعی بر پایه پارسیمونی، محدود به یافتن جواب بر روی مجموعههای کوچک میشوند. در این مقاله، ما یک روش ابتکاری با استفاده از الگوریتم جستجوی هارمونی توسعه داده شده با گیپس سمپلینگ 2 ارائه کردهایم. کارایی این روش بر روی مجموعه ژنوتایپهای مختلفی تست شدهاست. آزمایشها نشان میدهد که این روش نسبت به الگوریتمهای موجود، جوابهایی با بیشترین پارسیمونی را بدست میآورد.

استنتاج هاپلوتایپ، بیشترین پارسیمونی، جستجوی هارمونی، گیپس سمپلینگ