Jump to content

Опять ассемблеры последовательностей

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

Типы ассемблеров de novo

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

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

Сборщики жадных алгоритмов — это ассемблеры, которые находят локальные оптимумы при выравнивании меньших операций чтения . Сборщики жадных алгоритмов обычно состоят из нескольких этапов: 1) попарный расчет расстояний чтений, 2) кластеризация чтений с наибольшим перекрытием, 3) сборка перекрывающихся чтений в более крупные контиги и 4) повторение. Эти алгоритмы обычно плохо работают для больших наборов чтения, поскольку им нелегко достичь глобального оптимума в сборке, и они плохо работают с наборами чтения, содержащими повторяющиеся области. [ 1 ] Ранние ассемблеры последовательностей de novo, такие как SEQAID. [ 2 ] (1984) и КАП [ 3 ] (1992) использовали жадные алгоритмы, такие как алгоритмы консенсуса по компоновке перекрытия (OLC). Эти алгоритмы находят перекрытие между всеми операциями чтения, используют это перекрытие для определения расположения (или мозаики) операций чтения, а затем создают согласованную последовательность. Некоторые программы, использующие алгоритмы OLC, включали фильтрацию (для удаления пар чтения, которые не перекрываются) и эвристические методы для увеличения скорости анализа.

Ассемблеры графовых методов [ 4 ] бывают двух разновидностей: струнные и Де Брейна. строковых графов и графов Де Брёйна . были представлены ассемблеры метода На выставке DIMACS [ 5 ] в 1994 году мастер-класс Уотермана [ 6 ] и Джин Майерс . [ 7 ] Эти методы представляют собой важный шаг вперед в сборке последовательностей, поскольку оба они используют алгоритмы для достижения глобального оптимума, а не локального оптимума. Хотя оба эти метода позволили улучшить сборку, метод графов Де Брёйна стал самым популярным в эпоху секвенирования следующего поколения. Во время сборки графа Де Брейна чтения разбиваются на более мелкие фрагменты заданного размера k. Затем k -меры используются в качестве ребер в сборке графа. Узлы строятся как (k-1)-меры, соединяющиеся ребром. Затем ассемблер создаст последовательности на основе графа Де Брёйна. Ассемблеры графов Де Брёйна обычно работают лучше на больших наборах считываний, чем ассемблеры жадных алгоритмов (особенно когда они содержат повторяющиеся области).

Часто используемые программы

[ редактировать ]
Список ассемблеров de novo
Имя Описание /

Методология

Технологии Автор Представлено /

Последнее обновление

