Сборщик бархата
| Разработчик(и) | Дэниел Зербино, [1] Юэн Бирни |
|---|---|
| Первоначальный выпуск | 2008 |
| Стабильный релиз | 1.2.10 |
| Операционная система | Unix-подобный |
| Доступно в | С |
| Тип | Биоинформатика |
| Лицензия | GPL |
| Веб-сайт | www.github.com/dzerbino/velvet/ |
Velvet — это пакет алгоритмов, разработанный для работы со сборкой генома de novo и выравниваниями секвенирования коротких прочтений . Это достигается посредством манипуляции графами де Брейна для сборки геномной последовательности путем удаления ошибок и упрощения повторяющихся областей. [2] Velvet также был реализован в коммерческих пакетах, таких как Sequencher , Geneious , MacVector и BioNumerics .
Введение
Разработка секвенаторов нового поколения (NGS) позволила повысить экономическую эффективность при секвенировании очень коротких прочтений. Манипулирование графами де Брейна как методом выравнивания стало более реалистичным, но для решения проблем с ошибками и повторами потребовались дальнейшие разработки. [3] Это привело к разработке Velvet Дэниелом Зербино и Эваном Бирни в Европейском институте биоинформатики в Соединенном Королевстве. [4]
Velvet работает, эффективно манипулируя графами де Брейна посредством упрощения и сжатия, без потери информации о графе, путем схождения непересекающихся путей в отдельные узлы. Он устраняет ошибки и разрешает повторы, сначала используя алгоритм исправления ошибок, который объединяет последовательности вместе. Затем повторы удаляются из последовательности с помощью решателя повторов, который разделяет пути, которые имеют общие локальные перекрытия.
Комбинация коротких прочтений и пар прочтений позволяет Velvet разрешать небольшие повторы и производить контиги разумной длины. Это приложение Velvet может производить контиги с длиной N50 50 кб на парных конечных прокариотических данных и длиной 3 кб для регионов данных млекопитающих .
Алгоритм
Как уже упоминалось, Velvet использует граф де Брейна для сборки коротких прочтений. Более конкретно, Velvet представляет каждый отдельный k-мер, полученный из прочтений, уникальным узлом на графе. Два узла связаны, если его k-меры имеют k-1 перекрытие. Другими словами, дуга от узла A к узлу B существует, если последние k-1 символов k-мера, представленного A, являются первыми k-1 символами k-мера, представленного B. На следующем рисунке показан пример графа де Брейна, сгенерированного с помощью Velvet:
Тот же процесс одновременно выполняется с обратным дополнением всех k-меров, чтобы учесть перекрытия между прочтениями противоположных цепей. Над графом можно выполнить ряд оптимизаций, включая упрощение и удаление ошибок.
Упрощение
Простой способ сэкономить память — объединить узлы, которые не влияют на путь, сгенерированный в графе, т. е. всякий раз, когда узел A имеет только одну исходящую дугу, которая указывает на узел B, с только одной входящей дугой, узлы могут быть объединены. Можно представить оба узла как один, объединив их и всю их информацию вместе. Следующий рисунок иллюстрирует этот процесс в упрощении исходного примера.
Ошибка удаления
Ошибки в графике могут быть вызваны процессом секвенирования или просто тем, что биологический образец содержит некоторые ошибки (например, полиморфизмы ). Velvet распознает три вида ошибок: кончики; пузыри; и ошибочные соединения.
Советы
Узел считается наконечником и должен быть стерт, если он отключен на одном из своих концов, длина информации, хранящейся в узле, короче 2k, а дуга, ведущая к этому узлу, имеет низкую кратность (количество раз, когда дуга была найдена при построении графа) и, как следствие, не может быть сравнена с другими альтернативными путями. После устранения этих ошибок граф снова подвергается упрощению.
Пузыри
Пузыри образуются, когда два различных пути начинаются и заканчиваются в одних и тех же узлах. Обычно пузыри возникают из-за ошибок или биологических вариантов. Эти ошибки удаляются с помощью алгоритма Tour Bus, который похож на алгоритм Дейкстры , поиск в ширину , который определяет наилучший путь для следования и определяет, какие из них следует стереть. Простой пример показан на рисунке 4.
Этот процесс также показан на рисунке 5, который следует за примерами, показанными на рисунках 1 и 2.
Ошибочные соединения
Это соединения, которые не генерируют правильные пути или не создают никаких узнаваемых структур в графе. Velvet стирает эти ошибки после завершения алгоритма Tour Bus, применяя простое отсечение покрытия, которое должно быть определено пользователем.
Бархатные команды
Velvet предоставляет следующие функции:
- бархатный
- Эта команда помогает создать набор данных (хэширует чтения) для velvetg и включает информацию о значении каждого файла последовательности.
- бархатный
- Эта команда строит граф де Брейна из k-меров, полученных velveth, и выполняет упрощение и исправление ошибок на графе. Затем она извлекает контиги.
После запуска velvetg генерируется ряд файлов. Самое важное, что файл контигов содержит последовательности контигов длиной более 2k, где k — длина слова, используемая в velveth.
Более подробную информацию и примеры см. в руководстве Velvet [5].
Мотивация
Современные технологии секвенирования ДНК, включая NGS, ограничены тем, что геномы намного больше любой длины считывания. Обычно NGS работают с небольшими считываниями, менее 400 п.н., и имеют гораздо более низкую стоимость за считывание, чем предыдущие машины первого поколения . Они также проще в эксплуатации с более высокой параллельной работой и более высокой производительностью. [3]
Однако короткие чтения содержат меньше информации, чем более длинные чтения, поэтому требуется более высокое покрытие чтения сборки, чтобы обеспечить обнаруживаемые перекрытия. Это, в свою очередь, увеличивает сложность секвенирования и значительно увеличивает вычислительные требования. Большее количество чтений также увеличивает размер графа перекрытий, что делает его более сложным и долгим для вычисления. Связи между чтениями становятся более размытыми из-за уменьшения перекрывающихся участков, что приводит к большей вероятности ошибок.
Для преодоления этих проблем были разработаны динамические программы секвенирования, которые эффективны, высокорентабельны и способны устранять ошибки и повторы. Алгоритмы Velvet были разработаны для этого и способны выполнять выравнивание секвенирования de novo с коротким чтением за относительно короткое время вычислений и с меньшим использованием памяти по сравнению с другими ассемблерами. [6]
Графический интерфейс
Одним из главных недостатков использования Velvet является использование интерфейса командной строки и трудности, с которыми сталкиваются пользователи, особенно новички, при внедрении своих данных. Графический пользовательский интерфейс для ассемблера Velvet был разработан в 2012 году и призван преодолеть эту проблему и упростить работу с Velvet. [7]
Смотрите также
Ссылки
- ^ Зербино, DR (2010). «Использование ассемблера Velvetde novo для технологий секвенирования с коротким прочтением». В книге Андреаса Д. Баксеваниса (ред.). Использование ассемблера Velvet de novo для технологий секвенирования с коротким прочтением . Том 31. стр. Раздел 11.5. doi :10.1002/0471250953.bi1105s31. ISBN 978-0471250951. PMC 2952100 . PMID 20836074.
{{cite book}}:|journal=проигнорировано ( помощь ) - ^ Зербино, DR; Бирни, E. (2008). «Velvet: de novo assembly using very short reads». Получено 18 октября 2013 г.
- ^ ab Miller, JR; Koren, S; Sutton, G (2010). «Алгоритмы сборки для данных секвенирования следующего поколения». Genomics . 95 (6): 315–27 . doi :10.1016/j.ygeno.2010.03.001. PMC 2874646 . PMID 20211242.
- ^ Зербино, DR; Бирни, E. (2008). «Velvet: Алгоритмы для сборки коротких прочтений de novo с использованием графов де Брейна». Genome Research . 18 (5): 821– 829. doi :10.1101/gr.074492.107. PMC 2336801. PMID 18349386.
- ^ "Velvet Manual" Получено 18 октября 2013 г.
- ^ Zhang, W.; Chen, J.; Yang, Y.; Tang, Y.; Shang, J.; Shen, B. (2011). "Практическое сравнение программных средств сборки генома De Novo для технологий секвенирования следующего поколения". PLOS ONE . 6 (3): e17915. Bibcode :2011PLoSO...617915Z. doi : 10.1371/journal.pone.0017915 . PMC 3056720 . PMID 21423806.
- ^ Powell, DR; Seemann, T (2013). «VAGUE: графический пользовательский интерфейс для ассемблера Velvet». Биоинформатика . 29 (2): 264– 5. doi : 10.1093/bioinformatics/bts664 . PMID 23162059.
