Алгоритм «компрессионного» поиска работает тем эффективнее, чем больше объем данных

12:01 29.08.2015

|   1216 прочтений



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

Секвенаторы ДНК уже больше десятка лет развиваются быстрее, чем компьютерные системы, применяемые для анализа геномных данных: поиск последовательностей ДНК по нынешним геномным базам может занимать часы, а с ростом объемов данных ситуация может еще ухудшиться.

Специалисты лаборатории искусственного интеллекта МТИ, занимающиеся задачей оптимизации анализа биологических и химических данных, предлагают ускорять поиск по генетической информации путем ее «компрессии». Используется тот факт, что геномы живых организмов, даже не слишком родственных, содержат очень большой объем одинаковой информации. Поэтому из всех возможных последовательностей четырех оснований А, Г, Т, Ц в геномах реальных организмов представлено лишь очень малое подмножество. Более того, в пространстве возможных геномов принадлежащие реальным организмам распределены не случайным образом, а следуя определенной закономерности, отражающей относительно медленные темпы расхождения свойств близких видов.

Компрессионный алгоритм поиска ученых МТИ объединяет в кластеры последовательности, различающиеся несколькими буквами оснований, и выбирает одну из последовательностей представителем кластера. Поиск производится только по самым вероятным кластерам, таким образом большая часть данных вообще не просматривается.

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

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


Теги: Большие данные Геном МТИ


На ту же тему: