Подписаться на новости
  • Сенатор
  • ООО "Ай Вао"
  • healthage-forum
  • vsh25
  • Vitacoin

Как отыскать в геноме нужный ген?

Поисковая система: не заблудиться в геномах
«Популярная механика» по сообщению Technology Review: How to Build a Better DNA Search Engine


Что общего у китайского языка и биоинформационных баз данных, содержащих геномы обитателей нашей планеты? С точки зрения организации быстрого поиска по ключевым «словам» – сходство есть.

Чему Google научил современных пользователей мировой паутины – так это тому, что поиск в сети – это быстро, очень быстро. Мелкие буквы под строкой поиска постоянно напоминают об этом. Введите, к примеру, в поисковой системе слово «физика» – и получите «примерно 17 900 000 результатов» за 0,16 сек. Со скоростью мысли? Возможно, даже быстрее.

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

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

Биоинформационные системы поиска используют, в основном, алгоритмы BLAST или FASTA. Фактически, это сравнение данных одного генома с другим, потом с последующим, и так далее. Такой поиск дает удовлетворительные результаты при условии, что общее число сопоставляемых геномов невелико.

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

Тогда поисковые системы изменили свой подход к делу: они перевернули процесс индексирования с ног на голову, создав так называемый «инвертированный индекс». Принцип прост: вместо того, чтобы создавать для каждой страницы список содержащихся на ней слов, каждому слову ставится в соответствие список страниц, на которых оно встречается.

Это значительно упрощает поиск, но существуют некоторые тонкости, омрачающие картину. Для русского языка определить границу слов несложно – они разделены пробелом. Но то же самое нельзя сказать о генетической информации – в геномах «пробелов» нет. Поэтому возникает вопрос: что же считать «словом»?

Вот тут-то человечеству и пригождается столь трудный в изучении китайский язык, фактически лишенный пробелов, и принципы работы китайских поисковых систем. Для того, чтобы проиндексировать текст без разделителей (пробелов), можно разбить его на n-граммы – фрагменты длиной в n символов (букв). Например, разбив текст на 2-граммы (двухбуквенные слова), поиск по трехбуквенному ключевому слову АВС можно произвести как поиск по словам АВ и ВС. Более того, именно так и работают некоторые китайские поисковые системы.

Но сколько букв в каждом «слове» генома, какой длины последовательности должна индексировать поисковая система? Однобуквенное разбиение дает всего 4 различных «слова» – основные нуклеотиды A, T, C и G. Но при таком разбиении поиск по более длинным «ключевым словам» будет требовать слишком много времени и может оказаться практически невыполним.

Оптимальная длина n-граммы находится на основании статистического распределения слов в тексте (в том числе и в генетическом), подчиняющегося закону Ципфа.

Закон Ципфа (Зипфа) назван в честь его первооткрывателя – американского лингвиста George Kingsley Zipf из Гарвардского университета. Это эмпирически найденная закономерность распределения частоты слов естественного языка: если все слова языка или достаточно длинного текста упорядочить по убыванию частоты их использования, то частота n-го слова в таком списке окажется приблизительно обратно пропорциональной его порядковому номеру n (так называемому рангу этого слова). Например, второе по используемости слово встречается примерно в два раза реже, чем первое, третье – в три раза реже, чем первое, и т. д.


На графике – частота встречаемости слов в русской Википедии

Фактически, в достаточно большом документе 50% слов встречаются только однажды. Это может быть использовано для определения длины «слова» генома для индексирования.


Зависимость количества слов,
встречающихся в геноме только однажды,
от выбранной длины одного слова.

Так, при разбиении китайского текста на 1-граммы, количество встречающихся лишь однажды «слов» меньше 50%, для 2-грамм эта величина примерно 50%, а для 3-грамм – снова значительно меньше 50%. Следовательно, «золотой серединой» является разбиение текста на двухбуквенные слова.

Применив тот же принцип к геномам арабидопсиса, аспергилла, дрозофилы и мыши, исследователи из SOSO.com (одна из трех крупнейших в Китае поисковых систем) пришли к выводу, что в данном случае оптимальным будет использование 12-буквенных «слов».

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

Портал «Вечная молодость» http://vechnayamolodost.ru
01.07.2010

Читать статьи по темам:

биоинформатика геномика компьютеры Версия для печати
Ошибка в тексте?
Выдели ее и нажми ctrl + enter
назад

Читать также:

Биоинформатика регуляции и структуры геномов и системная биология

Приглашаем принять участие в Седьмой международной конференции «Биоинформатика регуляции и структуры геномов \ Системная биология (Bioinformatics of Genome Regulation and Structure \ Systems Biology).

читать

Геномика, протеомика, биоинформатика и нанобиотехнологии для медицины

V Юбилейная международная конференция «Геномика, протеомика, биоинформатика и нанобиотехнологии для медицины» состоится 31.05-05.06.2010 на теплоходе, следующем по маршруту Санкт-Петербург–Валаам–Коневец–Кижи–Санкт-Петербург.

читать

Биоинформатика – это не наука

В последние десятилетия появилось много новых наук с модными названиями: биоинформатика, геномика, протеомика, системная биология... Но по сути биоинформатика – не наука, а набор технологий и задач, которые решают с их помощью.

читать

«Википедия» создает интернет-генотеку

По планам создателей, основная задача Gene Wiki заключается в унификации информации по каждому гену, а также в возможности добавлять специалистами новейшую информацию по мере ее появления.

читать

Поездка на IV съезд общества биохимиков и молекулярных биологов

Фонд «Вечная молодость» на IV съезде Общества биохимиков и молекулярных биологов в Новосибирске представляли руководитель научно-экспертного отдела и его заместитель.

читать