Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

Ассемблеры генома [ править ]

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

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

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

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

Ассемблеры EST [ править ]

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

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

De-novo и сборка карт [ править ]

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

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

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

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

Влияние технологических изменений [ править ]

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

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

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

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

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

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

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

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

Жадный алгоритм [ править ]

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

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

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

Программы [ править ]

В течение списков де-NOVO монтажников см De Novo монтажники последовательности . Для получения списка выравнивателей для картирования см. Список программного обеспечения для выравнивания последовательностей § Выравнивание последовательностей с коротким считыванием .

См. Также [ править ]

  • Ассемблеры последовательностей de novo
  • Выравнивание последовательности
  • Сборка транскриптомов de novo
  • Установить проблему с обложкой
  • Список секвенированных геномов животных

Ссылки [ править ]

  1. ^ Майерс, EW; Sutton, GG; Делчер, AL; Роса, IM; Фасуло, Д.П .; Фланиган, MJ; Kravitz, SA; Mobarry, CM; и другие. (Март 2000 г.). «Полногеномная сборка дрозофилы». Наука . 287 (5461): 2196–204. Bibcode : 2000Sci ... 287.2196M . CiteSeerX  10.1.1.79.9822 . DOI : 10.1126 / science.287.5461.2196 . PMID  10731133 . S2CID  6049420 .
  2. ^ Batzoglou, S .; Jaffe, DB; Стэнли, К. Батлер, Дж; Gnerre, S; Мусели, E; Бергер, Б ; Месиров, JP; Лендер, ES (январь 2002 г.). «ARACHNE: полногеномный ассемблер дробовика» . Геномные исследования . 12 (1): 177–89. DOI : 10.1101 / gr.208902 . PMC 155255 . PMID 11779843 .  
  3. ^ Страница AMOS со ссылками на различные статьи
  4. ↑ Волк, Бит. «Сборка генома de novo против сопоставления с эталонным геномом» (PDF) . Университет прикладных наук Западной Швейцарии . Проверено 6 апреля 2019 .
  5. ^ Скопируйте в группы Google сообщение о гибридной версии MIRA 2.9.8 в группе Usenet bionet.software.
  6. ^ Дом, JC; Lottaz, C .; Бородина, Т .; Химмельбауэр, Х. (ноябрь 2007 г.). «SHARCGS, быстрый и высокоточный алгоритм сборки короткого чтения для геномного секвенирования de novo» . Геномные исследования . 17 (11): 1697–706. DOI : 10.1101 / gr.6435207 . PMC 2045152 . PMID 17908823 .