Лицензия* Домашняя страница
АБиСС параллельный ассемблер последовательностей с парными концами, предназначенный для сборки больших геномов коротких ридов (геномных и транскриптомных), использует фильтр Блума для графа Де Брейна Иллюмина [ 8 ] [ 9 ] 2009 / 2017 ТЫ связь
Пение Маленькие и большие гаплоидные/диплоидные геномы PacBio/Oxford Nanopore читает [ 10 ] 2001 / 2018 ТЫ связь
ДИСКОВАР чтение без ПЦР с парными концами (преемник ALLPATHS-LG) Illumina (MiSeq или HiSeq 2500) [ 11 ] 2014 ТЫ связь
Ассемблер базовых последовательностей ДНК Сборка последовательности ДНК с автоматической обрезкой концов и коррекцией неоднозначности. Включает базовый абонент. Сэнгер, Иллюмина Геракл Биософт ООО 2018.09 С (69 долларов США) ЧТО
ДНКСТАР Лазергенная Геномика Большие геномы, экзомы, транскриптомы, метагеномы, EST. Также de novo сборка и доработка данных секвенирования длинных считываний из Oxford Nanopore и PacBio, включая считывания PacBio Hifi. Illumina, ABI SOLiD, Roche 454, Ion Torrent, Solexa, Sanger ДНКСТАР 2007 / 2023 С связь
Сокол Диплоидные геномы PacBio читает [ 12 ] 2014 / 2017 ТЫ связь
Флай геномы и метагеномы. Использует повторяющиеся графики PacBio/Oxford Nanopore читает [ 13 ] 2018/2023 ТЫ связь
HGAP Геномы до 130 МБ PacBio читает [ 14 ] 2011 / 2015 ТЫ связь
хифиазм Сборка графа PacBio HiFi читает [ 15 ] 2021 ТЫ связь
Петля Маленькие микробные геномы PacBio/Oxford Nanopore читает [ 16 ] 2016 / 2018 ТЫ связь
МаСуРКА Любой размер, гаплоидные/диплоидные геномы Данные Illumina и PacBio/Oxford Nanopore, устаревшие данные 454 и данные Sanger [ 17 ] 2011 / 2018 ТЫ связь
Ньюблер геномы, EST 454, Сангер 454 Науки о жизни 2004/2012 С связь
Фрап геномы Зингер, 454 года, Солекса Грин, П. 1994 / 2008 С/НК-А связь
Комната Ассемблер на уровне белка: собирает считывания транслированной последовательности с шестью рамками в белковые последовательности. Иллюмина [ 18 ] 2018 / 2019 ТЫ связь
Рэй набор ассемблеров, включая de novo, метагеномное, онтологическое и таксономическое профилирование; использует график Де Брейна [ 19 ] 2010 ТЫ связь
ЛОПАТЫ (маленькие) геномы, одноклеточные Illumina, Solexa, Sanger, 454, Ion Torrent, PacBio, Oxford Nanopore. [ 20 ] 2012 / 2021 ТЫ связь
Троица сборки транскриптома по графу де Брёйна Illumina RNA-seq [ 21 ] 2011 связь
бархат (маленькие) геномы Сэнгер, 454, Солекса, SOLiD [ 22 ] 2007 / 2011 ТЫ связь
* Лицензии: ОС = открытый исходный код; С = Коммерческий; C / NC-A = коммерческая, но бесплатная для некоммерческих и научных кругов.

Различные ассемблеры предназначены для разных типов технологий чтения. Считывания с помощью технологий второго поколения (так называемых технологий короткого чтения), таких как Illumina, обычно короткие (с длиной порядка 50–200 пар оснований) и имеют частоту ошибок около 0,5–2%, причем ошибки в основном представляют собой ошибки замены. Однако операции чтения с использованием технологий третьего поколения, таких как PacBio, и технологий четвертого поколения, таких как Oxford Nanopore (так называемые технологии длительного чтения), длиннее, а длина чтения обычно исчисляется тысячами или десятками тысяч, и имеют гораздо более высокий уровень ошибок, составляющий около 10–20%, при этом ошибки главным образом вставки и удаления. Это требует разных алгоритмов сборки для технологий короткого и длинного чтения.

ассамблеятон

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

Существует множество программ для сборки последовательностей de novo, и многие из них сравнивались на Assemblathon. Assemblathon — это периодические совместные усилия по тестированию и улучшению многочисленных доступных ассемблеров. На данный момент завершены две сборки (2011 и 2013 гг.), а третья находится в стадии реализации (по состоянию на апрель 2017 г.). Команды исследователей со всего мира выбирают программу и собирают смоделированные геномы (Ассамблея 1) и геномы модельных организмов, которые были предварительно собраны и аннотированы (Ассамблея 2). Затем сборки сравниваются и оцениваются с использованием многочисленных показателей.

Ассамблея 1

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

