بهينه سازي و تلفيق الگوريتم هاي k-means و PSO جهت بازسازي هاپلوتيپ ها با استفاده از اطلاعات نشانگرهاي SNP

Optimizing and integrating K - means and PSO algorithms for haplotype reconstruction using SNP maker information

بازسازي هاپلوتيپ يكي از موضوعات مهم در مطالعات ژنتيكي و بيوانفورماتيكي است. تشكيل هاپلوتيپ ها به صورت مستقيم با استفاده از روش هاي زيستي و آزمايشگاهي بسيار دشوار و پرهزينه است. از اين رو، بازسازي هاپلوتيپ ها معمولا با استفاده از روش هاي محاسباتي بر روي اطلاعات ژنوتيپي و نشانگرهاي ژنتيكي انجام مي شود. در اين مقاله، دو الگوريتم بر اساس مدل حداقل تصحيح خطا براي بازسازي هاپلوتيپ ها از روي ژنوتيپ افراد براي چندشكلي هاي تك نوكلئوتيدي (SNP) ارايه مي شود. الگوريتم اول حالتي از الگوريتم K-Meansاست با اين تفاوت كه اين الگوريتم بجاي استفاده از مراكز اوليه تصادفي، اين مراكز را با شرايط ويژه انتخاب مي كند. الگوريتم دوم نيز تركيبي از الگوريتم PSO بهبوديافته و K-Means است كه IPSOKM نام گذاري شد. الگوريتم هاي بهينه سازي شده بر روي داده هاي شبيه سازي شده و واقعي به كار گرفته شدند. نتايج نشان داد كه دقت بازسازي هاپلوتيپ ها با استفاده از الگوريتم هاي ارايه شده در مقايسه با برخي از الگوريتم هاي مرسوم استفاده شده جهت بازسازي هاپلوتيپ ها، به خصوص در حالت هاي وجود خطا و حفره، به طور قابل ملاحظه اي افزايش يافت. از اين رو، اين الگوريتم ها مي توانند به طور موثري در مطالعات ژنتيك انساني و به نژادي گياه و دام به كار گرفته شوند.

Haplotype reconstruction is one of the main topics in genetic and bioinformatics studies. Construction haplotype directly through biological experiments is costly and cumbersome task. Therefore, haplotype reconstruction is generally done using algorithms and computational methods on genetic and genotype data. In this study, we present two algorithms, based upon minimal error correction model, to reconstruct haplotype from SNP and genotype data. The first algorithm is special case of K-Means algorithm that would select primary random centers with particular conditions. The second algorithm, is a combination of improved PSO and K-Means that we called up IPSOKM. The optimized algorithms were applied on real and simulated data. The results showed that haplotype reconstruction accuracy in comparing with general reconstruction haplotype algorithms, improved especially when there were gap and error. Overall, the presented algorithms could efficiently be used in human genetics as well as in plant and animal breeding studies.