بهبود کارایی اندیس گذاری باروز-ویلر برای همترازسازی توالی های خوانش کوتاه با انتخاب زیرمجموعه ای از ماتریس پسوند
Publish Year: 1395
نوع سند: مقاله کنفرانسی
زبان: Persian
View: 565
This Paper With 7 Page And PDF Format Ready To Download
- Certificate
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
ICIKT08_105
تاریخ نمایه سازی: 5 بهمن 1395
Abstract:
همترازسازی توالی ها یکی از وظایف مهم در بیوانفورماتیک است. الگوریتم های همترازسازی توالی ها در دو دسته ی کلی مبتنی بر برنامه نویسی پویا والگوریتم های ابتکاری قرار می گیرند. در الگوریتم های نوع دوم، اندیس گذاری ژنوم ها یک مرحله ی پیش نیاز مهم است. تبدیل باروز-ویلر یک روش اندیس گذاری پرکاربرد است که علاوه بر مصرف حافظه ی کم، ساختار مناسبی برای جستجوی سریع و دقیق در توالی ها فراهم می کند. این اندیس در سه مرحله ساخته می شود؛ ساختن ماتریس پسوند، مرتب سازی پسوندها و ساختن داده های کمکی مربوط به اندیس. بررسی ها نشان می دهد که مرحله ی مرتب سازی پسوندها دارای بیشترین زمان اجرا است بطوریکه برای یک توالی به طول 25600 نماد، بیش از 3 ساعت طول می کشد. در این مقاله یک روش برای بهبود زمان اندیس گذاری باروز-ویلر با استفاده از تغییری کوچک در مرتب سازی ماتریس پسوندها معرفی شده که بر اساس ویژگی های الگوریتم جستجوی دقیق عقبگرد پیشنهاد شده است. این الگوریتم جستجو یکی از الگوریتم های ابزار همترازسازی باروز-ویلر است که برای جستجوی توالی های خوانش کوتاه تولید شده توسط فناوری های تعیین توالی جدید (حداکثر 100 نماد)، در ژنوم ها به کار می رود. ایده ی اصلی، کاهش اندازه ی مسئله ی مرتب سازی با انتخاب پیشوندی از تمام سطرهای ماتریس پسوند بر اساس نیازهای الگوریتم جستجوی دقیق عقبگرد است؛ به طوریکه، در درستی الگوریتم جستجو تأثیر منفی نداشته باشد. نتایج حاصل از اجرای الگوریتم نشان می دهد که با انتخاب طول 100 برای پیشوندها، زمان اندیس گذاری یک توالی 25600 نمادی از حدود 4 / 3 ساعت به 5 / 3 دقیقه کاهش می یابد. با توجه به اینکه فناوری های تعیین توالی جدید، خوانش هایی با طول کوتاه تولید می کنند، می توان با انتخاب طول پیشوند متناسب با این فناوری ها، روش پیشنهادی را بدون از دست دادن درستی الگوریتم جستجو به کار برد.
Keywords:
اندیس گذاری ژنوم , تبدیل باروز-ویلر , بهبود کارایی اندیس گذاری , جستجوی دقیق توالی , همترازسازی توالی
Authors
ربابه شریفی
گروه مهندسی کامپیوتر، دانشکده ی مهندسی، دانشگاه گیلان
اسدالله شاه بهرامی
گروه مهندسی کامپیوتر، دانشکده ی مهندسی، دانشگاه گیلان
مراجع و منابع این Paper:
لیست زیر مراجع و منابع استفاده شده در این Paper را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود Paper لینک شده اند :