Поисковая система: Не заблудиться в геномах
Чему Google научил современных пользователей мировой паутины — так это тому, что поиск в сети — это быстро, очень быстро. Мелкие буквы под строкой поиска постоянно напоминают об этом. Введите, к примеру, в поисковой системе слово «физика» — и получите «примерно 17 900 000 результатов» за 0,16 сек. Со скоростью мысли? Возможно, даже быстрее.
Для исследователей, работающих с биоинформационными базами данных, такие скорости пока что кажутся фантастическими. Эти базы огромны и продолжают расти в геометрической прогрессии. Они содержат данные как о геномах разных видов, так и генетическую информацию отдельных особей внутри вида.
Может показаться, что найти ген, общий для некоторых видов или отдельных организмов, столь же просто, как ввести ключевые слова в привычную поисковую систему и получить результат. Однако это не так.
Поисковые системы, работающие в сети Интернет, столкнулись с этой проблемой 20 лет назад на волне роста объемов информации во всемирной паутине. Изначально они индексировали содержимое сети путем записи слов, содержащихся в документах. Чтобы найти страницу по ключевому слову, система искала его сначала в одном документе, потом в следующем и так далее. С ростом общего количества веб-страниц этот метод работал все медленнее и медленнее...
Тогда поисковые системы изменили свой подход к делу: они перевернули процесс индексирования с ног на голову, создав так называемый «инвертированный индекс». Принцип прост: вместо того, чтобы создавать для каждой страницы список содержащихся на ней слов, каждому слову ставится в соответствие список страниц, на которых оно встречается.
Это значительно упрощает поиск, но существуют некоторые тонкости, омрачающие картину. Для русского языка определить границу слов несложно — они разделены пробелом. Но то же самое нельзя сказать о генетической информации — в геномах «пробелов» нет. Поэтому возникает вопрос: что же считать «словом»?
Вот тут-то человечеству и пригождается столь трудный в изучении китайский язык, фактически лишенный пробелов, и принципы работы китайских поисковых систем. Для того, чтобы проиндексировать текст без разделителей (пробелов), можно разбить его на n-граммы — фрагменты длиной в n символов (букв). Например, разбив текст на 2-граммы (двухбуквенные слова), поиск по трехбуквенному ключевому слову АВС можно произвести как поиск по словам АВ и ВС. Более того, именно так и работают некоторые китайские поисковые системы.
Но сколько букв в каждом «слове» генома, какой длины последовательности должна индексировать поисковая система? Однобуквенное разбиение дает всего 4 различных «слова» — основные нуклеотиды A, T, C и G. Но при таком разбиении поиск по более длинным «ключевым словам» будет требовать слишком много времени и может оказаться практически невыполним.
Оптимальная длина n-граммы находится на основании статистического распределения слов в тексте (в том числе и в генетическом), подчиняющегося закону Ципфа. Фактически, в достаточно большом документе 50% слов встречаются только однажды. Это может быть использовано для определения длины «слова» генома для индексирования.
Так, при разбиении китайского текста на 1-граммы, количество встречающихся лишь однажды «слов» меньше 50%, для 2-грамм эта величина примерно 50%, а для 3-грамм — снова значительно меньше 50%. Следовательно, «золотой серединой» является разбиение текста на двухбуквенные слова.
Применив тот же принцип к геномам арабидопсиса, аспергилла, дрозофилы и мыши, исследователи из SOSO.com (одна из трех крупнейших в Китае поисковых систем) пришли к выводу, что в данном случае оптимальным будет использование 12-буквенных «слов».
Применение данного подхода в биоинформатике не требует создания какой-либо новой технологии — существующие системы (в том числе с открытым исходным кодом) вполне способны справиться с поставленной задачей. С ростом объемов обрабатываемых данных назрела необходимость применить современный подход к поиску, и похоже, что SOSO собирается занять эту нишу.
По сообщению Technology Review