Открытые базы данных генетическим структурам позволяют исследователям в режиме онлайн-запросов искать близкие генетические структуры или их части для анализа геномов, однако время выполнения такого запроса иногда исчисляется сутками. С аналогичной проблемой ученые сталкиваются и при сборке полного генома организма, в частности, геномов хвойных растений, особенность которых - большая доля повторов. Такой процесс занимает недели работы крупных вычислительных кластеров. Математики в настоящее время работают над созданием быстрых алгоритмов поиска совпадающих подпоследовательностей в больших массивах подобных текстовых данных.
"Наш метод называется "быстрый поиск с обобщенной шкалой нониуса". Идея напоминает работу штангенциркуля, который имеет штангу с основной шкалой и нониус - вспомогательную шкалу для отсчета долей делений. Этот принцип позволяет резко повысить скорости работы - в 10 раз, иногда больше. Кроме того, наш алгоритм может найти сходные участки ДНК там, где другие алгоритмы могут их пропустить", - рассказал Царев.
По его словам, быстрые алгоритмы поиска в текстах - область, применяемая чуть ли не везде в современном мире. Например, искать информацию в Google получается за считанные секунды, потому что там, кроме быстрых компьютеров, имеются весьма изощренные алгоритмы быстрого поиска нужной информации в накопленных данных. Другой пример - поиск сходных текстов системами типа "антиплагиат", поиск ошибок в больших текстах и так далее.
Разработка алгоритма, по словам Царева, началась в 2015 году - тогда совместно с красноярским биофизиком, профессором Михаилом Садовским решено было разработать новый алгоритм быстрого поиска, учитывая специфику геномики. Первых результатов ученым удалось достичь уже в 2016 году и продемонстрировать работу алгоритма на геноме человека и геноме одной из разновидностей дрозофилы. Сравнивая полученные результаты с имеющимися алгоритмами поиска в геномной информации, в том числе со самым старым из них BLAST, оказалось, что алгоритм красноярских ученых значительно превосходит их по скорости поиска данных.
В дальнейшем исследователи намерены встроить свой алгоритм в имеющиеся алгоритмы поиска в геномных базах данных, ускорив их работу. "Также планируем опробовать эту идею в смежных областях - поиск сходных текстов в системах типа "антиплагиат", ускорение поиска в интернете - тут, конечно, своя область, но и там явно возможен прогресс", - отметил Царев.