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

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

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

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 NPhard 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 nonavailability 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.