Бархатный сборщик

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-mer, представленными B. На следующем рисунке показано пример графа де Брейна, созданного с помощью Velvet:

Рисунок 1: Пример хеширования чтения и соответствующий граф де Брейна

Тот же процесс выполняется одновременно с обратным дополнением всех 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]

См. Также [ править ]

• Ассемблеры последовательностей de novo
• SPAdes (программное обеспечение)

Ссылки [ править ]