Последовательная сборка - Sequence assembly

В биоинформатика, сборка последовательности относится к выравнивание и слияние фрагментов из более длинного ДНК последовательность, чтобы восстановить исходную последовательность. Это необходимо как Секвенирование ДНК технология не может считывать целые геномы за один раз, а скорее считывает небольшие фрагменты от 20 до 30 000 оснований, в зависимости от используемой технологии. Обычно короткие фрагменты, называемые чтениями, являются результатом секвенирование дробовика геномный ДНК, или транскрипт гена (EST ).

Задачу сборки последовательности можно сравнить со снятием множества копий книги, пропусканием каждой из них через измельчитель с другим резаком и сборкой текста книги вместе, просто глядя на измельченные части. Помимо очевидной сложности этой задачи, есть некоторые дополнительные практические вопросы: в оригинале может быть много повторяющихся абзацев, а некоторые фрагменты могут быть изменены во время измельчения, чтобы в них были опечатки. Также могут быть добавлены отрывки из другой книги, а некоторые фрагменты могут быть совершенно неузнаваемыми.

Сборщики генома

Первые ассемблеры последовательностей начали появляться в конце 1980-х - начале 1990-х годов как варианты более простых выравнивание последовательностей программы для объединения огромного количества фрагментов, генерируемых инструментами автоматического секвенирования, называемыми Секвенаторы ДНК. По мере увеличения размера и сложности секвенированных организмов вирусы над плазмиды к бактерии и наконец эукариоты ) программы сборки, используемые в этих геномные проекты требовались все более сложные стратегии для обработки:

терабайты данных секвенирования, требующих обработки вычислительные кластеры;
идентичные и почти идентичные последовательности (известные как повторяет) что может в худшем случае увеличивать сложность алгоритмов во времени и пространстве квадратично;
Ошибки чтения ДНК во фрагментах инструментов для секвенирования, что может затруднить сборку.

Столкнувшись с проблемой сборки первых более крупных геномов эукариот - плодовой мушки Drosophila melanogaster в 2000 году и геном человека всего через год - ученые разработали ассемблеры, такие как Celera Assembler^[1] и Арахна^[2] способен обрабатывать 130 миллионов геномов (например, плодовая муха D. melanogaster) до 3 миллиардов (например, геном человека) пар оснований. После этих усилий несколько других групп, в основном в крупных центрах секвенирования генома, создали крупномасштабные ассемблеры и проект с открытым исходным кодом, известный как AMOS.^[3] был запущен, чтобы объединить все инновации в технологии сборки генома под Открытый исходный код рамки.

Стратегия того, как ассемблер последовательности будет брать фрагменты (показаны под черной полосой) и сопоставлять перекрытия между ними для сборки окончательной последовательности (показаны черным цветом). Потенциально проблемные повторы показаны над последовательностью (розовым цветом выше). Без перекрывающихся фрагментов может быть невозможно назначить эти сегменты какой-либо конкретной области.

Монтажники EST

Выраженный тег последовательности или сборка EST была ранней стратегией, датируемой с середины 1990-х до середины 2000-х годов, для сборки отдельных генов, а не целых геномов. Проблема несколько отличается от сборки генома. Входные последовательности для сборки EST являются фрагментами записанного мРНК клетки и представляют собой только часть всего генома. Ряд алгоритмических проблем различается между геномом и сборкой EST. Например, геномы часто имеют большое количество повторяющихся последовательностей, сосредоточенных в межгенных областях. Транскрибируемые гены содержат намного меньше повторов, что несколько упрощает сборку. С другой стороны, некоторые гены экспрессируются (транскрибируются) в очень большом количестве (например, гены домашнего хозяйства ), что означает, что в отличие от полногеномного секвенирования с дробовиком, считывания не являются однородными по всему геному.

Сборка EST значительно усложняется такими функциями, как (cis-) альтернативное сращивание, транс-сплайсинг, однонуклеотидный полиморфизм, и посттранскрипционная модификация. Начиная с 2008 года, когда РНК-Seq была изобретена, секвенирование EST было заменено этой гораздо более эффективной технологией, описанной ниже сборка транскриптомов de novo.

De-novo и сборка карт

При последовательной сборке можно выделить два разных типа:

de-novo: сборка коротких прочтений для создания полноразмерных (иногда новых) последовательностей без использования шаблона (см. ассемблеры последовательности de novo, сборка транскриптомов de novo )
отображение: сборка чтений против существующей базовой последовательности, построение последовательности, которая похожа, но не обязательно идентична базовой последовательности

