Алгоритмы поиска текста, написанного китайскими иероглифами, полностью подходят для создания генной поисковой машины.

Геном человека


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

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

Китайский ученый-программист Вонг Льянг (Wang Liang) из компании SOSO.com, являющейся одной из самых крупных поисковых машин в Китае, предложил для поиска в биоинформационной базе данных использовать методики и алгоритмы, схожие с алгоритмами для поиска текста, написанного китайскими иероглифами.

Используя каждую базовую последовательность пар генов как слово поисковая машина должна составить список генов, где она появляется. Но с обычными словами все легко - они достаточно просто отделяются друг от друга и поэтому их легко распознать. В новом методе длинные "генные" слова предлагается сегментировать на более короткие последовательности "n-граммы" (не путайте эти n-граммы с граммами, единицами веса), слова, длинной в n букв.

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

Вонг Льянг провел анализ последовательности ДНК, взятого от четырех разных живых существ. Этот анализ показал, что вся последовательность ДНК, в основном, подчиняется закону Зипфа, который утверждает, что половина слов любом длинном документе появляется всего однажды. Это позволило вычислить среднюю длину "слова" ДНК, которая оказалась равной 12 "символам". Используя словарь таких 12-граммных "слов" ДНК можно составить обратный индекс, с помощью которого становится возможным невероятно быстрый поиск, подобный поиску, реализованному компанией Google.




Ключевые слова:
ДНК, Геном, Последовательность, Поиск, Алгоритм, Обратный, Индекс, Поисковая, Машина, Слово, Китай, Иероглиф, Google, Закон, Зипфа

Первоисточник

Другие новости по теме:
  • Создан робот, способный изучить, понять и использовать язык человека
  • Роботы получили возможность учиться, просматривая обучающие видео с YouTube
  • Создана новая поисковая программа, способная разузнать абсолютно все по виз ...
  • Открытый проект Materials Project и его база данных - революционный подход ...
  • Google внедряет новые квантовые алгоритмы, что позволит значительное ускоре ...




  • 5 июля 2010 13:53
    #1 Написал: FomaNeverujuwij

    Публикаций: 0
    Комментариев: 4313
    Ну, может из этого что-нибудь и выйдет. Не зря Гугль отрабатывал алгоритмы с этими обратными индексами так долго.


    --------------------
        
    5 июля 2010 16:52
    #2 Написал: Zilux

    Публикаций: 0
    Комментариев: 0
    Меня лично очень радует фраза
    Количество накопленной информации растет в экспоненциальной зависимости
    и если такого рода поиск поможет ускорить этот процесс то я только рад.
        

    Информация

    Посетители, находящиеся в группе Гости, не могут оставлять комментарии к данной публикации.