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