Ассамблея 1 [ 23 ] был проведен в 2011 году и в нем приняли участие 59 собраний от 17 различных групп и организаторов. Целью этого Ассамбалтона было максимально точно и полно собрать геном, состоящий из двух гаплотипов (каждый с тремя хромосомами по 76,3, 18,5 и 17,7 Мб соответственно), сгенерированный с помощью Эволвера. Для оценки сборок использовались многочисленные метрики, в том числе: NG50 (точка, в которой достигается 50% общего размера генома при суммировании длин каркасов от самой длинной к самой короткой), LG50 (количество каркасов, которые больше или равны to, длина N50), покрытие генома и частота ошибок замены.

  • Сравниваемое программное обеспечение: ABySS, Phusion2, Phrap, Velvet, SOAPdenovo, PRICE, ALLPATHS-LG.
  • Анализ N50: сборки Plant Genome Assembly Group (с использованием ассемблера Meraculous) и ALLPATHS, Broad Institute, США (с использованием ALLPATHS-LG) показали лучшие результаты в этой категории, на порядок превосходя другие группы. Эти сборки получили N50 из >8 000 000 оснований.
  • Охват генома сборкой: по этому показателю сборка BGI через SOAPdenovo показала лучшие результаты: было охвачено 98,8% всего генома. Все ассемблеры показали относительно хорошие результаты в этой категории: все группы, кроме трех, имели охват 90% и выше, а самый низкий общий охват составил 78,5% (Кафедра компьютерных наук, Чикагский университет, США, через Kiki).
  • Ошибки замены: сборка с наименьшим уровнем ошибок замены была предоставлена ​​командой Wellcome Trust Sanger Institute, Великобритания, с использованием программного обеспечения SGA.
  • В целом: ни один ассемблер не показал значительно лучших результатов у других во всех категориях. Хотя некоторые ассемблеры преуспели в одной категории, но не в других, это позволяет предположить, что еще есть много возможностей для улучшения качества ассемблерного программного обеспечения.

Сборка 2 [ 24 ] улучшена версия Assemblathon 1 за счет включения геномов нескольких позвоночных (птицы ( Melopsittacus undulatus ), рыбы ( Maylandia zebra ) и змеи ( Boa constrictor constrictor )) с геномами, длина которых оценивается в 1,2, 1,0 и 1,6 Гбит/с) и оценка по более чем 100 метрикам. Каждой команде было дано четыре месяца на сбор своего генома на основе данных секвенирования следующего поколения (NGS), включая Illumina и Roche 454 данные последовательностей .

  • Сравниваемое программное обеспечение: ABySS, ALLPATHS-LG, PRICE, Ray и SOAPdenovo.
  • Анализ N50: при сборке генома птицы Центр секвенирования генома человека Медицинского колледжа Бэйлора и команды ALLPATHS имели самые высокие значения NG50 - более 16 000 000 и более 14 000 000 пар оснований соответственно.
  • Наличие основных генов: большинство сборок показали хорошие результаты в этой категории (~ 80% или выше), и только в одной сборке птичьего генома доля упала до чуть более 50% (Университет штата Уэйн через HyDA).
  • В целом: В целом, Центр секвенирования генома человека Медицинского колледжа Бэйлора использует различные методы сборки (SeqPrep, KmerFreq, Quake, BWA, Newbler, ALLPATHS-LG, Atlas-Link, Atlas-GapFill, Phrap, CrossMatch, Velvet, BLAST, и BLASR) показали лучшие результаты для групп птиц и рыб. Для сборки генома змеи наилучшие результаты показал Институт Wellcome Trust Sanger, использующий SGA. Для всех сборок SGA, BCM, Meraculous и Ray представили конкурсные сборки и оценки. Результаты многочисленных сборок и оценок, описанных здесь, показывают, что, хотя один ассемблер может хорошо работать с одним видом, он может не так хорошо работать с другим. Авторы делают несколько предложений по сборке: 1) использовать более одного ассемблера, 2) использовать более одной метрики для оценки, 3) выбирать ассемблер, который превосходит другие показатели, представляющие больший интерес (например, N50, покрытие), 4) низкие N50. или размеры сборки могут не иметь значения, в зависимости от потребностей пользователя, и 5) оценить уровни гетерозиготности в интересующем геноме.

См. также

