دو مدل برنامه ريزي خطي دودويي براي مساله‌ي برهم‌گذاري هاپلوتايپ در حالت تريپلوئيد

Two Binary Linear Programming Models for Haplotype Assembly Problem in Triploid Case

مساله‌ي برهم­ گذاري هاپلوتايپ عبارت است از يافتن هاپلوتايپ­ هاي منشأ تعدادي قطعه كه از روش­ هاي توالي­ يابي به­ دست آمده­ اند. درحالت ديپلوئيد كه مربوط به جانداران جفت كروموزومي مانند انسان است، درپي يافتن دو هاپلوتايپ هستيم كه هر كدام از خوانش­ ها از يكي از دو هاپلوتايپ نشأت گرفته باشند. اين مساله در حالت ديپلوئيد بسيار مورد مطالعه قرار گرفته و به­ دليل NP-hard بودن به ­خاطر وجود خطاهاي اجتناب­­­ ناپذير دستگاه­ هاي توالي­ يابي، روش­ هاي دقيق حل آن از مرتبه‌ي نمايي هستند. به ­همين دليل روش­ هاي سريع ­تر ولي تقريبي زيادي نيز براي آن ارايه شده ­اند. درحالت تريپلوئيد درپي يافتن سه هاپلوتايپ هستيم به­ طوري كه هر يك از خوانش ­ها نشأت گرفته از يكي از سه هاپلوتايپ باشند. حالت تريپلوئيد بسيار مشكل ­تر از حالت ديپلوئيد بوده و با چالش محاسباتي بيشتري مواجه است. به­ همين دليل محققان كمتر به اين مساله پرداخته­ اند. در اين مقاله دو مدل برنامه ­ريزي خطي دودويي براي اين مساله در دو حالت وجود و عدم وجود اطلاعات ژنوتايپ ارايه و كارايي محاسباتي آن­ها به­ كمك نرم­ افزار AIMMS روي داده­ هاي شبيه­ سازي­ شده مورد مطالعه قرار مي‌گيرند. مدل ­هاي ارايه شده قابليت تعميم به پلوئيدي­ هاي بالاتر را نيز دارند.

The haplotype assembly problem aims at finding originate haplotypes of some fragments that obtained from sequencing methods. In diploid case in which organisms have pair chromosomes, like humans, the aim is to reconstruct two haplotypes such that each of reads is originated from one of the two reconstructed haplotypes. In diploid case, the problem is well studied and since it is NP-hard due to unavoidable errors of sequencing machines, exact approaches are of exponential order. So, many fast, but approximate approaches have been proposed. In triploid case, the aim is finding three haplotypes such that each read originates from one of the three haplotypes. The triploid case is much harder than the diploid case and faces with more computational difficulties. For this reason, a few researchers studied the triploid case of haplotype assembly problem. In this paper, two binary linear programming models are proposed for two cases of availability and non-availability of genotype data for triploid haplotype assembly and the computational efficiency of the models is tested on simulated datasets using AIMMS. The proposed models could be generalized to higher ploidy.