Фреймворк для сборки генома с помощью графа перекрытий, графа де Брюйна с использованием ML-компоненты

Контекст задачи.

ДНК можно представить как обычную строку, состоящую из четырех символов: A, C, G и T — это алфавит, кодирующий генетическую информацию. Современные биологические приборы — секвенаторы — не считывают всю строку целиком. Они «разрывают» её на короткие фрагменты — риды — длиной 50–150 символов, и задача биоинформатики — восстановить исходную последовательность по этим кусочкам, это называется сборкой генома. В результате получается набор контигов — неперекрывающихся длинных последовательностей.

Постановка задачи

Математическая постановка задачи: пусть имеется набор ридов где каждый рид строка над алфавитом {A,C,G,T}, причем для некоторых пар ридов выполняется условие перекрытия — суффикс одной строки совпадает с префиксом другой строки. Необходимо по перекрытиям восстановить полную последовательность. Наиболее подходящее решение заключается в использовании графов.

Графовые подходы

Граф перекрытий представляет собой структуру, где в качестве вершин выступают сами риды, а дуга между двумя вершинами ставится, если риды перекрываются. В таком случае, решение задачи сводится к поиску гамильтонова пути.

Более выгодной структурой является граф де Брюйна, дугами которого являются k-меры, то есть каждый рид разбивается на подстроки длины k, а вершины графа - (k-1)-меры. Дуги выходят из одной вершины, если они перекрываются на (k-1)-мер. В таком случае, задача сводится к поиску эйлерова пути в графе.

Данные

В качестве данных был выбран геном организма Salmonella enterica, поскольку является одним из наиболее изученных организмов. Длина генома составляет около 4.8 млн.п.н., количество ридов — 2.8 млн. штук, средняя длина ридов 92 п.н..

Сравнение готовых сборщиков

Были протестированы три популярных ассемблера: Abyss, SPAdes и Velvet.

• Abyss показал наименьшее количество ошибок, но при этом сборка получилась сильно фрагментированной — то есть много коротких кусочков.
• SPAdes и Velvet собирают более длинные участки, но ошибаются чаще.

Граф перекрытий

• Граф перекрытий — подходит для длинных ридов и дает более точную, но дорогую по ресурсам сборку. Используется реже из-за сложности.

Граф чаще используют для сборки “длинных” ридов (от 10 тыс.п.н.), поэтому для демонстрации работы графа были извлечены фрагменты нужной длины непосредственно из референсного генома.

Граф де Брюйна. Выбор k

• Граф де Брюйна — основан на разбиении ридов на короткие подстроки фиксированной длины. Он быстрее и масштабируемее, но требует точной настройки параметра длины подстрок (k).

Для коротких ридов длины 80-90 п.н. принято выбирать k равное 61-71. С целью подобрать оптимальное значение k, было осуществлено несколько запусков с различными значениями параметра на небольшом количестве данных (100000 ридов). Можно заметить, как при увеличении числа k уменьшается количество вершин и ребер графа, что закономерно, так как уменьшается общее число уникальных k-меров данной длины, вследствие чего для больших k меньше ребер и вершин после упрощения. Однако, напротив, увеличивается число контигов после сборки - это происходит потому, что при меньшем числе ребер получается больше компонент связности, а каждая компонента отражает отдельный контиг.

Внедрение машинного обучения.

Чтобы улучшить качество сборки в графе де Брюйна, был добавлен классификатор перекрытий, обученный отделять ложные связи от реальных.

Результат — ошибки при сборке сократились примерно в 1.5 раза, однако общая структура графа осталась фрагментированной. Это показывает потенциал, но требует дальнейшей доработки моделей.

Выводы

• Abyss показал наименьшее количество ошибок, но дал фрагментированную сборку.
• SPAdes и Velvet собирают более длинные контиги, но с большим числом ошибок
• Граф перекрытий лучше подходит для сборки длинных и немногочисленных ридов
• Граф де Брюйна показывает очень высокую фрагментацию при сборке
• Внедрение машинного обучения позволило снизить количество ошибок при сборке