[ редактировать ]
  1. ^ Дж. Банг-Дженсен; Г. Гутин; А. Йео (2004). «Когда жадный алгоритм дает сбой» . Дискретная оптимизация . 1 (2): 121–127. дои : 10.1016/j.disopt.2004.03.007 .
  2. ^ Пелтола, Ханну; Содерлунд, Ганс; Укконен, Эско (11 января 1984 г.). «SEQAID: программа сборки последовательностей ДНК, основанная на математической модели» . Исследования нуклеиновых кислот . 12 (1Часть 1): 307–321. дои : 10.1093/нар/12.1Part1.307 . ISSN   0305-1048 . ПМК   321006 . ПМИД   6320092 .
  3. ^ Хуан, Сяоцю (1 сентября 1992 г.). «Программа сборки контигов, основанная на чувствительном обнаружении перекрытий фрагментов». Геномика . 14 (1): 18–25. дои : 10.1016/S0888-7543(05)80277-0 . ПМИД   1427824 .
  4. ^ Компо, Филипп EC; Павел Алексеевич Певзнер; Гленн Теслер (2011). «Как применять графы де Брёйна для сборки генома» . Природная биотехнология . 29 (11): 987–991. дои : 10.1038/nbt.2023 . ПМЦ   5531759 . ПМИД   22068540 .
  5. ^ «Семинар DIMACS по комбинаторным методам картирования и секвенирования ДНК» . Октябрь 1994 года.
  6. ^ Идури, РМ; Уотерман, MS (1 января 1995 г.). «Новый алгоритм сборки последовательности ДНК». Журнал вычислительной биологии . 2 (2): 291–306. CiteSeerX   10.1.1.79.6459 . дои : 10.1089/cmb.1995.2.291 . ISSN   1066-5277 . ПМИД   7497130 .
  7. ^ Майерс, EW (1 января 1995 г.). «К упрощению и точной формулировке сборки фрагментов». Журнал вычислительной биологии . 2 (2): 275–290. дои : 10.1089/cmb.1995.2.275 . ISSN   1066-5277 . ПМИД   7497129 .
  8. ^ Симпсон, Джаред Т.; и др. (2009). «ABySS: параллельный ассемблер для данных последовательности короткого чтения» . Геномные исследования . 19 (6): 1117–1123. дои : 10.1101/гр.089532.108 . ПМЦ   2694472 . ПМИД   19251739 .
  9. ^ Бироль, Инанч; и др. (2009). «Сборка транскриптома de novo с ABySS» . Биоинформатика . 25 (21): 2872–2877. doi : 10.1093/биоинформатика/btp367 . ПМИД   19528083 .
  10. ^ Корен, Сергей, Брайан П. Валенц, Константин Берлин, Джейсон Р. Миллер, Николас Х. Бергман и Адам М. Филлиппи. «Кану: масштабируемая и точная сборка длинных чтений посредством адаптивного взвешивания k-меров и разделения повторов». Геномные исследования 27, вып. 5 (2017): 722-736. Доступно здесь
  11. ^ С любовью, Р. Ребекка; Вайзенфельд, Нил И.; Яффе, Дэвид Б.; Безански, Нора Дж .; Нифси, Дэниел Э. (декабрь 2016 г.). «Оценка DISCOVAR de novo с использованием образца комара для экономичной сборки генома с коротким считыванием» . БМК Геномика . 17 (1): 187. дои : 10.1186/s12864-016-2531-7 . ISSN   1471-2164 . ПМЦ   4779211 . ПМИД   26944054 .
  12. ^ Чин, Чен-Шан, Пол Пелузо, Фриц Дж. Седлазек, Мария Наттестад, Грегори Т. Консепсьон, Алисия Клам, Кристофер Данн и др. «Поэтапная сборка диплоидного генома с секвенированием одиночных молекул в реальном времени». Природные методы 13, вып. 12 (2016): 1050-1054. Доступно здесь
  13. ^ Колмогоров Михаил; Юань, Джеффри; Лин, Ю; Певзнер, Павел А. (01.04.2019). «Сборка длинных, подверженных ошибкам операций чтения с использованием повторяющихся графов» (PDF) . Природная биотехнология . 37 (5): 540–546. дои : 10.1038/s41587-019-0072-8 . ISSN   1087-0156 . ПМИД   30936562 . S2CID   89616540 .
  14. ^ Чин, Чен-Шан, Дэвид Х. Александр, Патрик Маркс, Аарон А. Кламмер, Джеймс Дрейк, Шерил Хайнер, Алисия Клам и др. «Негибридные готовые сборки микробного генома на основе давно считанных данных секвенирования SMRT». Природные методы 10, вып. 6 (2013): 563-569. Доступно онлайн
  15. ^ Ченг, Хаоюй; Консепсьон, Грегори Т.; Фэн, Сяовэнь; Чжан, Хаовэнь; Ли, Хэн (февраль 2021 г.). «Сборка de novo с разрешением гаплотипа с использованием графов поэтапной сборки с хифиазмом» . Природные методы . 18 (2): 170–175. arXiv : 2008.01237 . дои : 10.1038/s41592-020-01056-5 . ISSN   1548-7105 . ПМЦ   7961889 . ПМИД   33526886 .
  16. ^ Камат, Говинда М., Илан Шоморони, Фей Ся, Томас А. Куртейд и Н. Це Дэвид. «ШАРНИР: сборка длительного чтения обеспечивает оптимальное разрешение повтора». Геномные исследования 27, вып. 5 (2017): 747-756. Доступно здесь
  17. ^ Зимин, Алексей В.; Маркэ, Гийом; Пуйу, Даниэла; Робертс, Майкл; Зальцберг, Стивен Л.; Йорк, Джеймс А. (ноябрь 2013 г.). «Ассемблер генома MaSuRCA» . Биоинформатика . 29 (21): 2669–2677. doi : 10.1093/биоинформатика/btt476 . ISSN   1367-4803 . ПМЦ   3799473 . ПМИД   23990416 .
  18. ^ Штайнеггер, Мартин; Мирдита, Милот; Сёдинг, Йоханнес (24 июня 2019 г.). «Сборка на уровне белка многократно увеличивает восстановление последовательности белка из метагеномных образцов» (PDF) . Природные методы . 16 (7): 603–606. дои : 10.1038/s41592-019-0437-4 . hdl : 21.11116/0000-0003-E0DD-7 . ПМИД   31235882 .
  19. ^ Буасвер, Себастьен; Франсуа Лавиолетт; Жак Корбей (2010). «Рэй: одновременная сборка ридов из сочетания технологий высокопроизводительного секвенирования» . Журнал вычислительной биологии . 17 (11): 1519–1533. дои : 10.1089/cmb.2009.0238 . ПМК   3119603 . ПМИД   20958248 .
  20. ^ Банкевич, Антон; Нурк, Сергей; Антипов Дмитрий; Гуревич Алексей А.; Дворкин Михаил; Куликов, Александр С.; Лесин Валерий Михайлович; Николенко Сергей Иванович; Фам, Сон; Пржибельский, Андрей Д.; Пышкин, Алексей В. (май 2012 г.). «SPAdes: новый алгоритм сборки генома и его применение к секвенированию одиночных клеток» . Журнал вычислительной биологии . 19 (5): 455–477. дои : 10.1089/cmb.2012.0021 . ISSN   1066-5277 . ПМЦ   3342519 . ПМИД   22506599 .
  21. ^ Грабхерр, Манфред Г.; и др. (2011). «Сборка полноразмерного транскриптома на основе данных RNA-Seq без эталонного генома» . Природная биотехнология . 29 (7): 644–652. дои : 10.1038/nbt.1883 . ПМЦ   3571712 . ПМИД   21572440 .
  22. ^ Зербино, ДР; Бирни, Э. (21 февраля 2008 г.). «Бархат: Алгоритмы сборки короткого чтения de novo с использованием графов де Брёйна» . Геномные исследования . 18 (5): 821–829. дои : 10.1101/гр.074492.107 . ISSN   1088-9051 . ПМК   2336801 . ПМИД   18349386 .
  23. ^ Эрл, Дент; и др. (декабрь 2011 г.). «Ассамблея 1: Конкурсная оценка методов сборки короткого чтения de novo» . Геномные исследования . 21 (12): 2224–2241. дои : 10.1101/гр.126599.111 . ПМК   3227110 . ПМИД   21926179 .
  24. ^ Брэднэм, Кейт Р.; и др. (2013). «Сборка 2: оценка методов сборки генома de novo у трех видов позвоночных» . ГигаСайенс . 2 (1): 10. arXiv : 1301.5406 . дои : 10.1186/2047-217X-2-10 . ПМЦ   3844414 . ПМИД   23870653 .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 05411d2ba3269efafaa530654eaaeed4__1720426080
URL1:https://arc.ask3.ru/arc/aa/05/d4/05411d2ba3269efafaa530654eaaeed4.html
Заголовок, (Title) документа по адресу, URL1:
De novo sequence assemblers - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)