الگوریتم ترکیبی HyperCollhaps برای مسئله استنباط هاپلوتایپ با دیدگاه صرفه جویی کامل

یک هاپلوتیپ مجموعه ای از چندشکلی های تک نوکلئوتیدی (اسنیپها)، و اسنیپ از معمول ترین ساختاری می باشد. از آنجایی که برخی از بیماریهای ژنتیکی ناشی از تغییرات در ساختار ژنوم است، بررسی هاپلوتیپ ها مورد توجه بسیاری از محققین قرار گرفته است. بدلیل محدودیتهای تکنیکی در بدست آوردن هاپلوتیپها، در اغلب موارد به جای هاپلوتیپ ها از ژنوتیپ ها که اطلاعات کمتری را دربردارند استفاده می شود. لذا مسئله بدست آوردن یک مجموعه هاپلوتیپ از روی ژنوتیپها، که استنباط هاپلوتیپ نامیده می شود، از اهمیت ویژه ای برخوردار است. در صورتیکه برای یک مجموعه ژنوتیپ به دنبال یافتن کمترین تعداد هاپلوتیپ مورد نیاز برای توصیف آن مجموعه باشیم مسئله ی استنباط هاپلوتیپ با دیدگاه صرفه جویی کامل را داریم. نشان داده شده است که مسئله استنباط هاپلوتیپ، در حالت صرفه جویی کامل، یک مسئله NP- سخت می باشد. الگوریتمهای غیر دقیق برای این مسئله دارای زمان اجرای نسبتاً پائینی هستند، اما در همه موارد به راه حل بهینه نمی رسند، ولی می توان هنوز کارایی آنها را بهبود بخشید. در این مقاله الگوریتم مکاشفه ای HyperCollhaps پیشنهاد می گردد. در این الگوریت از دو الگوریتم مکاشفه ای freeCollhaps و Collhaps استفاده می شود تا بتوان از ویژگیهای هر دو الگوریتم استفاده نمود. کارایی الگوریتم پیشنهادی توسط آزمایشات متعدد برای روی چندین مجموعه داده تأئید می گردد.

کلیدواژه ها:

استنباط هاپلوتیپ ، دیدگاه صرفه جویی کامل ، الگوریتم مکاشفه ای ، NP- سخت