بازسازی توالی
بازسازی توالی (به انگلیسی ) در بیوانفورماتیک، به ادغام و هم‌تراز کردن قسمت‌های مختلف توالی DNA برای بازسازی توالی اصلی اطلاق می‌شود. اهمیت بازسازی توالی در آن است که فناوری‌های موجود برای تعیین توالی DNA قادر به خواندن تمام ژنوم در یک مرحله نیستند و توالی به صورت قطعه‌های ۲۰ تا ۳۰۰۰۰ حرفی (هر حرف نشانهٔ یک باز است) خوانده می‌شود، این قطعه‌ها معمولاً نتیجهٔ رونویسی ژن (ESTها) یا تعیین توالی ژنوم با روش شاتگان‌اند.
می‌توان مسئلهٔ بازسازی توالی DNA را به این تشبیه کرد که؛ از یک کتاب نسخه‌های مختلفی ایجاد کنیم، هر نسخه را با دستگاهی متفاوت قطعه قطعه کنیم، تغییراتی در قطعه‌های ایجاد شده بدهیم، قطعاتی از کتاب‌های دیگر به آن‌ها اضافه کنیم و برخی قطعه‌ها را نابود کنیم و در نهایت بخواهیم با دیدن قطعه‌های نهایی، کتاب اصلی را بازسازی کنیم. مسئله حتی پیچیده‌تر می‌شود وقتی این کتاب شامل نوشته‌ها و قطعات تکراری بوده باشد. در اواخر دههٔ ۱۹۸۰ و اوایل دههٔ ۱۹۹۰ میلادی، اولین برنامه‌های بازسازی توالی به عنوان نسخه‌های پیشرفته‌تر از برنامه‌های سادهٔ هم‌ترازسازی معرفی شدند تا توالی‌هایی که دستگاه‌های تعیین توالی قطعاتی از آن‌ها را یافته بودند، بازسازی کنند.
با پیشرفت علم و فناوری، در ابتدا ژنوم ویروسهای ساده، سپس باکتریها و در نهایت یوکاریوتها مورد بررسی قرار گرفتند، و پیچیدگی مسئلهٔ بازسازی ژنوم با افزایش طول و پیچیدگی توالی‌های یافته شده بیشتر شد، پیچیدگی‌هایی از قبیل; دانشمندان برای بازسازی توالی‌های پیچیدهٔ ژنوم یوکاریوتهایی چون مگس سرکه (در سال ۲۰۰۰ میلادی) و انسان (در سال ۲۰۰۱ میلادی) ابزارهای بازسازی توالی‌ای همچون Celera Assembler و Arachne را ارائه کردند که قادر به بازسازی توالی‌هایی به طول ۱۰۰ تا ۳۰۰ میلیون حرف‌اند. پیروی این ابداعات، در مراکز بازسازی توالی‌های ژنوم، گروه‌هایی به ساخت ابرابزارهای بازسازی پرداختند که نمونهٔ متن بازی از آن AMOS است که تلاشی برای گردآوری دست‌یافته‌های مختلف در این زمینه بود.
پیچیدگی مسئلهٔ بازسازی توالی تحت تأثیر تعداد توالی و طول هرکدام است. تعداد زیادی توالی طولانی به یافتن بهتر همپوشانی‌ها کمک می‌کند، ولی زمان اجرای الگوریتم‌ها به صورت نمایی با تعداد و طول توالی‌ها افزایش می‌یابد. از طرفی، توالی‌های کوتاه‌تر به راحتی هم‌تراز می‌شوند، اما موجب پیچیدگی بازسازی می‌شوند، چراکه یافتن و استفاده از قسمت‌های تکراری در قطعات کوتاه‌تر، سخت‌تر است.
در ابتدا، تعداد کمی توالی کوتاه از ژنوم به سختی و پس از چند هفته تلاش در آزمایشگاه بدست می‌آمد که به راحتی و به صورت دستی (!) هم‌تراز می‌شدند.
با ابداع روش سنگر در سال ۱۹۷۵ میلادی و تا سال ۲۰۰۰ میلادی، فناوری به جایی رسید که ابزارهای پیشرفته و خودکار به صورت شبانه‌روزی توالی‌های ژنوم را بدست آورند و در نتیجهٔ آن نیاز به روش‌هایی برای پردازش توالی‌هایی ایجاد شده که; فناوری سنگر این امکان را ایجاد کرد که با تنها یک رایانه بتوان توالی‌های باکتری با ۲۰۰۰۰ تا ۲۰۰۰۰۰ قطعه را بازسازی کرد، اما بازسازی توالی‌های بزرگتر مانند ژنوم انسان (با حدود ۳۵ میلیون قطعه) همچنان نیاز به استفاده از پردازش موازی با چندین رایانه دارند.
شرکت بیوانفورماتیک در سال‌های ۲۰۰۴/۲۰۰۵ میلادی روش Pyroscequencing را معرفی کرد که قطعه‌های کوتاه‌تری نسبت به روش سنگر ایجاد می‌کرد (در ابتدا قطعاتی به طول حدود ۱۰۰ حرف و در حال حاضر ۴۰۰–۵۰۰ حرف)، و توان عملیاتی و سرعت بالای آن موجب شد مورد استفادهٔ مراکز بازسازی توالی قرار گیرد.
حجم داده‌ها و خطاهای ابزارهای توالی یابی در خواندن قطعات موجب تأخیر در ساخت ابزارهای بازسازی توالی شد و در ابتدا (سال ۲۰۰۴ میلادی) فقط ابزار از شرکت ۴۵۴ در دسترس بود. اولین ابزار در دسترس که می‌توانست علاوه بر قطعات ۴۵۴، ترکیب قطعات ۴۵۴ و سنگر را برای بازسازی ادغام کند، نسخهٔ ترکیبی ابزار MIRA بود که Chevreux و همکارانش در اواسط سال ۲۰۰۷ میلادی ارائه کردند و پس از آن به بازسازی توالی از توالی‌های یافته شده با فناوری های‌مختلف، بازسازی ترکیبی () اطلاق شد.
فناوری ایلومینا از سال ۲۰۰۶ میلادی در دسترس است که می‌تواند در هر اجرا حدود ۱۰۰ میلیون قطعه را، در یک دستگاه، بخواند (ژنوم انسان نیاز به خواندن حدود ۳۵ میلیون قطعه دارد) که در ابتدا طول این قطعات به ۳۶ حرف (باز) محدود بود که برای روش De-Novo مناسب نبود، اما هم‌اکنون طول این قطعات به بالای ۱۰۰ حرف می‌رسد.
ابزار بازسازی SHARCGS که اواخر سال ۲۰۰۷ میلادی معرفی شد، اولین ابزار بازسازی توالی بود که از قطعات توالی بدست آمده با Solexa (نام قبلی ایلومینا) استفاده می‌کرد که پس از آن چندین ابزار دیگر نیز ارائه شدند.
از ابزارها و فناوری‌های جدیدتر در این زمینه می‌توان به , , و اشاره کرد.
بازسازی برچسب توالی بیان شده () از جهات مختلفی با بازسازی توالی ژنوم متفاوت است; بازسازی EST خود پیچیدگی‌هایی نظیر پیرایش‌های دگرسان ()، تراپیرایش، چندریختی تک-نوکلئوتید و تغییرات پس از رونویسی () دارد.
بازسازی توالی ژنوم به دو صورت مختلف انجام می‌گیرد:
۱. De-Novo: بازسازی تمام توالی از قسمت‌های کوچکتر آن.
این روش بسیار کندتر است و حافظهٔ بیشتری مصرف می‌کند، چراکه تمامی قطعات باید با هم مقایسه شوند (که در حالت عادی از مرتبهٔ زمانی formula_1 است و البته با استفاده از جدول درهم‌سازی بهبود می‌یابد).
۲. استفاده از یک توالی اولیه و تطبیق قطعه‌های بدست آمده با قسمت‌های مختلف آن (mapping) برای ایجاد توالی‌ای جدید که مشابه توالی اولیه، ولی نه الزاماً یکسان با آن، است.
اگر از نوع توالی پیش زمینه‌ای داشته باشیم، لازم نیست از ابتدا تمام توالی را بازسازی کنیم و با داشتن یک توالی به عنوان قالب می‌توانیم تفاوت‌های جزئی آن با توالی مورد نظر را با استفاده از قطعات بدست آمده اصلاح کنیم.
این مسئله مشابه یافتن کوتاه‌ترین ابردنبالهٔ مشترک () برای رشته‌های داده شده‌است که راه حل حریصانهی آن بدین صورت است: البته این جواب الزاماً بهینه نیست.
ابزارهای بازسازی توالی که توانایی بازسازی De-Novo را در حداقل یکی از فناوری‌های پشتیبانی شده دارند در جدول زیر معرفی شده‌اند: