Ассемблеры последовательностей de novo - это тип программ, которые собирают короткие нуклеотидные последовательности в более длинные без использования эталонного генома . Чаще всего они используются в биоинформатических исследованиях для сборки геномов или транскриптомов . Два распространенных типа ассемблеров de novo - это жадные ассемблеры алгоритмов и ассемблеры графов Де Брёйна .
Типы de novo ассемблеров
Эти ассемблеры обычно используют два типа алгоритмов: жадные , которые стремятся к локальным оптимумам , и алгоритмы методов графов, которые стремятся к глобальным оптимумам . Различные ассемблеры предназначены для конкретных нужд, таких как сборка (малых) бактериальных геномов, (больших) эукариотических геномов или транскриптомов.
Сборщики жадных алгоритмов - это ассемблеры, которые находят локальные оптимумы в выравнивании меньших чтений . Сборщики жадных алгоритмов обычно включают несколько этапов: 1) вычисление попарного расстояния чтений, 2) кластеризация считываний с наибольшим перекрытием, 3) сборка перекрывающихся считываний в более крупные контиги и 4) повторение. Эти алгоритмы обычно плохо работают для больших наборов чтения, поскольку они нелегко достигают глобального оптимума в сборке и плохо работают с наборами чтения, которые содержат повторяющиеся области. [1] Ранние сборщики последовательностей de novo, такие как SEQAID [2] (1984) и CAP [3] (1992), использовали жадные алгоритмы, такие как алгоритмы консенсуса с перекрытием компоновки (OLC). Эти алгоритмы находят перекрытие между всеми чтениями, используют перекрытие для определения макета (или мозаики) чтения, а затем создают согласованную последовательность. В некоторых программах, использующих алгоритмы OLC, предусмотрена фильтрация (для удаления неперекрывающихся пар чтения) и эвристические методы для увеличения скорости анализа.
Ассемблеры графовых методов [4] бывают двух разновидностей: струнные и De Bruijn. Ассемблеры методов графа строк и де Брюйна были представлены на семинаре DIMACS [5] в 1994 году Уотерманом [6] и Джином Майерсом . [7] Эти методы представляют собой важный шаг вперед в сборке последовательностей, поскольку оба они используют алгоритмы для достижения глобального оптимума вместо локального. Хотя оба этих метода позволили улучшить сборку, метод графа Де Брейна стал наиболее популярным в эпоху секвенирования следующего поколения. Во время сборки графа Де Брёйна чтения разбиваются на более мелкие фрагменты заданного размера k. Затем k-меры используются в качестве узлов в сборке графа. Узлы, которые частично перекрываются (обычно k-1), затем соединяются ребром. Затем ассемблер построит последовательности на основе графа Де Брёйна. Ассемблеры графов Де Брёйна обычно лучше работают с большими наборами чтения, чем жадные ассемблеры алгоритмов (особенно когда они содержат повторяющиеся области).
Часто используемые программы
Имя | Описание / Методология | Технологии | Автор | Представлено / Последнее обновление | Лицензия* | Домашняя страница |
---|---|---|---|---|---|---|
Бездна | ассемблер параллельных последовательностей с парными концами, предназначенный для сборки большого генома из коротких чтений (геномных и транскриптомных), использует фильтр Блума для графа Де Брейна | Иллюмина | [8] [9] | 2009/2017 | Операционные системы | ссылка на сайт |
Клонирование AFEAP Lasergene Genomics Suite | точный и эффективный метод сборки больших последовательностей ДНК | два раунда ПЦР с последующим лигированием липких концов фрагментов ДНК | [10] | 2017/2018 | C | ссылка на сайт |
ОТКРОЙТЕ ДЛЯ СЕБЯ Г. | чтения без ПЦР с парным концом (преемник ALLPATHS-LG) | Illumina (MiSeq или HiSeq 2500) | [11] | 2014 г. | Операционные системы | ссылка на сайт |
Сборщик последовательности ДНК-басера | Сборка последовательности ДНК с автоматической обрезкой концов и исправлением неоднозначности. Включает базового вызывающего абонента. | Сэнгер, Иллюмина | Heracle BioSoft SRL | 2018.09 | C (69 долларов США) | NA |
DNASTAR Lasergene Genomics Suite | (большие) геномы, экзомы, транскриптомы, метагеномы, EST | Illumina, ABI SOLiD, Roche 454, Ion Torrent, Solexa, Sanger | ДНАСТАР | 2007/2016 | C | ссылка на сайт |
Newbler | геномы, EST | 454, Зангер | 454 Науки о жизни | 2004/2012 | C | ссылка на сайт |
Phrap | геномы | Сангер, 454, Солекса | Грин, П. | 1994/2008 | C / NC-A | ссылка на сайт |
Plass | Ассемблер на уровне белка: собирает данные секвенирования с трансляцией шести кадров в последовательности белков. | Иллюмина | [12] | 2018/2019 | Операционные системы | ссылка на сайт |
Луч | набор ассемблеров, включая de novo, метагеномное, онтологическое и таксономическое профилирование; использует граф Де Брёйна | [13] | 2010 г. | Операционные системы | ссылка на сайт | |
SPAdes | (малые) геномы, одноклеточные | Illumina, Solexa, Sanger, 454, Ion Torrent, PacBio, Oxford Nanopore | [14] | 2012/2019 | Операционные системы | ссылка на сайт |
Бархат | (маленькие) геномы | Сэнгер, 454, Solexa, СОЛИД | [15] | 2007/2011 | Операционные системы | ссылка на сайт |
HGAP | Геномы до 130 МБ | PacBio читает | [16] | 2011/2015 | Операционные системы | ссылка на сайт |
Сокол | Диплоидные геномы | PacBio читает | [17] | 2014/2017 | Операционные системы | ссылка на сайт |
Можешь | Малые и большие, гаплоидные / диплоидные геномы | PacBio / Oxford Nanopore читает | [18] | 2001/2018 | Операционные системы | ссылка на сайт |
MaSuRCA | Любой размер, гаплоидные / диплоидные геномы | Данные Illumina и PacBio / Oxford Nanopore, данные Legacy 454 и Sanger | [19] | 2011/2018 | Операционные системы | ссылка на сайт |
Петля | Небольшие микробные геномы | PacBio / Oxford Nanopore читает | [20] | 2016/2018 | Операционные системы | ссылка на сайт |
Троица | сборки транскриптомов по графу де Брейна | Illumina RNA-seq | [21] | 2011 г. | ссылка на сайт | |
* Лицензии: OS = Open Source; C = коммерческий; C / NC-A = коммерческий, но бесплатный для некоммерческих и академических кругов |
Разные ассемблеры предназначены для разных типов технологий чтения. Чтения с помощью технологий второго поколения (называемых технологиями короткого чтения), таких как Illumina, обычно короткие (с длиной порядка 50–200 пар оснований) и имеют частоту ошибок около 0,5–2%, причем ошибки в основном связаны с ошибками замещения. Однако чтение из технологий третьего поколения, таких как PacBio, и технологий четвертого поколения, таких как Oxford Nanopore (называемых технологиями длительного чтения), длиннее с длиной считывания, обычно исчисляемой тысячами или десятками тысяч, и имеет гораздо более высокий уровень ошибок - около 10-20% с ошибками, которые в основном вставки и удаления. Это требует различных алгоритмов сборки из технологий короткого и длительного чтения.
Ассемблатон
Существует множество программ для сборки последовательностей de novo, и многие из них сравнивались на Assemblathon. Assemblathon - это периодические совместные усилия по тестированию и улучшению многочисленных доступных ассемблеров. К настоящему времени завершены две сборки (2011 и 2013 гг.), А третья находится в стадии разработки (по состоянию на апрель 2017 г.). Команды исследователей со всего мира выбирают программу и собирают смоделированные геномы (Assemblathon 1) и геномы модельных организмов, которые были предварительно собраны и аннотированы (Assemblathon 2). Затем сборки сравниваются и оцениваются с использованием множества показателей.
Assemblathon 1
Assemblathon 1 [22] проводился в 2011 году и включал 59 собраний от 17 различных групп и организаторов. Целью этого Assembalthon было наиболее точно и полностью собрать геном, состоящий из двух гаплотипов (каждый с тремя хромосомами размером 76,3, 18,5 и 17,7 МБ соответственно), которые были созданы с помощью Evolver. Для оценки сборок использовались многочисленные показатели, в том числе: NG50 (точка, в которой достигается 50% общего размера генома, когда длины каркасов суммируются от самой длинной к самой короткой), LG50 (количество каркасов, которые больше или равны to, длина N50), охват генома и частота ошибок замещения.
- Сравнение программ: ABySS, Phusion2, phrap, Velvet, SOAPdenovo, PRICE, ALLPATHS-LG
- Анализ N50: сборки, произведенные группой сборки генома растений (с использованием ассемблера Meraculous) и ALLPATHS, Broad Institute, США (с использованием ALLPATHS-LG), показали лучшие результаты в этой категории, на порядок по сравнению с другими группами. Эти сборки набрали N50> 8 000 000 баз.
- Покрытие генома сборкой: для этого показателя сборка BGI с помощью SOAPdenovo показала наилучшие результаты, покрывая 98,8% всего генома. Все сборщики показали относительно хорошие результаты в этой категории, при этом все группы, кроме трех, имели охват 90% и выше, а наименьшее общее покрытие составляло 78,5% (Департамент компьютерных наук, Чикагский университет, США через Kiki).
- Ошибки замены: сборка с наименьшим количеством ошибок замены была представлена британской командой Wellcome Trust Sanger Institute с использованием программного обеспечения SGA.
- В целом: ни один ассемблер не работал значительно лучше других во всех категориях. В то время как некоторые ассемблеры преуспели в одной категории, они не преуспели в других, что говорит о том, что есть еще много возможностей для улучшения качества программного обеспечения ассемблера.
Ассемблатон 2
Assemblathon 2 [23] улучшил Assemblathon 1 за счет включения геномов нескольких позвоночных (птицы ( Melopsittacus undulatus ), рыбы ( Maylandia zebra ) и змеи ( Boa constrictor constrictor )), геномы которых оцениваются в 1,2, 1,0 и 1.6Gbp в длину) и оценка по более чем 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) оценить уровни гетерозиготности в интересующем геноме.
Смотрите также
- Последовательная сборка
- Выравнивание последовательности
- Сборка транскриптомов de novo
Рекомендации
- ^ Дж. Банг-Дженсен; Г. Гутин; А. Йео (2004). «Когда жадный алгоритм дает сбой». Дискретная оптимизация . 1 (2): 121–127. DOI : 10.1016 / j.disopt.2004.03.007 .
- ^ Пелтола, Ханну; Седерлунд, Ганс; Укконен, Эско (11 января 1984). «SEQAID: программа сборки последовательности ДНК на основе математической модели» . Исследования нуклеиновых кислот . 12 (1Part1): 307–321. DOI : 10.1093 / NAR / 12.1Part1.307 . ISSN 0305-1048 . PMC 321006 . PMID 6320092 .
- ^ Хуан Сяоцю (01.09.1992). «Программа сборки контигов, основанная на чувствительном обнаружении перекрытий фрагментов». Геномика . 14 (1): 18–25. DOI : 10.1016 / S0888-7543 (05) 80277-0 . PMID 1427824 .
- ^ Компо, Филипп ЕС, Павел А. Певзнер и Гленн Теслер (2011). «Как применить графики де Брейна к сборке генома» . Природа Биотехнологии . 29 (11): 987–991. DOI : 10.1038 / nbt.2023 . PMC 5531759 . PMID 22068540 .CS1 maint: использует параметр авторов ( ссылка )
- ^ "Семинар DIMACS по комбинаторным методам картирования и секвенирования ДНК" . Октябрь 1994 г.
- ^ Идури, РМ; Уотерман, MS (1995-01-01). «Новый алгоритм сборки последовательности ДНК». Журнал вычислительной биологии . 2 (2): 291–306. CiteSeerX 10.1.1.79.6459 . DOI : 10,1089 / cmb.1995.2.291 . ISSN 1066-5277 . PMID 7497130 .
- ^ Майерс, EW (1995-01-01). «К упрощению и точной постановке сборки фрагментов». Журнал вычислительной биологии . 2 (2): 275–290. DOI : 10,1089 / cmb.1995.2.275 . ISSN 1066-5277 . PMID 7497129 .
- ^ Симпсон, Джаред Т .; и другие. (2009). «ABySS: параллельный ассемблер для данных короткой последовательности чтения» . Геномные исследования . 19 (6): 1117–1123. DOI : 10.1101 / gr.089532.108 . PMC 2694472 . PMID 19251739 .
- ^ Бирол, Инанс; и другие. (2009). «Сборка транскриптомов De novo с ABySS» . Биоинформатика . 25 (21): 2872–2877. DOI : 10.1093 / биоинформатики / btp367 . PMID 19528083 .
- ^ Цзэн, Фанли; Занг, Цзиньпин; Чжан, Сухуа; Хао, Чжимин; Донг, Цзингао; Линь, Ибинь (2017-11-14). «Клонирование AFEAP: точный и эффективный метод сборки больших последовательностей ДНК» . BMC Biotechnology . 17 (1): 81. DOI : 10,1186 / s12896-017-0394-х . ISSN 1472-6750 . PMC 5686892 . PMID 29137618 .
- ^ Любовь, Р. Ребекка; Weisenfeld, Neil I .; Джефф, Дэвид Б .; Бесанский, Нора Дж .; Нефси, Дэниел Э. (декабрь 2016 г.). «Оценка DISCOVAR de novo с использованием образца комаров для рентабельной сборки генома с коротким считыванием» . BMC Genomics . 17 (1): 187. DOI : 10,1186 / s12864-016-2531-7 . ISSN 1471-2164 . PMC 4779211 . PMID 26944054 .
- ^ Штейнеггер, Мартин; Мирдита, Милот; Сёдинг, Йоханнес (24.06.2019). «Сборка на уровне белка многократно увеличивает восстановление белковой последовательности из метагеномных образцов» . Методы природы . 16 (7): 603–606. DOI : 10.1038 / s41592-019-0437-4 . hdl : 21.11116 / 0000-0003-E0DD-7 . PMID 31235882 .
- ^ Буазвер, Себастьен, Франсуа Лавиолетт и Жак Корбей (2010). «Луч: одновременная сборка чтений из смеси высокопроизводительных технологий секвенирования» . Журнал вычислительной биологии . 17 (11): 1519–1533. DOI : 10,1089 / cmb.2009.0238 . PMC 3119603 . PMID 20958248 .CS1 maint: использует параметр авторов ( ссылка )
- ^ Банкевич, Антон; Нурк, Сергей; Антипов Дмитрий; Гуревич, Алексей А .; Дворкин Михаил; Куликов, Александр С .; Лесин Валерий М .; Николенко, Сергей И .; Фам, сын; Пржибельский, Андрей Д .; Пышкин, Алексей В. (май 2012). «SPAdes: новый алгоритм сборки генома и его приложения для секвенирования отдельных клеток» . Журнал вычислительной биологии . 19 (5): 455–477. DOI : 10,1089 / cmb.2012.0021 . ISSN 1066-5277 . PMC 3342519 . PMID 22506599 .
- ^ Зербино, ДР; Бирни, Э. (21 февраля 2008 г.). "Velvet: Алгоритмы для сборки короткого чтения de novo с использованием графов де Брейна" . Геномные исследования . 18 (5): 821–829. DOI : 10.1101 / gr.074492.107 . ISSN 1088-9051 . PMC 2336801 . PMID 18349386 .
- ^ Чин, Чен-Шань, Дэвид Х. Александр, Патрик Маркс, Аарон А. Кламмер, Джеймс Дрейк, Шерил Хайнер, Алисия Клам и др. «Негибридные, готовые сборки микробного генома на основе данных секвенирования SMRT с длительным считыванием». Природные методы 10, вып. 6 (2013): 563-569. Доступно онлайн
- ^ Чин, Чен-Шань, Пол Пелузо, Фриц Дж. Седлазек, Мария Наттестад, Грегори Т. Консепсьон, Алисия Клам, Кристофер Данн и др. «Поэтапная диплоидная сборка генома с секвенированием одной молекулы в реальном времени». Природные методы 13, вып. 12 (2016): 1050-1054. Доступна здесь
- ^ Корен, Сергей, Брайан П. Валенц, Константин Берлин, Джейсон Р. Миллер, Николас Х. Бергман и Адам М. Филлиппи. «Canu: масштабируемая и точная сборка с длинным считыванием за счет адаптивного взвешивания k-mer и разделения повторов». Геномные исследования 27, вып. 5 (2017): 722-736. Доступна здесь
- ^ Зимин, Алексей В .; Марсе, Гийом; Пуйу, Даниэла; Робертс, Майкл; Зальцберг, Стивен Л .; Йорк, Джеймс А. (ноябрь 2013 г.). «Сборщик генома MaSuRCA» . Биоинформатика . 29 (21): 2669–2677. DOI : 10.1093 / биоинформатики / btt476 . ISSN 1367-4803 . PMC 3799473 . PMID 23990416 .
- ^ Kamath, Говинд М., Илан Shomorony, Фэй Ся, Томас А. Courtade и Н. Ца Дэвид. «ПЕТЛЯ: сборка с длинным считыванием обеспечивает оптимальное разрешение повторов». Геномные исследования 27, вып. 5 (2017): 747-756. Доступна здесь
- ^ Grabherr, Manfred G .; и другие. (2011). «Сборка транскриптома полной длины из данных RNA-Seq без эталонного генома» . Природа Биотехнологии . 29 (7): 644–652. DOI : 10.1038 / nbt.1883 . PMC 3571712 . PMID 21572440 .
- ^ Эрл, Дент; и другие. (2011). «Assemblathon 1: конкурентная оценка методов сборки de novo short read» . Геномные исследования . 21 (12): 2224–2241. DOI : 10.1186 / 2047-217X-2-10 . PMC 3844414 . PMID 23870653 .
- ^ Bradnam, Keith R .; и другие. (2013). «Assemblathon 2: оценка de novo методов сборки генома у трех видов позвоночных» . GigaScience . 2 (1): 10. arXiv : 1301.5406 . DOI : 10.1186 / 2047-217X-2-10 . PMC 3844414 . PMID 23870653 .