بهبود کارایی اندیس گذاری باروز-ویلر برای همترازسازی توالی های خوانش کوتاه با انتخاب زیرمجموعه ای از ماتریس پسوند

سال انتشار: 1395
نوع سند: مقاله کنفرانسی
زبان: فارسی
مشاهده: 557

فایل این مقاله در 7 صفحه با فرمت PDF قابل دریافت می باشد

استخراج به نرم افزارهای پژوهشی:

لینک ثابت به این مقاله:

شناسه ملی سند علمی:

ICIKT08_105

تاریخ نمایه سازی: 5 بهمن 1395

چکیده مقاله:

همترازسازی توالی ها یکی از وظایف مهم در بیوانفورماتیک است. الگوریتم های همترازسازی توالی ها در دو دسته ی کلی مبتنی بر برنامه نویسی پویا والگوریتم های ابتکاری قرار می گیرند. در الگوریتم های نوع دوم، اندیس گذاری ژنوم ها یک مرحله ی پیش نیاز مهم است. تبدیل باروز-ویلر یک روش اندیس گذاری پرکاربرد است که علاوه بر مصرف حافظه ی کم، ساختار مناسبی برای جستجوی سریع و دقیق در توالی ها فراهم می کند. این اندیس در سه مرحله ساخته می شود؛ ساختن ماتریس پسوند، مرتب سازی پسوندها و ساختن داده های کمکی مربوط به اندیس. بررسی ها نشان می دهد که مرحله ی مرتب سازی پسوندها دارای بیشترین زمان اجرا است بطوریکه برای یک توالی به طول 25600 نماد، بیش از 3 ساعت طول می کشد. در این مقاله یک روش برای بهبود زمان اندیس گذاری باروز-ویلر با استفاده از تغییری کوچک در مرتب سازی ماتریس پسوندها معرفی شده که بر اساس ویژگی های الگوریتم جستجوی دقیق عقبگرد پیشنهاد شده است. این الگوریتم جستجو یکی از الگوریتم های ابزار همترازسازی باروز-ویلر است که برای جستجوی توالی های خوانش کوتاه تولید شده توسط فناوری های تعیین توالی جدید (حداکثر 100 نماد)، در ژنوم ها به کار می رود. ایده ی اصلی، کاهش اندازه ی مسئله ی مرتب سازی با انتخاب پیشوندی از تمام سطرهای ماتریس پسوند بر اساس نیازهای الگوریتم جستجوی دقیق عقبگرد است؛ به طوریکه، در درستی الگوریتم جستجو تأثیر منفی نداشته باشد. نتایج حاصل از اجرای الگوریتم نشان می دهد که با انتخاب طول 100 برای پیشوندها، زمان اندیس گذاری یک توالی 25600 نمادی از حدود 4 / 3 ساعت به 5 / 3 دقیقه کاهش می یابد. با توجه به اینکه فناوری های تعیین توالی جدید، خوانش هایی با طول کوتاه تولید می کنند، می توان با انتخاب طول پیشوند متناسب با این فناوری ها، روش پیشنهادی را بدون از دست دادن درستی الگوریتم جستجو به کار برد.

نویسندگان

ربابه شریفی

گروه مهندسی کامپیوتر، دانشکده ی مهندسی، دانشگاه گیلان

اسدالله شاه بهرامی

گروه مهندسی کامپیوتر، دانشکده ی مهندسی، دانشگاه گیلان

مراجع و منابع این مقاله:

لیست زیر مراجع و منابع استفاده شده در این مقاله را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود مقاله لینک شده اند :
  • P. Pevzner, Computational Molecular Biology: An Algorithmic Approach, MIT press, ...
  • H. Li and R. Durbin, "Fast and Accurate Short Read ...
  • R. K. Menon, G. P. Bhat, and M. C. Schatz, ...
  • G. Nong, S. Zhang, and W. Hong Chan, "Two Efficiet ...
  • D. R. Singh and A. N. Arslan, "Using an Extended ...
  • U. Chandra Satish, P. kondikoppa, S. J. Park, M. Patil, ...
  • _ Comin, and M. Farerras, "Parallel Continuous Flow: a parallel ...
  • F. Kulla, and P. Sanders, "Scalable Parallel Suffix Array Construction, ...
  • W. Sun, "Using GPU to Accelerate Suffix Array Construction, " ...
  • M. Burrows, and D. J. Wheeler, "A Block-Sorting Lossless Data ...
  • P. Ferragina, and G. Manzini, "Opportunistic Data Structures with Applications, ...
  • J. S. Torres, I. B. Espert, A. T. Dominguez, V. ...
  • M. A. Quail, and et al, "A Tale of Three ...
  • _ Liu, and et al, "Comparison of Next- Generation Sequencing ...
  • H. Li, "Aligning Sequence Reads, Clone Sequences and Assembly Contigs ...
  • H. Li and R. Durbin, "Fast and Accurate Long-Read Transform, ...
  • Bioinformatics, vol. 26, no. 5, pp. 589-595, 2010. ...
  • نمایش کامل مراجع