همگذار ولوت

ولوت یک پکیج نرم‌افزاری می‌باشد که برای بازسازی ژنوم و ترتیب دهی هم ترازی ریدهای کوتاه به وجود آمده‌است. ولوت با دستکاری در گراف دی بر این از آن برای ساختن توالی ژنوم استفاده می‌کند که می‌توان خطاها را از بین ببرد و ناحیه‌های تکراری را تشخیص دهد. ولوت در پکیج‌های تجاری نیز پیاده‌سازی شده‌است.

مقدمه

توسعه روش‌های NGS باعث شد که هزینه هم ترازی ریدهای کوتاه افزایش یابد. دستکاری گراف دی بر این به عنوان یک روش برای هم ترازی مطرح شد با این حال برای برطرف کردن مشکل خطاها و نواحی تکراری به تکنیک‌های جدیدی نیار بود. این نیازمندی به توسعه ولوت توسط دنیل زربینو و اروان بیرنی در مرکز تحقیقات بیوانفورماتیک اروپا منجر شد.

ولوت با دست کاری در گراف دی بر این با استفاده از ساده زای و فشرده سازی، بدون اینکه اطلاعات مربوط به گراف از دست برود کار می‌کند. عملیات ساده‌سازی و فشرده سازی با تبدیل کردن مسیرهای غیر جالب به یک راس انجام می‌شود. عملیات حذف خطاها و برطرف کردن مشکل نواحی تکراری ابتدا با یک الگوریتم حذف خطا که توالی‌ها را با هم ادغام می‌کند انجام می‌شود، پس از آن نواحی تکراری با استفاده از حل‌کننده تکرار که مسیرهایی که همپوشانی محلی دارند را جدا می‌کند انجام می‌شود.

ترکیب ریدهای کوتاه و ریدهای جفت به ولوت این قدرت را می‌دهد که بتوان نواحی تکراری کوتاه را برطرف کند و کانتیگ‌هایی با طول قابل قبول تولید نماید. ولوت می‌تواند کانتیگ‌هایی تولید کند که مقدار N50 برای آن‌ها برابر 50kb در داده‌های مربوط به پروکاریوتها باشد و 3kb برای داده‌های مربوط به پستانداران باشد.

الگوریتم

همان‌طور که اشاره شد ولوت از گراف دی بر این برای همگذاری ریدهای کوتاه استفاده می‌کند. به‌طور دقیق تر ولوت برای هر کدام از رشته‌های بطول k که از ریدها بدست می‌آید یک راس در گراف در نظر می‌گیرد. دو راس در این گراف به هم متصل هستند اگر رشته k تایی متناظر آن‌ها یک همپوشانی بطول k-1 داشته باشند. به بیان دقیق تر یک یال جهت دار از راس A به راس B وجود دارد اگر و تنها اگر k-1 حرف آخر توالی مربوط به A برابر k-1 حرف اول توالی مربوط به B باشد. شکل زیر گراف دی بر این ای که توسط ولوت به وجود می‌آید را نمایش می‌دهد:

شکل ۱

همین فرایند برای معکوس مکمل همه رشته‌های بطول k بدست آمده نیز انجام می‌شود. تعدادی مرحله برای بهینه‌سازی گراف انجام می‌شود که به آن‌ها ساده‌سازی و حفظ خطا می‌گوییم.

ساده‌سازی

ادغام راس‌هایی که مسیرهای ایجاد شده در گراف را تحت تأثیر نمی‌گذارند، یک راه ساده برای کاهش میزان حافظه مصرفی می‌باشد، یعنی هنگامی که یک راس A فقط یک یال خروجی به راس B دارد و راس B نیز فقط یک یال ورودی دارد، می‌توانیم A و B را ادغام کنیم. ادغام دو راس و اطلاعات موجود در آن راس‌ها امکان‌پذیر است. شکل بعد این فرایند را برای مثال اولیه نشان می‌دهد.

شکل ۲

حذف خطا

خطاهای موجود در گراف می‌توانند توسط فرایند توالی یابی ایجاد شوند یا نمونه زیستی می‌تواند شامل تعدادی خطا باشد. ولوت سه نوع خطا را تشخیص می‌دهد: نک‌ها، حباب‌ها و ارتباط‌های اشتباه.

نوک‌ها

یک راس نوک در نظر می‌گیریم اگر شرایط اینکه ۱-راس یال ورودی یا خروجی نداشته باشد. ۲-طول اطلاعاتی که در راس ذخیره شده‌است از 2k کمتر باشد. ۳-یال‌هایی که به این راس ختم می‌شوند تعدد کمتری داشته باشند. را داشته باشد. راس‌های نوک را از گراف حذف می‌کنیم.

شکل ۳

حباب‌ها

حباب‌ها وقتی ایجاد می‌شوند که دو مسیر جداگانه شروع و پایان یکسانی داشته باشند. به‌طور طبیعی حباب‌ها توسط خطاهای زیستی یا تغییرات ژنتیکی ایجاد می‌شوند. این خطاها توسط الگوریتم تورباس حذف می‌شوند. یک مثال ساده از این نوع خطا در شکل زیر نمایش داده شده‌است:

شکل ۴

همچنین فرایند انجام حذف حباب‌ها برای مثال شکل ۱ و ۲ در زیر نشان داده شده‌است:

شکل ۵

ارتباط‌های اشتباه

ارتباط‌هایی که مسیرهای درستی را ایجاد نمی‌کند یا اینکه هیچ ساختار قابل شناسایی را در گراف ایجاد نمی‌کند را ارتباط‌های اشتباه می‌نامیم. ولوت این خطاها را بعد از انجام الگوریتم تورباس حذف می‌کند.

دستورهای ولوت

ولوت این این عملکردها را پشتیبانی می‌کند:

velveth

بعد از اجرای دستور velvetg تعدادی فایل تولید می‌شوند که مهترین آن‌ها یک فایل شامل همه کانتیگ‌های طولانی‌تر از 2k است که k طول کلمه استفاده شده در velveth می‌باشد.

انگیزه

روش‌های توالی یابی DNA مانند NGS بسیار محدود می‌باشند زیرا که ژنوم بسیار طولانی‌تر از طول هر رید است. به‌طور معمول روش‌های NGS با ریدهای کوتاه کار می‌کند و هزینه تولید هر رید در این روش نسبت به روش‌ها نسل اول بسیار کمتر است. همچنین انجام روش‌های NGS بسیار ساده‌تر است و قابلیت انجام موازی را دارا می‌باشند.

با این حال، ریدهای کوتاه حاوی اطلاعات کمتری نسبت به ریدهای طولانی می‌باشند و نیازمند پوشش بازسازی رید بالایی می‌باشند تا شامل همپوشانی‌های معنادار باشند. این مسئله باعث می‌شود که پیچیدگی توالی یابی افزایش یابد و بشدت نیازهای محاسبی را افزایش می‌دهد. تعداد زیاد رید همچنین باعث می‌شود که تعداد همپوشانی‌ها در گراف افزایش یابد که محاسبه گراف را سخت‌تر می‌کند.

برای غلبه بر این مشکلات، برنامه‌های توالی یابی پویا که هم به صورت کارا بودن و هم مقرون به صرفه بودند و قادر به حذف خطاها و تکرار بوند توسعه داده شدند. ولوت نیز برای این مقصود ایجاد شد و می‌تواند بازسازی ریدهای کوتاه بدون توالی مرجع را با زمان محاسبه کمتر و استفاده از حافظه کمتری نسبت به بقیه ابزارها انجام دهد.