توالی‌یابی دنوو

**توالی‌یابی دنوو** (به انگلیسی: De novo sequence assemblers) روشی از توالی‌یابی ژنوم است که بدون داشتن ژنوم اولیه، قطعات کوتاه ("کانتیگ") توالی، قطعات بزرگ را تشکیل داده و توالی ژنوم یا ترانسکریپتوم را می‌سازند. به‌طور کلی دو روش حریصانه و گراف دی براین برای توالی‌یابی دنوو وجود دارند.

## انواع روش‌های توالی‌یابی دنوو
به‌طور کلی دو الگوریتم در توالی‌یاب‌های دنوو استفاده می‌شوند. روش الگوریتم حریصانه که در آن هدف پیدا کردن بهینهٔ محلی و الگوریتم گراف دی براین که هدف پیدا کردن بهینهٔ جهانی است. توالی‌یاب‌ها برای اهداف متفاوتی مانند توالی‌یابی ژنوم باکتری (توالی کوتاه)، توالی‌یابی ژنوم یوکاریوتها (توالی بلند) یا ترانسکریپتوم‌ها ساخته شده و مورد استفاده قرار می‌گیرند.

**توالی‌یاب‌هایی که از الگوریتم‌های حریصانه استفاده می‌کنند** بهینهٔ محلی را با سامان‌دهی خوانده‌های کوچک می‌یابند. آن‌ها ابتدا فاصلهٔ دوبه‌دوی خواندهها را محاسبه کرده، خوانده‌ها را بر حسب فاصلهٔ آن‌ها خوشه‌بندی کرده، از خوانده‌ها کانتیگ‌ها را تولید کرده و این فرایند را چندین بار تکرار می‌کنند. اگر مجموعهٔ خوانده‌ها بزرگ باشد، این الگوریتم‌ها به دلیل این که به بهینهٔ جهانی نمی‌رسند، خوب عمل نمی‌کنند. در حالی که اگر تعداد ناحیه‌های تکراری در خوانده‌ها زیاد باشد، الگوریتم‌های فوق بهتر عمل می‌کنند. نخستین توالی‌یاب‌های دنوو از الگوریتم‌های حریصانه استفاده می‌کردند.

**توالی‌یاب‌هایی که از گراف استفاده می‌کنند** به دو دسته تقسیم می‌شوند. گراف رشته‌ای و گراف دی براین. این دو روش در سال ۱۹۹۴ در کارگاهی توسط واترمن و جین مایرز معرفی شدند. از بین این دو روش، استفادهٔ روش گراف دی براین متداول‌تر است. در توالی‌یابی توسط گراف دی براین، خوانده‌ها به قطعات کوچک‌تری با طول یکسان k تقسیم می‌شوند. سپس از این k-تایی‌ها به عنوان یال‌های گراف دی براین استفاده می‌شود. گره‌های این گراف از تقسیم هر k-تایی به دو k - 1-تایی به دست می‌آیند. به این ترتیب گراف دی براین توسط توالی‌یاب ساخته می‌شود. این توالی‌یاب‌ها زمانی که تعداد خوانده‌ها زیاد باشند، بهتر از الگوریتم‌های حریصانه عمل می‌کنند.

جایگزین=مراحل طی شده در توالی یاب‌های دنوو|بندانگشتی|مراحل طی شده در توالی‌یاب‌های دنوو

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

## توالی‌یابی قطعات جفت-انتهایی
قطعات جفت-انتهایی زمانی تولید می‌شوند که طول قطعات مورد استفاده در توالی‌یابی طولانی بوده (۲۵۰ تا ۵۰۰ نوکلئوتید) و دو انتهای هر قطعه خوانده می‌شوند. به این ترتیب در هر قطعه، انتهای چپ، راست و فاصلهٔ بین این دو انتها را می‌دانیم. این فاصله معمولاً از یک توزیع نرمال با واریانس و میانگین مشخص پیروی می‌کند. دانستن دو انتها و فاصلهٔ بین آن دو به توالی‌یاب کمک کرده تا قطعات توالی داده را در کنار هم به درستی قرار دهد. با ایجاد تغییر در الگوریتم گراف دی براین می‌توان قطعات جفت-انتهایی را نیز توالی‌یابی کرد.

## مراحل توالی‌یابی دنوو
* خواندن دادهٔ خام توسط فناوری‌های توالی‌خوان
* بررسی کیفیت داده
* تمیز کردن داده
* تبدیل داده به کانتیگ‎ها و اسکافلد‎ها
* تعیین پارامترهای مورد استفاده در الگوریتم
* تعیین خروجی با استفاده از الگوریتم‌های مشخص

## توالی‌یاب وِلوِت
توالی‌یاب وِلوِت (Velvet) در گراف دی براین، تنها از خوانده‌های بسیار کوتاه و خوانده‌های جفت-انتهایی استفاده می‌کند. خوانده‌های کوتاه معمولاً برای توالی‌یابی در گراف دی براین مناسب نیستند زیرا تعداد تکرار بالایی داشته و در گراف ابهام ایجاد می‌کنند. در روش وِلوِت گراف دی‌براین به گونه‌ای تغییر داده می‌شود تا خطاها کاهش یافته و تکرارها شناسایی شوند. این دو مرحله به‌صورت مستقل از هم اجرا می‌شوند. در ابتدا الگوریتم خطایابی وِلوِت توالی‌هایی را که به هم مربوط هستند با هم ادغام کرده و سپس الگوریتم تکراریاب، مسیرهایی که با هم هم‌پوشانی دارند را از هم جدا می‌کند.

## توالی‌یابی ترنسکریپتوم دنوو
گذردهی بالای آران‌ای تغییری اساسی در توالی‌یابی ژنوم گونه‌هایی ایجاده کرده‌است که ژنوم مرجع آن‌ها وجود ندارد یا ناقص است. این تغییر با استفاده از تحلیل ترنسکریپتوم آن‌ها به وجود آمده‌است. هدف این روش این است که تمامی مجموعه‌های رونوشت موجود در داده بدون داشتن ژنوم مرجع بازسازی شوند. نتیجهٔ این توالی‌یاب‌ها تهیهٔ دادهٔ اولیه برای شناسایی تمامی رونوشت‌های تولید شده و ایزوفرم‌های آن‌ها است.

## توالی‌یاب‌های متداول مورد استفاده
توالی‌یاب‌های متفاوت برای فناوری‌های متفاوتی به کار می‌روند. خوانده‌های فناوری‌های نسل دوم معمولاً کوتاه‌تر بوده (۵۰ تا ۲۰۰ نوکلئوتید) و احتمال خطایی برابر با ۲ تا ۵ درصد دارند. خوانده‌های فناوری‌های نسل سوم و چهارم اما طولانی‌تر بوده (هزار تا ده هزار نوکلئوتید) و احتمال خطایی برابر با ۱۰ تا ۲۰ درصد دارند. به همین دلیل به الگوریتم‌های متفاوتی برای انواع خوانده‌ها و فناوری‌ها احتیاج است.

### [[:en:SPAdes (software)|الگوریتم SPAdes]]
این الگوریتم از یک گراف دی براین، که برای توالی‌یابی ژنوم‌های کوتاه‌تر مانند ژنوم باکتری، ساخته شده استفاده می‌کند.

### الگوریتم ری (Ray)
این الگوریتم یک توالی‌یاب شامل موارد زیر است:

ری (توالی‌یاب دنوو تک ژنوم)، ری‌متا (توالی‌یاب دنوو متاژنوم)، جامعهٔ ری (فراوانی میکروب و مشخصات طبقه‌بندی شده)، آنتولوژی ری (طبقه‌بندی آنتولوژی ژن)، نقشه‌بردار ری (محتوای ژن را بین نمونه‌های مختلف مقایسه می‌کند). ری همچنین دارای یک رابط در سطح وب به نام مرورگر ابری ری است.

### الگوریتم ABySS
یک توالی‌یاب دنوو موازی و جفت-انتهایی که برای توالی‌یابی ژنوم‌های طولانی از خوانده‌های کوتاه استفاده می‌شود. این توالی‌یاب شامل دو مدل ABySS(برای ژنوم) و Trans-ABySS (برای ترنسکریپتوم) است.

### الگوریتم ALLPATHS-LG
این توالی‌یاب نرم‌افزاریست که برای توالی‌یابی دنووی ژنوم‌های بزرگ و کوتاه مورد استفاده قرار می‌گیرد. این نرم‌افزار امکان بررسی تکرارها، تصحیح خطا و استفاده از کتابخانه‌های مرتبط را می‌دهد. این نرم‌افزار به صورت بهینه‌تری از حافظه استفاده کرده و نواحی با هم‌پوشانی کمتر را نیز توالی‌یابی می‌کند.

### الگوریتم ترینتی (Trinity)
این الگوریتم در سه مرحله توالی با کیفیت ترنسکریپتوم را تولید می‌کند. ۱) با استفاده از یک الگوریتم حریصانه پس از تولید کتابخانه‌ای از k-تایی‌ها، کانتیگ‌های ترنسکریپتوم ایجاد می‌کند. ۲) گراف دی براین این کانتیگ‌ها را تولید می‌کند. ۳) با استفاده از این گراف و وفق دادن آن با خوانده‌های اولیه، ترنسکریپ را تولید می‌کند.

### الگوریتم HGAP
این الگوریتم اولین توالی‌یاب خوانده‌های طولانی است که توسط گروه علوم بیولوژیکی اقیانوس آرام و مؤسسهٔ ژنومیک مشترک ساخته شد.

### الگوریتم فالکن (Falcon)
فالکن الگوریتمی است که توسط گروه علوم بیولوژیکی اقیانوس آرام برای توالی‌یابی خوانده‌های طولانی گونه‌های دیپلوئد طراحی شده‌است.

### الگوریتم کانو (Canu)
این توالی‌یاب برای کار بر روی خوانده‌های طولانی فناوری‌های نسل سوم و چهارم استفاده می‌شود. این توالی‌یاب در ادامهٔ نسل توالی‌یاب سلرا است.

### الگوریتم هینج (Hinge)
این توالی‌یاب نیز برای کار بر روی خوانده‌های طولانی فناوری‌های نسل سوم و چهارم استفاده می‌شود، اما به‌طور کلی برای ژنوم‌های کوتاه‌تر میکروب‌ها طراحی شده‌است.

## پانویس

رده:الگوریتم‌های بیوانفورماتیک
رده:توالی‌یابی دی‌ان‌ای
رده:نرم‌افزارهای بیوانفورماتیک
رده:نرم‌افزارهای متاژنومیکس