С точки зрения сложности и требований по времени сборки de-novo на порядки медленнее и потребляют больше памяти, чем сборки сопоставления. В основном это связано с тем, что алгоритм сборки должен сравнивать каждое чтение с каждым другим чтением (операция, имеющая наивную временную сложность O (п²). Ссылаясь на сравнение, проведенное с измельченными книгами во введении: в то время как для сопоставления сборок можно использовать очень похожую книгу в качестве шаблона (возможно, с измененными именами главных героев и несколькими местами), сборки de-novo представляют собой более сложную задачу. Задача состоит в том, что никто заранее не знает, станет ли это научной книгой, романом, каталогом или даже несколькими книгами. Кроме того, каждый клочок будет сравниваться с любым другим клочком.

Обработка повторов в сборке de-novo требует построения график представляющие соседние повторы. Такую информацию можно получить, прочитав длинный фрагмент, полностью покрывающий повторы, или только его два конца. С другой стороны, в сборке сопоставления детали с несколькими совпадениями или без них обычно оставляются для изучения другим методом сборки.^[4]

Влияние технологических изменений

Сложность сборки последовательности определяется двумя основными факторами: количеством фрагментов и их длиной. Хотя все больше и больше фрагментов позволяют лучше идентифицировать перекрытия последовательностей, они также создают проблемы, поскольку лежащие в основе алгоритмы демонстрируют квадратичное или даже экспоненциальное поведение сложности как для количества фрагментов, так и для их длины. И хотя более короткие последовательности быстрее выравниваются, они также усложняют этап компоновки сборки, поскольку более короткие чтения труднее использовать с повторами или почти идентичными повторами.

В первые дни секвенирования ДНК ученые могли получить только несколько коротких последовательностей (несколько десятков оснований) после недель работы в лабораториях. Следовательно, эти последовательности можно было выровнять вручную за несколько минут.

В 1975 г. прекращение дидезокси метод (AKA Секвенирование по Сэнгеру ) была изобретена, и вскоре после 2000 года технология была усовершенствована до точки, когда полностью автоматизированные машины могли производить последовательности в режиме высокой степени параллелизма 24 часа в сутки. В крупных центрах генома по всему миру размещались полные фермы этих секвенирующих машин, что, в свою очередь, привело к необходимости оптимизации ассемблеров для последовательностей из всего генома. секвенирование дробовика проекты, где читает

имеют длину около 800–900 оснований
содержат артефакты секвенирования, такие как секвенирование и клонирование векторов
имеют коэффициент ошибок от 0,5 до 10%

С помощью технологии Sanger бактериальные проекты с 20 000–200 000 считываний можно легко собрать на одном компьютере. Более крупные проекты, такие как геном человека с примерно 35 миллионами чтений, требовали больших вычислительных ферм и распределенных вычислений.

К 2004/2005 г. пиросеквенирование были доведены до коммерческой жизнеспособности 454 Науки о жизни. Этот новый метод секвенирования генерировал считывания намного короче, чем при секвенировании по Сэнгеру: первоначально около 100 оснований, теперь 400-500 оснований. Его гораздо более высокая пропускная способность и более низкая стоимость (по сравнению с секвенированием по Сэнгеру) подтолкнули к принятию этой технологии геномными центрами, что, в свою очередь, подтолкнуло к разработке сборщиков последовательностей, которые могли бы эффективно обрабатывать наборы для чтения. Огромный объем данных в сочетании со специфическими для технологии шаблонами ошибок при чтении задержал разработку ассемблеров; в начале 2004 г. только Newbler ассемблер от 454 был доступен. Выпущен в середине 2007 г.^[5] гибридная версия ассемблера MIRA, разработанная Chevreux et al. был первым свободно доступным ассемблером, который мог собирать 454 чтения, а также смеси 454 чтения и чтения Сэнгера. Впоследствии была придумана сборка последовательностей из различных технологий секвенирования. гибридная сборка.

С 2006 г. Иллюмина (ранее Solexa) технология была доступна и может генерировать около 100 миллионов операций чтения за цикл на одной машине для секвенирования. Сравните это с 35 миллионами прочтений проекта генома человека, которые потребовалось несколько лет для производства на сотнях секвенирующих машин. Изначально длина Illumina была ограничена 36 базами, что делало ее менее подходящей для сборки de novo (например, сборка транскриптомов de novo ), но более новые итерации технологии достигают длины чтения более 100 оснований с обоих концов клона 3-400bp. Анонсированный в конце 2007 года ассемблер SHARCGS^[6] Автор: Dohm et al. был первым опубликованным ассемблером, который использовался для сборки с чтениями Solexa. За ним быстро последовал ряд других.

Позже появились новые технологии, такие как Твердый из Прикладные биосистемы, Ион Торрент и SMRT были выпущены и новые технологии (например, Секвенирование нанопор ) продолжают появляться. Несмотря на более высокий процент ошибок, связанных с этими технологиями, они важны для сборки, поскольку их большая длина чтения помогает решить проблему повторения. Невозможно собрать идеальный повтор, длина которого превышает максимальную длину чтения; однако по мере того, как чтения становятся длиннее, вероятность идеального повторения такого большого становится меньше. Это дает преимущество при более длительных чтениях секвенирования при сборке повторов, даже если они имеют низкую точность (~ 85%).

Жадный алгоритм

Учитывая набор фрагментов последовательности, цель состоит в том, чтобы найти более длинную последовательность, содержащую все фрагменты.

Рассчитайте попарные выравнивания всех фрагментов.
Выберите два фрагмента с наибольшим перекрытием.
Объедините выбранные фрагменты.
Повторяйте шаги 2 и 3, пока не останется только один фрагмент.

Результат не обязательно должен быть оптимальным решением проблемы.

Программ

Для списков de-novo сборщики, см. Ассемблеры последовательностей de novo. Список выравнивателей карт см. Список программного обеспечения для выравнивания последовательностей § Выравнивание последовательностей с коротким считыванием.