امروز چهارشنبه 1 آذر 1396

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

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

mgj-16-c-00253

ژنتیک جانوری

پژوهشی کامل

Fa

 

 

بازسازی هاپلوتیپ یکی از موضوعات مهم در مطالعات ژنتیکی و بیوانفورماتیکی است. تشکیل هاپلوتیپ‌ها به‌صورت مستقیم با استفاده از روش‌های زیستی و آزمایشگاهی بسیار دشوار و پرهزینه است. از این‌رو، بازسازی هاپلوتیپ‌ها معمولا با استفاده از روش‌های محاسباتی بر روی اطلاعات ژنوتیپی و نشانگرهای ژنتیکی انجام می‌شود. در این مقاله، دو الگوریتم بر اساس مدل حداقل تصحیح خطا برای بازسازی هاپلوتیپ‌ها از روی ژنوتیپ افراد برای چندشکلی‌های تک نوکلئوتیدی (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.

نویسندگان مقاله
ناممحل خدمتپست الکترونیکی

مصطفی قادری‌زفره‌ایی
m Ghaderi Zefrei

mghaderi[AT]yu.ac.ir نویسنده مسئول

صمد شریفی
s Sharifi

نویسنده مسئول

ماشاءا... عباسی دزفولی
m Abbassi Dezfouli

نویسنده مسئول

احسان عسگریان
e Asgarian

نویسنده مسئول

محمدحسین بناء بازی
mh Banabazi

نویسنده مسئول

مقالات چاپ شده