Genome Query — различия между версиями

Материал из SEWiki
Перейти к: навигация, поиск
Строка 10: Строка 10:
  
 
Приемущества разработанного алгоритма:
 
Приемущества разработанного алгоритма:
- Превосходство по времени поиска над реализованными в этом же проекте алгоритмом
+
 
Кнута-Морриса-Пратта и алгоритмами, использующими суффиксное дерево и суффиксный массив
+
- Превосходство по времени поиска над реализованными в этом же проекте алгоритмом Кнута-Морриса-Пратта и алгоритмами, использующими суффиксное дерево и суффиксный массив
  
 
- Превосходство по времени препроцессинга данных
 
- Превосходство по времени препроцессинга данных

Версия 11:53, 15 марта 2011

   * Студент: Андрей Пржибельский
   * Руководитель: Николай Вяххи 
   * Страничка проекта: http://confluence.jetbrains.net/display/GQRY/Genome+Query
   * Note: проект является командным, но в данной страничке описана в основном моя часть.

Описание: Основной задачей является создание веб-сервиса для поиска различных данных по геному человека. Основная функциональность включает поиск последовательностей нуклеотидов в геноме с различными опциями (поиск в хромосомах, генах, интронах/экзона, в заданных позициях), возможность просмотра различных генов и информации о них. Моей частью в данном проекте является разработка и реализация быстрых алгоритмов поиска.

Проделанная работа: За осенний семестр был разработан и реализован алгоритм, использующий индексацию блоков нуклеотидов в геноме.

Приемущества разработанного алгоритма:

- Превосходство по времени поиска над реализованными в этом же проекте алгоритмом Кнута-Морриса-Пратта и алгоритмами, использующими суффиксное дерево и суффиксный массив

- Превосходство по времени препроцессинга данных

- Возможность поиска оптимального параметра -- размер индексируемого блока (остальные алгоритмы параметров не имеют)

- Предложенная структура индексов занимает примерно 34-36 бит на нуклеотид, то есть около 13Гб для всего генома человека. Поэтому, так же как и суффиксный массив, данная структура не загружается в оперативную память, а читается с диска. Но в отличии от суффиксного массива, чтение из данной структуры производится последовательно, а не в произвольном порядке, что может существенно сказаться на производительности.


Возможные дальнейшие задачи:

- Реализация неточного поиска с различными системами штрафов

- Реализация алгоритмов определения

- Реализация алгоритмов поиска по сжатым суффиксным массивам (CSA)