Сборщик бархата
| Разработчик(и) | Даниэль Зербино, [1] Я не знаю Бирни |
|---|---|
| Первоначальный выпуск | 2008 |
| Стабильная версия | 1.2.10 |
| Операционная система | Unix-подобный |
| Доступно в | С |
| Тип | Биоинформатика |
| Лицензия | лицензия GPL |
| Веб-сайт | www |
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]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Зербино, ДР (2010). Velvetde novo «Использование ассемблера для технологий секвенирования короткого чтения». Андреас Д. Баксеванис (ред.). Использование ассемблера Velvet de novo для технологий секвенирования короткого чтения . Том. 31. С. Раздел 11.5. дои : 10.1002/0471250953.bi1105s31 . ISBN 978-0471250951 . ПМК 2952100 . ПМИД 20836074 .
{{cite book}}:|journal=игнорируется ( помогите ) - ^ Зербино, ДР; Бирни, Э. (2008). «Бархат: сборка de novo с использованием очень коротких операций чтения» . Проверено 18 октября 2013 г.
- ^ Jump up to: а б Миллер-младший; Корен, С; Саттон, Дж. (2010). «Алгоритмы сборки данных секвенирования нового поколения» . Геномика . 95 (6): 315–27. дои : 10.1016/j.ygeno.2010.03.001 . ПМЦ 2874646 . ПМИД 20211242 .
- ^ Зербино, ДР; Бирни, Э. (2008). «Бархат: Алгоритмы сборки короткого чтения de novo с использованием графов де Брёйна» . Геномные исследования . 18 (5): 821–829. дои : 10.1101/гр.074492.107 . ПМК 2336801 . ПМИД 18349386 .
- ^ "Бархатное руководство" Проверено 18 октября 2013 г.
- ^ Чжан, В.; Чен, Дж.; Ян, Ю.; Тан, Ю.; Шан, Дж.; Шен, Б. (2011). «Практическое сравнение программных средств сборки генома De Novo для технологий секвенирования следующего поколения» . ПЛОС ОДИН . 6 (3): e17915. Бибкод : 2011PLoSO...617915Z . дои : 10.1371/journal.pone.0017915 . ПМК 3056720 . ПМИД 21423806 .
- ^ Пауэлл, доктор медицинских наук; Зееманн, Т (2013). «VAGUE: графический интерфейс пользователя для ассемблера Velvet» . Биоинформатика . 29 (2): 264–5. doi : 10.1093/биоинформатика/bts664 . ПМИД 23162059 .