Бархатный сборщик - Velvet assembler
| Разработчики) | Даниэль Зербино,[1] Юэн Бирни |
|---|---|
| изначальный выпуск | 2008 |
| Стабильный выпуск | 1.2.10 |
| Операционная система | Unix-подобный |
| Доступно в | C |
| Тип | Биоинформатика |
| Лицензия | GPL |
| Интернет сайт | www |
Бархат это пакет алгоритмов, который был разработан для работы с de novo сборка генома и короткое чтение выравнивание секвенирования. Это достигается за счет манипулирования графы де Брейна для сборки геномной последовательности за счет устранения ошибок и упрощения повторяющихся областей.[2] Velvet также был реализован в коммерческих пакетах, таких как Секвенсор, Гениальный, MacVector и BioNumerics.
Вступление
Развитие секвенсоры нового поколения (NGS) позволил повысить рентабельность очень короткого секвенирования чтения. Манипуляции с графиками де Брейна как методом выравнивания стали более реалистичными, но потребовались дальнейшие разработки для решения проблем с ошибками и повторами.[3] Это привело к разработке Velvet Даниэлем Зербино и Юэн Бирни на Европейский институт биоинформатики в Соединенном Королевстве.[4]
Velvet работает, эффективно манипулируя графами де Брейна посредством упрощения и сжатия, без потери информации о графах, путем схождения непересекающихся путей в отдельные узлы. Он устраняет ошибки и устраняет повторы, сначала используя алгоритм исправления ошибок, который объединяет последовательности вместе. Затем повторы удаляются из последовательности с помощью решателя повторов, который разделяет пути, которые имеют локальные перекрытия.
Комбинация коротких считываний и пар чтения позволяет Velvet разрешать небольшие повторы и производить контиги разумной длины. Это приложение Velvet может производить контиги с N50 длина 50 кб на парном конце прокариотический данных и длиной 3 КБ для регионов млекопитающее данные.
Алгоритм
Как уже упоминалось, Velvet использует граф де Брейна для сборки коротких чтений. В частности, Velvet представляет каждый к-мер полученный из считываний уникальным узлом на графе. Два узла соединены, если их k-меры имеют перекрытие k-1. Другими словами, дуга от узла A до узла B существует, если последние k-1 символов k-мер, представленных A, являются первыми k-1 символами k-mer, представленными B. На следующем рисунке показано пример графа де Брейна, созданного с помощью Velvet:
Тот же процесс выполняется одновременно с обратное дополнение всех k-мер, чтобы учесть перекрытия между чтениями противоположных цепей. В графике можно выполнить ряд оптимизаций, включая упрощение и устранение ошибок.
Упрощение
Простой способ сэкономить память - объединить узлы, которые не влияют на путь, созданный в графе, т. Е. Всякий раз, когда узел A имеет только одну исходящую дугу, указывающую на узел B, только с одной входящей дугой, узлы могут быть объединены . Можно представить оба узла как один, объединив их вместе со всей их информацией. Следующий рисунок иллюстрирует этот процесс в упрощении исходного примера.
Удаление ошибки
Ошибки на графике могут быть вызваны процессом секвенирования или просто тем, что биологический образец содержит некоторые ошибки (например, полиморфизмы ). Velvet распознает три вида ошибок: подсказки; пузыри; и ошибочные подключения.
подсказки
Узел считается наконечником и должен быть удален, если он отключен на одном из своих концов, длина информации, хранящейся в узле, меньше 2k, а дуга, ведущая к этому узлу, имеет низкую кратность (во сколько раз больше дуга была найдена при построении графа) и в результате не может быть сравнена с другими альтернативными путями. После устранения этих ошибок график снова подвергается упрощению.
Пузыри
Пузыри образуются, когда два разных пути начинаются и заканчиваются в одних и тех же узлах. Обычно пузыри возникают из-за ошибок или биологических вариантов. Эти ошибки удаляются с помощью алгоритма Tour Bus, который похож на Алгоритм Дейкстры, а поиск в ширину который определяет лучший путь и определяет, какие из них следует стереть. Простой пример показан на рисунке 4.
Этот процесс также показан на рисунке 5 и является продолжением примеров, показанных на рисунках 1 и 2.
Ошибочные подключения
Это соединения, которые не генерируют правильные пути или не создают никаких распознаваемых структур внутри графа. Velvet стирает эти ошибки после завершения алгоритма Tour Bus, применяя простое ограничение покрытия, которое должно быть определено пользователем.
Бархатные команды
Бархат выполняет следующие функции:
- бархат
- Эта команда помогает создать набор данных (хеширует чтение) для velvetg и включает информацию о значении каждого файла последовательности.
- бархат
- Эта команда строит граф де Брейна из k-мер, полученных с помощью velveth, и выполняет упрощение и исправление ошибок по графу. Затем он извлекает контиги.
После запуска velvetg создается ряд файлов. Наиболее важно то, что файл контигов содержит последовательности контигов длиннее 2k, где k - длина слова, используемая в velveth.
Для получения более подробной информации и примеров обратитесь к Velvet Руководство [5]
Мотивация
Существующие технологии секвенирования ДНК, включая NGS, ограничены на том основании, что геномы намного больше любой длины чтения. Как правило, NGS работают с небольшими чтениями, менее 400 бит / с, и имеют гораздо меньшую стоимость чтения, чем предыдущие. машины первого поколения. Они также проще в эксплуатации, имеют более высокий уровень параллельной работы и более высокую производительность.[3]
Однако короткие чтения содержат меньше информации, чем более крупные чтения, поэтому требуется более высокое покрытие сборки для чтения, чтобы обеспечить обнаруживаемые перекрытия. Это, в свою очередь, увеличивает сложность последовательности и значительно увеличивает вычислительные требования. Большее количество чтений также увеличивает размер графа перекрытия, что затрудняет и затягивает вычисления. Связи между чтениями становятся более нечеткими из-за уменьшения перекрывающихся разделов, что приводит к большей вероятности ошибок.
Чтобы преодолеть эти проблемы, были разработаны программы динамического секвенирования, которые являются эффективными, очень экономичными и способны устранять ошибки и повторы. Алгоритмы Velvet были разработаны для этого и могут выполнять выравнивание последовательности короткого чтения de novo за относительно короткое время вычислений и с меньшим использованием памяти по сравнению с другими ассемблерами.[6]
Графический интерфейс
Одним из основных недостатков использования Velvet является использование интерфейса командной строки и трудности, с которыми пользователи, особенно новички, сталкиваются при реализации своих данных. Графический пользовательский интерфейс для ассемблера Velvet был разработан в 2012 году и призван решить эту проблему и упростить работу Velvet.[7].
Смотрите также
Рекомендации
- ^ Зербино, Д. Р. (2010). "Использование Velvetde novo Ассемблер для технологий кратковременного секвенирования ». В Андреас Д. Баксеванис (ред.). Использование ассемблера Velvet de novo для технологий короткого чтения. С. Раздел 11.5. Дои:10.1002 / 0471250953.bi1105s31. ISBN 0471250953. ЧВК 2952100. PMID 20836074.
- ^ Зербино, Д. Р .; Бирни, Э. (2008). «Velvet: сборка de novo с использованием очень коротких чтений». Проверено 18 октября 2013.
- ^ а б Miller, J. R .; Корен, S; Саттон, Г. (2010). «Алгоритмы сборки для данных секвенирования нового поколения». Геномика. 95 (6): 315–27. Дои:10.1016 / j.ygeno.2010.03.001. ЧВК 2874646. PMID 20211242.
- ^ Зербино, Д. Р .; Бирни, Э. (2008). "Velvet: Алгоритмы для сборки короткого чтения de novo с использованием графов де Брейна". Геномные исследования. 18 (5): 821–829. Дои:10.1101 / гр.074492.107. ЧВК 2336801. PMID 18349386.
- ^ «Бархатный мануал» Проверено 18 октября 2013 г.
- ^ Zhang, W .; Chen, J .; Ян, Й .; Tang, Y .; Shang, J .; Шен Б. (2011). «Практическое сравнение программных средств сборки генома De Novo для технологий секвенирования нового поколения». PLoS ONE. 6 (3): e17915. Дои:10.1371 / journal.pone.0017915. ЧВК 3056720. PMID 21423806.
- ^ Пауэлл, Д. Р .; Зееманн, Т. (2013). «VAGUE: графический пользовательский интерфейс для ассемблера Velvet». Биоинформатика. 29 (2): 264–5. Дои:10.1093 / биоинформатика / bts664. PMID 23162059.