الگوریتم‌ها و روش‌های سرهم‌بندی ژنوم

سرهم‌بندی ژنوم (Genome assembly) یک مسئله محاسباتی است که به بازسازی ژنوم از تعداد زیادی توالی‌های کوتاه یا بلند همپوشان تولید شده توسط توالی‌یابی می‌پردازد، زیرا هیچ فناوری کنونی نمی‌تواند یک کروموزوم کامل را از ابتدا تا انتها توالی‌یابی کند. الگوریتم‌هایی که این مسئله را حل می‌کنند، تعیین می‌کنند که ژنوم با چه میزان کامل بودن و دقتی می‌تواند از داده‌های توالی خام بازیابی شود.

Definition

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

Scope

این مدخل دو پارادایم الگوریتمی غالب، یعنی همپوشانی-چیدمان-اجماع (overlap-layout-consensus) و گراف دوبراین (de Bruijn graph)، تمایز بین سرهم‌بندی د نوو (de novo assembly) و سرهم‌بندی با هدایت مرجع (reference-guided assembly)، و مفاهیم کنتیگ‌ها (contigs) و اسکافولدها (scaffolds) را پوشش می‌دهد. این یک موضوع روش‌شناختی است که بر مرحله بازسازی محاسباتی تمرکز دارد و به پروتکل‌های آزمایشگاهی یا کاربرد بالینی نمی‌پردازد.

Core questions

• چرا توالی‌های توالی‌یابی شده باید سرهم‌بندی شوند و نمی‌توان آن‌ها را مستقیماً به عنوان کروموزوم‌های کامل خواند؟
• رویکردهای همپوشانی-چیدمان-اجماع و گراف دوبراین چه تفاوتی با هم دارند؟
• چه عواملی کامل بودن سرهم‌بندی را محدود می‌کنند و تکرارها و طول توالی چه اهمیتی دارند؟

Key concepts

• سرهم‌بندی همپوشانی-چیدمان-اجماع
• سرهم‌بندی گراف دوبراین
• k-mers
• کنتیگ‌ها و اسکافولدها
• سرهم‌بندی د نوو در مقابل سرهم‌بندی با هدایت مرجع
• حل تکرارها
• پیوستگی سرهم‌بندی (مثلاً N50)

Mechanisms

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

Clinical relevance

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

Evidence & guidelines

ادبیات روش‌شناختی عمدتاً اولیه و مبتنی بر مرور است تا مبتنی بر دستورالعمل: ایدوری و واترمن (1995) فرمول‌بندی گرافی را معرفی کردند که پیش‌بینی‌کننده سرهم‌بندی دوبراین بود، زربینو و بیرنی (2008) سرهم‌بندی گراف دوبراین را برای توالی‌های کوتاه با Velvet پایه‌گذاری کردند، و سرهم‌بندی شات‌گان کل ژنوم انسان (ونتر و همکاران، 2001) نمونه‌ای از پارادایم همپوشانی-چیدمان-اجماع در مقیاس بزرگ است.

History

سرهم‌بندهای اولیه از روش‌های همپوشانی-چیدمان-اجماع استفاده می‌کردند که برای توالی‌های نسبتاً بلند توالی‌یابی سنگر بسیار مناسب بودند، مانند سرهم‌بندی شات‌گان کل ژنوم انسان در سال 2001. تغییر به توالی‌یابی با توان عملیاتی بالا و توالی‌های کوتاه، روش‌های گراف دوبراین را که توسط فرمول‌بندی‌های گرافی از اواسط دهه 1990 پیش‌بینی شده بودند و در ابزارهایی مانند Velvet (2008) تحقق یافتند، به پارادایم غالب تبدیل کرد، در حالی که بازگشت بعدی توالی‌های بلند، علاقه به رویکردهای مبتنی بر همپوشانی را برای حل تکرارها دوباره زنده کرد.

Key figures

• Michael Waterman
• Daniel Zerbino
• Ewan Birney
• Eugene Myers

Seminal works

• idury-1995
• zerbino-2008
• venter-2001-asm

Frequently asked questions

تفاوت بین سرهم‌بندی د نوو و سرهم‌بندی با هدایت مرجع چیست؟

سرهم‌بندی د نوو ژنوم را تنها از روی توالی‌ها و بدون استفاده از توالی قبلی بازسازی می‌کند، در حالی که سرهم‌بندی با هدایت مرجع، توالی‌ها را در برابر یک ژنوم مرجع موجود هم‌تراز یا اسکافولد می‌کند تا به بازسازی کمک کند.

چرا سرهم‌بندی مناطق تکراری دشوار است؟

هنگامی که یک تکرار طولانی‌تر از توالی‌هایی است که آن را پوشش می‌دهند، الگوریتم نمی‌تواند تشخیص دهد که توالی از کدام کپی آمده است، که مسیرهای مبهمی ایجاد می‌کند و سرهم‌بندی را به قطعات کوتاه‌تر تقسیم می‌کند؛ توالی‌های بلندتر به حل این تکرارها کمک می‌کنند.