همگذار ولوت

ولوت یک پکیج نرم‌افزاری می‌باشد که برای بازسازی ژنوم و ترتیب دهی هم ترازی ریدهای کوتاه بوجود آمده است. ولوت با دستکاری در گراف دی براین از آن برای ساختن توالی ژنوم استفاده می‌کند که می‌توان خطاها را از بین ببرد و ناحیه‌های تکراری را تشخیص دهد. ولوت در پکیج‌های تجاری نیز پیاده‌سازی شده است.
مقدمه
توسعه روش‌های 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 را ایجاد می‌کند. velvetg این دستور گراف دی براین را از رشته‌های بطو k که از دستور velveth بدست آمده‌اند را ایجاد می‌کند و ساده‌سازی و حذف خطا را در گراف انجام می‌دهد و سپس کانتیگ‌ها را شناسایی می‌کند.
بعد از اجرای دستور velvetg تعدادی فایل تولید می‌شوند که مهترین آنها یک فایل شامل همه کانتیگ‌های طولانی‌تر از 2k است که k طول کلمه استفاده شده در velveth می‌باشد.
انگیزه
روش‌های توالی یابی DNA مانند NGS بسیار محدود می‌باشند زیرا که ژنوم بسیار طولانی‌تر از طول هر رید است. بطور معمول روش‌های NGS با ریدهای کوتاه کار می‌کند و هزینه تولید هر رید در این روش نسبت به روش‌ها نسل اول بسیار کمتر است. همچنین انجام روش‌های NGS بسیار ساده‌تر است و قابلیت انجام موازی را دارا می‌باشند.
با این حال، ریدهای کوتاه حاوی اطلاعات کمتری نسبت به ریدهای طولانی می‌باشند و نیازمند پوشش بازسازی رید بالایی می‌باشند تا شامل همپوشانی‌های معنادار باشند. این مسئله باعث می‌شود که پیچیدگی توالی یابی افزایش یابد و بشدت نیازهای محاسبی را افزایش می‌دهد. تعداد زیاد رید همچنین باعث می‌شود که تعداد همپوشانی‌ها در گراف افزایش یابد که محاسبه گراف را سخت‌تر می‌کند.
برای غلبه بر این مشکلات، برنامه‌های توالی یابی پویا که هم بصورت کارا بودن و هم مقرون به صرفه بودند و قادر به حذف خطاها و تکرار بوند توسعه داده شدند. ولوت نیز برای این مقصود ایجاد شد و می‌تواند بازسازی ریدهای کوتاه بدون توالی مرجع را با زمان محاسبه کمتر و استفاده از حافظه کمتری نسبت به بقیه ابزارها انجام دهد.