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

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