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

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

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

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

توالی یاب‎هایی که از الگوریتم‎های حریصانه استفاده می‎کنند بهینه محلی را با سامان‎دهی خوانده‎های کوچک می‎یابند. آن‎ها ابتدا فاصله دو‎به‎دوی خواندهها را محاسبه کرده، خوانده‎ها را بر حسب فاصله آن‎ها خوشه‎بندی کرده، از خوانده‎ها کانتیگ‎ها را تولید کرده و این فرایند را چندین بار تکرار می‎کنند. اگر مجموعه خوانده‎ها بزرگ باشد، این الگوریتم‎ها به دلیل این که به بهینه جهانی نمی‎رسند، خوب عمل نمی‎کنند، در حالی که اگر تعداد ناحیه‎های تکراری در خوانده‎ها زیاد باشد، الگوریتم های فوق بهتر عمل می‎کنند.[۱] نخستین توالی یاب‎های دنوو از الگوریتم‎های حریصانه استفاده می‎کردند.[۲][۳]

توالی یاب‎هایی که از گراف استفاده می‎کنند[۴] به دو دسته تقسیم می‎شوند.گراف رشته ای و گراف دی براین. این دو روش در سال 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

این توالی یاب [۲۰] نیز برای کار بر روی خوانده‎های طولای فناوری های نسل سوم و چهارم استفاده می‎شود، اما به طور کلی برای ژنوم های کوتاه‎تر میکروب‎ها طراحی شده است.

پانویسویرایش

  1. J. Bang-Jensen; G. Gutin; A. Yeo (2004). "When the greedy algorithm fails". Discrete Optimization. 1 (2): 121–127. doi:10.1016/j.disopt.2004.03.007.
  2. Peltola, Hannu; Söderlund, Hans; Ukkonen, Esko (1984-01-11). "SEQAID: a DNA sequence assembling program based on a mathematical model". Nucleic Acids Research. 12 (1Part1): 307–321. doi:10.1093/nar/12.1Part1.307. ISSN 0305-1048. PMC 321006. PMID 6320092.
  3. Huang, Xiaoqiu (1992-09-01). "A contig assembly program based on sensitive detection of fragment overlaps". Genomics. 14 (1): 18–25. doi:10.1016/S0888-7543(05)80277-0. PMID 1427824.
  4. Compeau, Phillip EC, Pavel A. Pevzner, and Glenn Tesler (2011). "How to apply de Bruijn graphs to genome assembly". Nature Biotechnology. 29 (11): 987–991. doi:10.1038/nbt.2023. PMC 5531759. PMID 22068540.
  5. "DIMACS Workshop on Combinatorial Methods for DNA Mapping and Sequencing". October 1994.
  6. Idury, R. M.; Waterman, M. S. (1995-01-01). "A new algorithm for DNA sequence assembly". Journal of Computational Biology: A Journal of Computational Molecular Cell Biology. 2 (2): 291–306. CiteSeerX 10.1.1.79.6459. doi:10.1089/cmb.1995.2.291. ISSN 1066-5277. PMID 7497130.
  7. Myers, E. W. (1995-01-01). "Toward simplifying and accurately formulating fragment assembly". Journal of Computational Biology: A Journal of Computational Molecular Cell Biology. 2 (2): 275–290. doi:10.1089/cmb.1995.2.275. ISSN 1066-5277. PMID 7497129.
  8. What Is De Novo Sequencing?
  9. ۹٫۰ ۹٫۱ De novo Genome Assembly for Illumina Data
  10. Zerbino, D. R.; Birney, E. "Velvet: Algorithms for de novo short read assembly using de Bruijn graphs".
  11. Bankevich, Anton; et al. (2012). "SPAdes: a new genome assembly algorithm and its applications to single-cell sequencing". Journal of Computational Biology. 19 (5): 455–477. doi:10.1089/cmb.2012.0021. PMC 3342519. PMID 22506599.
  12. Boisvert, Sébastien, François Laviolette, and Jacques Corbeil (2010). "Ray: simultaneous assembly of reads from a mix of high-throughput sequencing technologies". Journal of Computational Biology. 17 (11): 1519–1533. doi:10.1089/cmb.2009.0238. PMC 3119603. PMID 20958248.
  13. Simpson, Jared T.; et al. (2009). "ABySS: a parallel assembler for short read sequence data". Genome Research. 19 (6): 1117–1123. doi:10.1101/gr.089532.108. PMC 2694472. PMID 19251739.
  14. Birol, Inanç; et al. (2009). "De novo transcriptome assembly with ABySS". Bioinformatics. 25 (21): 2872–2877. doi:10.1093/bioinformatics/btp367. PMID 19528083.
  15. «ALLPATHS-LG | High quality genome assembly from low cost data» (به انگلیسی). دریافت‌شده در ۲۰۱۹-۰۷-۲۵.
  16. Grabherr, Manfred G.; et al. (2011). "Full-length transcriptome assembly from RNA-Seq data without a reference genome". Nature Biotechnology. 29 (7): 644–652. doi:10.1038/nbt.1883. PMC 3571712. PMID 21572440.
  17. Chin, Chen-Shan, David H. Alexander, Patrick Marks, Aaron A. Klammer, James Drake, Cheryl Heiner, Alicia Clum et al. "Nonhybrid, finished microbial genome assemblies from long-read SMRT sequencing data." Nature methods 10, no. 6 (2013): 563-569. Available online
  18. Chin, Chen-Shan, Paul Peluso, Fritz J. Sedlazeck, Maria Nattestad, Gregory T. Concepcion, Alicia Clum, Christopher Dunn et al. "Phased diploid genome assembly with single-molecule real-time sequencing." Nature methods 13, no. 12 (2016): 1050-1054. Available here
  19. Koren, Sergey, Brian P. Walenz, Konstantin Berlin, Jason R. Miller, Nicholas H. Bergman, and Adam M. Phillippy. "Canu: scalable and accurate long-read assembly via adaptive k-mer weighting and repeat separation." Genome research 27, no. 5 (2017): 722-736. Available here
  20. Kamath, Govinda M., Ilan Shomorony, Fei Xia, Thomas A. Courtade, and N. Tse David. "HINGE: long-read assembly achieves optimal repeat resolution." Genome research 27, no. 5 (2017): 747-756. Available here