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

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

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

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

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

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

مزایای توالی‌یاب‌های دنوو

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

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

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

مراحل توالی‌یابی دنوو

خواندن دادهٔ خام توسط فناوری‌های توالی‌خوان
بررسی کیفیت داده
تمیز کردن داده
تبدیل داده به کانتیگ‎ها و اسکافلد‎ها
تعیین پارامترهای مورد استفاده در الگوریتم
تعیین خروجی با استفاده از الگوریتم‌های مشخص^[۹]

توالی‌یاب وِلوِت

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

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

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

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

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

الگوریتم SPAdes

این الگوریتم^[۱۱] از یک گراف دی براین، که برای توالی‌یابی ژنوم‌های کوتاه‌تر مانند ژنوم باکتری، ساخته شده استفاده می‌کند.

الگوریتم ری (Ray)

این الگوریتم^[۱۲] یک توالی‌یاب شامل موارد زیر است:

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

الگوریتم ABySS

یک توالی‌یاب دنوو موازی و جفت-انتهایی که برای توالی‌یابی ژنوم‌های طولانی از خوانده‌های کوتاه استفاده می‌شود. این توالی‌یاب شامل دو مدل ABySS^[۱۳](برای ژنوم) و Trans-ABySS^[۱۴] (برای ترنسکریپتوم) است.

الگوریتم ALLPATHS-LG

این توالی‌یاب^[۱۵] نرم‌افزاریست که برای توالی‌یابی دنووی ژنوم‌های بزرگ و کوتاه مورد استفاده قرار می‌گیرد. این نرم‌افزار امکان بررسی تکرارها، تصحیح خطا و استفاده از کتابخانه‌های مرتبط را می‌دهد. این نرم‌افزار به صورت بهینه‌تری از حافظه استفاده کرده و نواحی با هم‌پوشانی کمتر را نیز توالی‌یابی می‌کند.

الگوریتم ترینتی (Trinity)

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

الگوریتم HGAP

این الگوریتم^[۱۷] اولین توالی‌یاب خوانده‌های طولانی است که توسط گروه علوم بیولوژیکی اقیانوس آرام و مؤسسهٔ ژنومیک مشترک ساخته شد.

الگوریتم فالکن (Falcon)

فالکن^[۱۸] الگوریتمی است که توسط گروه علوم بیولوژیکی اقیانوس آرام برای توالی‌یابی خوانده‌های طولانی گونه‌های دیپلوئد طراحی شده‌است.

الگوریتم کانو (Canu)

این توالی‌یاب^[۱۹] برای کار بر روی خوانده‌های طولانی فناوری‌های نسل سوم و چهارم استفاده می‌شود. این توالی‌یاب در ادامهٔ نسل توالی‌یاب سلرا است.

الگوریتم هینج (Hinge)

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

پانویس

↑ Bang-Jensen, Jørgen; Gutin, Gregory; Yeo, Anders (2004-11-15). "When the greedy algorithm fails". Discrete Optimization. 1 (2): 121–127. doi:10.1016/j.disopt.2004.03.007. ISSN 1572-5286.
↑ 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.
↑ Huang, X. (Summer 1992). "A contig assembly program based on sensitive detection of fragment overlaps". Genomics. 14 (1): 18–25. doi:10.1016/s0888-7543(05)80277-0. ISSN 0888-7543. PMID 1427824.
↑ 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.{{cite journal}}: نگهداری یادکرد:استفاده از پارامتر نویسندگان (link)
↑ "DIMACS Workshop on Combinatorial Methods for DNA Mapping and Sequencing". October 1994.
↑ Idury, R. M.; Waterman, M. S. (1995). "A new algorithm for DNA sequence assembly". Journal of Computational Biology: A Journal of Computational Molecular Cell Biology. 2 (2): 291–306. doi:10.1089/cmb.1995.2.291. ISSN 1066-5277. PMID 7497130.
↑ Myers, E. W. (1995). "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.
↑ «De Novo Sequencing | Assemble novel genomes». www.illumina.com. دریافت‌شده در ۲۰۲۳-۱۰-۰۶.
↑ ^۹٫۰ ^۹٫۱ «Introduction to de novo genome assembly for Illumina reads - Bioinformatics Documentation». www.melbournebioinformatics.org.au. دریافت‌شده در ۲۰۲۳-۱۰-۰۶.
↑ Zerbino, D. R.; Birney, E. "Velvet: Algorithms for de novo short read assembly using de Bruijn graphs". {{cite journal}}: Cite journal requires |journal= (help)
↑ 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.
↑ 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.{{cite journal}}: نگهداری یادکرد:استفاده از پارامتر نویسندگان (link)
↑ 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.
↑ Birol, Inanç; Jackman, Shaun D.; Nielsen, Cydney B.; Qian, Jenny Q.; Varhol, Richard; Stazyk, Greg; Morin, Ryan D.; Zhao, Yongjun; Hirst, Martin (2009-11-01). "De novo transcriptome assembly with ABySS". Bioinformatics (Oxford, England). 25 (21): 2872–2877. doi:10.1093/bioinformatics/btp367. ISSN 1367-4811. PMID 19528083.
↑ «ALLPATHS-LG | High quality genome assembly from low cost data» (به انگلیسی). بایگانی‌شده از اصلی در ۲۵ ژوئیه ۲۰۱۹. دریافت‌شده در ۲۰۱۹-۰۷-۲۵.
↑ 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.
↑ Chin, Chen-Shan; Alexander, David H.; Marks, Patrick; Klammer, Aaron A.; Drake, James; Heiner, Cheryl; Clum, Alicia; Copeland, Alex; Huddleston, John (Spring 2013). "Nonhybrid, finished microbial genome assemblies from long-read SMRT sequencing data". Nature Methods (به انگلیسی). 10 (6): 563–569. doi:10.1038/nmeth.2474. ISSN 1548-7105.
↑ Chin, Chen-Shan; Peluso, Paul; Sedlazeck, Fritz J.; Nattestad, Maria; Concepcion, Gregory T.; Clum, Alicia; Dunn, Christopher; O'Malley, Ronan; Figueroa-Balderas, Rosa (Fall 2012). "Phased diploid genome assembly with single-molecule real-time sequencing". Nature Methods (به انگلیسی). 13 (12): 1050–1054. doi:10.1038/nmeth.4035. ISSN 1548-7105.
↑ Koren, Sergey; Walenz, Brian P.; Berlin, Konstantin; Miller, Jason R.; Bergman, Nicholas H.; Phillippy, Adam M. (2017-03-15). "Canu: scalable and accurate long-read assembly via adaptive k-mer weighting and repeat separation". Genome Research (به انگلیسی): gr.215087.116. doi:10.1101/gr.215087.116. ISSN 1088-9051. PMID 28298431.
↑ Kamath, Govinda M.; Shomorony, Ilan; Xia, Fei; Courtade, Thomas; Tse, David N. (2017-03-20). "HINGE: Long-read assembly achieves optimal repeat resolution". Genome Research (به انگلیسی): gr.216465.116. doi:10.1101/gr.216465.116. ISSN 1088-9051. PMID 28320918.

