Сборка последовательности

редактировать

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

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

Содержание

  • 1 Ассемблеры генома
  • 2 Ассемблеры EST
  • 3 De-novo и сборка карт
  • 4 Влияние технологических изменений
  • 5 Жадный алгоритм
  • 6 Программы
  • 7 См. Также
  • 8 Ссылки

Ассемблеры генома

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

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

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

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

Ассемблеры EST

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

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

De-novo против сборки картирования

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Программы

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

См. Также

Ссылки

Последняя правка сделана 2021-06-07 10:45:30
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте