يك مدل رياضي جديد براي مساله استنباط هاپلوتايپ‌ها از ژنوتايپ‌ها با معيار پارسيموني

A New Mathematical Model for Haplotype Inference from Genotypes by Parsimony Criterion

ساله استنباط هاپلوتايپ­ ها از ژنوتايپ­ ها يكي از مسايل مهم حوزه رياضيات زيستي است. اهميت اين مساله به ­دليل كاربردهاي فراوان آن در تشخيص و درمان بيماري­هاي ژنتيكي همچون ديابت، آلزايمر و امراض قلبي است كه موجب رقابت پژوهشگران در ارايه مدل­ هاي رياضي بهتر و طراحي الگوريتم­هاي كاراتر براي حل اين مساله شده است. علي­رغم پژوهش­هاي فراوان، به دليل NP-hard بودن مساله همچنان نياز به ارايه مدل­ هاي جديد و يا بهبود روش­هاي قبلي احساس مي­ شود. استنباط هاپلوتايپ­ ها تحت معيارهاي متفاوتي بيان مي­ شود. پارسيموني يكي از مهم­ترين آن هاست و در اين مقاله مساله با اين معيار مورد بررسي قرار گرفته است. روش ­هاي حل مساله استنباط هاپلوتايپ­ ها از ژنوتايپ­ ها با معيار پارسيموني به دو دسته دقيق و تقريبي تقسيم مي­ شود. اغلب روش­هاي دقيق مساله را به ­صورت يك مساله برنامه­ ريزي با اعداد صحيح فرمول­ بندي مي­ كنند. اخيرا در مقاله ­اي يك مدل دقيق به نام10HI Base - براي اين مساله ارايه شده كه ابتدا به هر هاپلوتايپ و ژنوتايپ يك عدد متناظر كرده و سپس مدل را بر اساس اين اعداد تشكيل مي­ دهد كه درآن هيچ متغير و قيدي متناظر جايگاه­ هاي هتروزيگوت به مساله تحميل نمي­ شود. در اين مقاله نيز با شيوه­ اي متفاوت به ژنوتايپ­ ها اعدادي متناظر كرده و بر اساس اين اعداد يك مساله برنامه ­ريزي با متغيرهاي دودويي و آميخته مي­ سازيم. در نتيجه اين تبديلات، مدل جديد، متغير عدد صحيح نداشته و متغيرهاي كم­تري نسبت به HI Base –10 دارد. به علاوه در مدل جديد هيچ متغير و قيدي متناظر جايگاه ­هاي هموزيگوت وجود ندارد و متغيرها به جايگاه­ هاي هتروزيگوت اختصاص داده مي­ شوند. با توجه به تعداد زياد جايگاه ­هاي هموزيگوت در مقايسه با جايگاه ­هاي هتروزيگوت در داده­ هاي واقعي ارزش اين مدل مشخص مي­ شود.

The haplotype inference is one of the most important issues in the field of bioinformatics. It is because of its various applications in the diagnosis and treatment of inherited diseases such as diabetes, Alzheimer's and heart disease, which has provided a competition for researchers in presentation of mathematical models and design of algorithms to solve this problem. Despite the existence of a robust literature, a need is still felt for providing new or improved methods because of the NP-hard nature of the problem. Haplotype inference is expressed by different criteria. Parsimony is one of the most important criteria here, and the problem in this study is examined with this criterion. Haplotype inference by parsimony criterion solving methods are divided into two categories: exact and approximate. The exact methods often formulate this problem as an integer programming model. Recently, in an article an exact model, HI Base- 10, for haplotype inference has been proposed, which first corresponds a number to each haplotype and genotype, and then forms the model based on these numbers. As a result of this action, it does not impose any variable and constraint corresponding to heterozygous sites in the model. In this paper, we correspond numbers to the genotype in a different approach and form a mixed binary model based on these numbers. As a result of this conversion, the new model has fewer variables than the HI Base- 10, and it doesn’t have integer variable. In addition, in the new model, there is no variable and constraint corresponding to homozygous sites, and they are assigned to heterozygous sites. In addition, the value of the model is determined considering the large number of homozygous sites compared with heterozygous sites.