Journal of Operational Research and Its Applications

fa یک مدل ریاضی جدید برای مساله استنباط هاپلوتایپ‌ها از ژنوتایپ‌ها با معیار پارسیمونی A New Mathematical Model for Haplotype Inference from Genotypes by Parsimony Criterion تخصصي Special پژوهشي Research مساله استنباط هاپلوتایپ ها از ژنوتایپ ها یکی از مسایل مهم حوزه ریاضیات زیستی است. اهمیت این مساله به دلیل کاربردهای فراوان آن در تشخیص و درمان بیماریهای ژنتیکی همچون دیابت، آلزایمر و امراض قلبی است که موجب رقابت پژوهشگران در ارایه مدل های ریاضی بهتر و طراحی الگوریتمهای کاراتر برای حل این مساله شده است. علیرغم پژوهشهای فراوان، به دلیل 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.   بیوانفورماتیک, استنباط هاپلوتایپ ها, مدل عدد صحیح, پارسیمونی, ژنوتایپ Bioinformatics, Haplotype inference, Integer programming, Parsimony, Genotype 61 77 http://jamlu.lahijan.iau.ir/browse.php?a_code=A-11-815-2&slc_lang=fa&sid=1 R. Feizabadi رضا فیض آبادی feizabadireza1@gmail.com 10031947532846006464 10031947532846006464 No Department of Applied Mathematics, Faculty of Mathematical Science, University of Guilan, Rasht, Iran گروه ریاضی کاربردی، دانشکده علوم ریاضی، دانشگاه گیلان، رشت M. Bagherian مهری باقریان mbagherian@guilan.ac.ir 10031947532846006465 10031947532846006465 Yes Department of Applied Mathematics, Faculty of Mathematical Science, University of Guilan, Rasht, Iran گروه ریاضی کاربردی، دانشکده علوم ریاضی، دانشگاه گیلان، رشت