[1] Bang-Jensen, Jørgen; Gutin, Gregory; Yeo, Anders (2004-11-15). "When the greedy algorithm fails". Discrete Optimization. 1 (2): 121–127. doi:10.1016/j.disopt.2004.03.007. ISSN 1572-5286.

[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, X. (Summer 1992). "A contig assembly program based on sensitive detection of fragment overlaps". Genomics. 14 (1): 18–25. doi:10.1016/s0888-7543(05)80277-0. ISSN 0888-7543. 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.{{cite journal}}: نگهداری یادکرد:استفاده از پارامتر نویسندگان (link)

[5] "DIMACS Workshop on Combinatorial Methods for DNA Mapping and Sequencing". October 1994.

[6] Idury, R. M.; Waterman, M. S. (1995). "A new algorithm for DNA sequence assembly". Journal of Computational Biology: A Journal of Computational Molecular Cell Biology. 2 (2): 291–306. doi:10.1089/cmb.1995.2.291. ISSN 1066-5277. PMID 7497130.

[7] Myers, E. W. (1995). "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] «De Novo Sequencing | Assemble novel genomes». www.illumina.com. دریافت‌شده در ۲۰۲۳-۱۰-۰۶.

[:0-9] ۹٫۰ ^۹٫۱ «Introduction to de novo genome assembly for Illumina reads - Bioinformatics Documentation». www.melbournebioinformatics.org.au. دریافت‌شده در ۲۰۲۳-۱۰-۰۶.

[10] Zerbino, D. R.; Birney, E. "Velvet: Algorithms for de novo short read assembly using de Bruijn graphs". {{cite journal}}: Cite journal requires |journal= (help)

[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.{{cite journal}}: نگهداری یادکرد:استفاده از پارامتر نویسندگان (link)

[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ç; Jackman, Shaun D.; Nielsen, Cydney B.; Qian, Jenny Q.; Varhol, Richard; Stazyk, Greg; Morin, Ryan D.; Zhao, Yongjun; Hirst, Martin (2009-11-01). "De novo transcriptome assembly with ABySS". Bioinformatics (Oxford, England). 25 (21): 2872–2877. doi:10.1093/bioinformatics/btp367. ISSN 1367-4811. 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; Alexander, David H.; Marks, Patrick; Klammer, Aaron A.; Drake, James; Heiner, Cheryl; Clum, Alicia; Copeland, Alex; Huddleston, John (Spring 2013). "Nonhybrid, finished microbial genome assemblies from long-read SMRT sequencing data". Nature Methods (به انگلیسی). 10 (6): 563–569. doi:10.1038/nmeth.2474. ISSN 1548-7105.

[18] Chin, Chen-Shan; Peluso, Paul; Sedlazeck, Fritz J.; Nattestad, Maria; Concepcion, Gregory T.; Clum, Alicia; Dunn, Christopher; O'Malley, Ronan; Figueroa-Balderas, Rosa (Fall 2012). "Phased diploid genome assembly with single-molecule real-time sequencing". Nature Methods (به انگلیسی). 13 (12): 1050–1054. doi:10.1038/nmeth.4035. ISSN 1548-7105.

[19] Koren, Sergey; Walenz, Brian P.; Berlin, Konstantin; Miller, Jason R.; Bergman, Nicholas H.; Phillippy, Adam M. (2017-03-15). "Canu: scalable and accurate long-read assembly via adaptive k-mer weighting and repeat separation". Genome Research (به انگلیسی): gr.215087.116. doi:10.1101/gr.215087.116. ISSN 1088-9051. PMID 28298431.

[20] Kamath, Govinda M.; Shomorony, Ilan; Xia, Fei; Courtade, Thomas; Tse, David N. (2017-03-20). "HINGE: Long-read assembly achieves optimal repeat resolution". Genome Research (به انگلیسی): gr.216465.116. doi:10.1101/gr.216465.116. ISSN 1088-9051. PMID 28320918.

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]

[۷]

[۸]

[۹]

[۱۰]

[۱۱]

[۱۲]

[۱۳]

[۱۴]

[۱۵]

[۱۶]

[۱۷]

[۱۸]

[۱۹]

[۲۰]