В последнее время ученые, получив в свое распоряжение высокоточные научные инструменты, расшифровывают все больше и больше информации, заключенной в генах живых существ. Количество накопленной информации растет в экспоненциальной зависимости и эту уже сейчас вызывает большую проблему у ученых-генетиков, которые постоянно выполняют одну основную операцию - поиск схожих участков в различных генах. Таким образом назрела острая необходимость в создании универсальной поисковой машины, способной выполнить быстрый поиск по огромной биоинформационной базе данных.
Подавляющее большинство поисковых машин для ускорения поиска используют так называемый обратный индекс, вместо того, чтобы составлять индексы каждой веб-страницы в отдельности, они составляют списки мест, где появляются определенные ключевые слова. Поиск в биоинформационной базе, наоборот, использует пару несложных алгоритмов, которые в основном сравнивают данные одного генома с данными другого. Это делается относительно быстро только при небольшом количестве данных, но в связи с постоянно увеличивающимся объемом, поиск становится очень длительным процессом.
Китайский ученый-программист Вонг Льянг (Wang Liang) из компании SOSO.com, являющейся одной из самых крупных поисковых машин в Китае, предложил для поиска в биоинформационной базе данных использовать методики и алгоритмы, схожие с алгоритмами для поиска текста, написанного китайскими иероглифами.
Используя каждую базовую последовательность пар генов как слово поисковая машина должна составить список генов, где она появляется. Но с обычными словами все легко - они достаточно просто отделяются друг от друга и поэтому их легко распознать. В новом методе длинные "генные" слова предлагается сегментировать на более короткие последовательности "n-граммы" (не путайте эти n-граммы с граммами, единицами веса), слова, длинной в n букв.
Таким образом для того, что бы выполнить поиск трехбуквенного слова "АВС" необходимо получить и отфильтровать пересечение результатов поиска двухбуквенных слов "АВ" и "ВС". Именно таким образом и работают китайские поисковые машины, ищущие текст, состоящий из иероглифов.
Вонг Льянг провел анализ последовательности ДНК, взятого от четырех разных живых существ. Этот анализ показал, что вся последовательность ДНК, в основном, подчиняется закону Зипфа, который утверждает, что половина слов любом длинном документе появляется всего однажды. Это позволило вычислить среднюю длину "слова" ДНК, которая оказалась равной 12 "символам". Используя словарь таких 12-граммных "слов" ДНК можно составить обратный индекс, с помощью которого становится возможным невероятно быстрый поиск, подобный поиску, реализованному компанией Google.
Источник: www.dailytechinfo.org[/i]
|
