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

انواع روش های توالی یابی دنوو

به طور کلی دو الگوریتم در توالی یاب‎های دنوو استفاده می‎شوند. روش الگوریتم حریصانه که در آن هدف پیدا کردن بهینه محلی و الگوریتم گراف دی براین که هدف پیدا کردن بهینه جهانی است. توالی یاب‎ها برای اهداف متفاوتی مانند توالی یابی ژنوم باکتری (توالی کوتاه)، توالی یابی ژنوم یوکاریوتها (توالی بلند) و یا ترانسکریپتوم‎ها ساخته شده و مورد استفاده قرار می‎گیرند.
توالی یاب‎هایی که از الگوریتم‎های حریصانه استفاده می‎کنند بهینه محلی را با سامان‎دهی خوانده‎های کوچک می‎یابند. آن‎ها ابتدا فاصله دو‎به‎دوی خواندهها را محاسبه کرده، خوانده‎ها را بر حسب فاصله آن‎ها خوشه‎بندی کرده، از خوانده‎ها کانتیگ‎ها را تولید کرده و این فرایند را چندین بار تکرار می‎کنند. اگر مجموعه خوانده‎ها بزرگ باشد، این الگوریتم‎ها به دلیل این که به بهینه جهانی نمی‎رسند، خوب عمل نمی‎کنند، در حالی که اگر تعداد ناحیه‎های تکراری در خوانده‎ها زیاد باشد، الگوریتم های فوق بهتر عمل می‎کنند. نخستین توالی یاب‎های دنوو از الگوریتم‎های حریصانه استفاده می‎کردند.  
توالی یاب‎هایی که از گراف استفاده می‎کنند به دو دسته تقسیم می‎شوند.گراف رشته ای و گراف دی براین. این دو روش در سال 1994 در کارگاهی  توسط واترمن و جین مایرز معرفی شدند. از بین این دو روش، استفاده روش گراف دی براین متداول‎تر است. در توالی یابی توسط گراف دی براین، خوانده‎ها به قطعات کوچک تری با طول یکسان k تقسیم می‎شوند. سپس از این k-تایی‎ها به عنوان یال های گراف دی براین استفاده می‎شود. گره های این گراف از تقسیم هر k-تایی به دو k - 1-تایی به دست می‎آیند. به این ترتیب گراف دی براین توسط توالی یاب ساخته می‎شود. این توالی یاب‎ها زمانی که تعداد خوانده‎ها زیاد باشند، بهتر از الگوریتم های حریصانه عمل می‎کنند.

فواید استفاده از توالی یاب‎های دنوو

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

توالی یابی قطعات جفت-انتهایی

قطعات جفت-انتهایی زمانی تولید می‎شوند که طول قطعات مورد استفاده در توالی یابی طولانی بوده (250 تا 500 نوکلئوتاید) و دو انتهای هر قطعه خوانده می‎شوند. به این ترتیب در هر قطعه، انتهای چپ، راست و فاصله بین این دو انتها را می‎دانیم.‎ این فاصله معمولاً از یک توزیع نرمال با واریانس و میانگین مشخص پیروی می‎کند. دانستن دو انتها و فاصله بین آن دو به توالی یاب کمک کرده تا قطعات توالی داده را در کنار هم به درستی قرار دهد. با ایجاد تغییر در  الگوریتم گراف دی براین می‎توان قطعات جفت-انتهایی را نیز توالی یابی کرد.

توالی یاب ول‎وت

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

توالی یابی ترنسکریپتوم دنوو

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

توالی‎یاب های متدوال مورد استفاده

توالی‎ یاب‎های متفاوت برای فناوری‎های متفاوتی به کار می‎روند. خوانده‎های فناوری‎های نسل دوم معمولاً کوتاه تر بوده( 50 تا 200 نوکلئوتاید) و احتمال خطایی برابر با 2 تا 5 درصد دارند. خوانده‎های فناوری های نسل سوم و چهارم اما طولانی تر بوده( هزار تا ده‎هزار نوکلئوتاید) و احتمال خطایی برابر با 10 تا 20 درصد دارند. به همین دلیل به الگوریتم‎های متفاوتی برای انواع خوانده‎ها و فناوری‎ها احتیاج است.

الگوریتم SPAdes

این الگوریتم از یک گراف دی براین ،که برای توالی‎یابی ژنوم‎های کوتاه‎تر مانند ژنوم باکتری، ساخته شده استفاده می‎کند.

الگوریتم ری

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

الگوریتم ABySS

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

الگوریتم ALLPATHS-LG

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

الگوریتم ترینتی

به انگلیسی: Trinity
این الگوریتم  در سه مرحله توالی با کیفیت ترنسکریپتوم را تولید می‎کند. 1) با استفاده از یک الگوریتم حریصانه پس از تولید کتابخانه ای از k-تایی ها، کانتیگ‎های ترنسکریپتوم ایجاد می‎کند. 2) گراف دی براین این کانتیگ‎ها را تولید می‎کند. 3) با استفاده از این گراف و وفق دادن آن با خوانده‎های اولیه، ترنسکریپ را تولید می‎کند.

الگوریتم HGAP

این الگوریتم  اولین توالی یاب خوانده‎های طولانی است که توسط گروه علوم بیولوژیکی اقیانوس آرام و موسسه ژنومیک مشترک ساخته شد.

الگوریتم فالکن

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

الگوریتم کانو

به انگلیسی: Canu
این توالی یاب برای کار بر روی خوانده‎های طولای فناوری های نسل سوم و چهارم استفاده می‎شود. این توالی یاب در ادامه نسل توالی یاب سلرا است.

الگوریتم هینج

به انگلیسی: Hinge
این توالی یاب نیز برای کار بر روی خوانده‎های طولای فناوری های نسل سوم و چهارم استفاده می‎شود، اما به طور کلی برای ژنوم های کوتاه‎تر میکروب‎ها طراحی شده است.