ارائه یک الگوریتم هیوریستیک برای حل مسئله بازسازی هاپلوتایپ با رویکرد حداقل تصحیح خطا

چند شکلی تک نوکلئوتیدی (اسنیپ) رایج ترین شکل تغییر در دیانای انسانی است. به توالی اسنیپها بر روی هر کروموزوم، هاپلوتایپ گفته می شود. از آنجائیکه برخی از بیماریهای ژنتیکی براثر تغییرات در ساختار ژنوم بروز می نمایند، از این رو مطالعه هاپلوتایپها وبه تبع آن مسئله بازسازی هاپلوتایپ مورد توجه بسیاری از محققین قرار گرفته است. همواره توالیهای بدست آمده از توالی یابها همراه با خطا هستند، که این قضیه ساخت هاپلوتایپها را پیچیده می کند. خصوصاً رویکرد حداقل تصحیح خطا، که از معروفترین نسخه های این مسئله بوده و ثابت شده که از دسته مسائل NP- سخت است. در این مقاله، یک روش جدید به نام ErrHapSAT مشابه HapSAT بوده با این تفاوت که آن، ابتدا ستونها را به هتروزیگوت و هوموزیگوت تفکیک کرده و سپس مقادیر برخی از ستونهای هوموزیگوت را شناسایی می کند. نتایج حاصل از آزمایشها نشان می دهد که این روش بدون کاهش سرعت، موجب افزایش دقت هاپلوتایپهای ساخته شده می شود، که در تحلیل هاپلوتایپهای بدست آمده بسیار اثر گذار می باشد. بنابراین روش پیشنهادی، جایگزین بهترین روش هیوریستیک فعلی برای بازسازی هاپلوتایپ می شود.

کلیدواژه ها:

بازسازی هاپلوتایپ ، NP- سخت ، حداقل تصحیح خطا ، هیوریستیک