Цифра › Софт2 мин чтения

McDag индексирует максимальные общие подпоследовательности пар геномных последовательностей за минуты

Авторы создали первый общедоступный инструмент индексации максимальных общих подпоследовательностей реальных геномных данных и обобщили определение на k строк.

McDag indexes maximal common subsequences of sequence pairs over 10,000 base pairs in minutes
Фото: Aimin Yang, Wei Zhang, Jiahao Wang, Ke Yang, Yang Han and Limin Zhang, Wikimedia Commons, CC BY-SA 4.0 · Лицензия: CC BY-SA 4.0

Исследователи Джованни Буцегга, Алессио Конте, Роберто Гросси и Джулия Пунци описали в журнале Algorithms for Molecular Biology инструмент McDag для индексации максимальных общих подпоследовательностей (MCS) геномных последовательностей. По словам авторов, это первый общедоступный инструмент, способный индексировать MCS реальных геномных данных. Он индексирует пары последовательностей длиной свыше 10 000 пар оснований за минуты, используя лишь на 4–7% больше узлов, чем минимально необходимо biomedcentral.comAlgorithms for Molecular Biologybiomedcentral.comОткрыть источник ↗.

Зачем нужны максимальные общие подпоследовательности

MCS — это максимальная по включению последовательность несмежных символов, общая для двух или более строк: вставить в неё символ так, чтобы она осталась общей для всех входных строк, нельзя. Любая наибольшая общая подпоследовательность (LCS) является MCS, но MCS сохраняют и более короткие неразширяемые общие фрагменты, которые анализ по LCS отбрасывает.

Авторы отмечают, что поиск LCS для произвольного числа k строк NP-полон, а для двух строк требует квадратичного времени при условных нижних оценках. Автоматы общих подпоследовательностей, в свою очередь, содержат множество немаксимальных подпоследовательностей. Число MCS тоже может быть экспоненциальным, поэтому перечислять и хранить их непрактично, и нужен компактный индекс.

Как строится индекс

McDag — детерминированный размеченный ориентированный ациклический граф с одним истоком и одним стоком. Каждый путь от истока к стоку задаёт ровно одну MCS, а каждой MCS соответствует ровно один путь. Исходящие рёбра любого узла ведут к узлам с различными метками. При построении удаляются «пузыри подпоследовательностей» — пары путей, где более короткий является подпоследовательностью более длинного biomedcentral.comAlgorithms for Molecular Biologybiomedcentral.comОткрыть источник ↗.

Построение идёт в два этапа. Сначала читают последовательности слева направо, отбрасывают доминируемые переходы и получают приближённый индекс CSA-mixed. Затем последовательности обходят в обратном порядке и собирают CSA-filtered, который передают процедуре McConstruct; она выдаёт итоговый McDag. Авторы реализовали алгоритмы на C++ и провели замеры на сервере с двумя процессорами Intel Xeon Gold 5318Y.

Определение McDag обобщено на несколько строк. Для трёх и более последовательностей авторы наблюдают экспериментально, что минимальный индекс может заметно увеличиваться по числу узлов. По данным публикации о работе, в экспериментах использовались геномные последовательности вирусов.

Источники · 2

Нашли ошибку?
  1. ↩

Читайте также

Далее

Следующая статья откроется сама

Ещё
Мы в соцсетях

Введите хотя бы две буквы — результаты появятся сразу

↑↓выбрать↵открытьescзакрыть