Genome Query — различия между версиями
| (не показано 5 промежуточных версий этого же участника) | |||
| Строка 4: | Строка 4: | ||
* Note: проект является командным, но в данной страничке описана в основном моя часть. | * Note: проект является командным, но в данной страничке описана в основном моя часть. | ||
| − | Описание: Основной задачей является создание веб-сервиса для поиска различных данных по геному человека. Основная функциональность включает поиск последовательностей нуклеотидов в геноме с различными опциями (поиск в хромосомах, генах, интронах/экзона, в заданных позициях), возможность просмотра различных генов и информации о них. | + | '''Описание''': Основной задачей является создание веб-сервиса для поиска различных данных по геному человека. Основная функциональность включает поиск последовательностей нуклеотидов в геноме с различными опциями (поиск в хромосомах, генах, интронах/экзона, в заданных позициях), возможность просмотра различных генов и информации о них. |
Моей частью в данном проекте является разработка и реализация быстрых алгоритмов поиска. | Моей частью в данном проекте является разработка и реализация быстрых алгоритмов поиска. | ||
| − | |||
| − | Приемущества разработанного алгоритма: | + | '''Проделанная работа''': За осенний семестр был разработан и реализован алгоритм, использующий индексацию блоков нуклеотидов в геноме. |
| − | + | ||
| − | + | ||
| − | + | '''Приемущества разработанного алгоритма''': | |
| − | + | ||
| + | - Превосходство по времени поиска над реализованными в этом же проекте алгоритмом Кнута-Морриса-Пратта и алгоритмами, использующими суффиксное дерево и суффиксный массив | ||
| + | |||
| + | - Превосходство по времени препроцессинга данных | ||
| + | |||
| + | - Возможность поиска оптимального параметра -- размер индексируемого блока | ||
(остальные алгоритмы параметров не имеют) | (остальные алгоритмы параметров не имеют) | ||
| − | + | ||
| + | - Предложенная структура индексов занимает примерно 34-36 бит на нуклеотид, то есть | ||
около 13Гб для всего генома человека. Поэтому, так же как и суффиксный массив, данная | около 13Гб для всего генома человека. Поэтому, так же как и суффиксный массив, данная | ||
структура не загружается в оперативную память, а читается с диска. Но в отличии от | структура не загружается в оперативную память, а читается с диска. Но в отличии от | ||
| Строка 22: | Строка 27: | ||
| − | Возможные дальнейшие задачи: | + | '''Возможные дальнейшие задачи''': |
| − | + | ||
| − | + | - Разработка алгоритмов неточного поиска с различными системами штрафов | |
| − | + | ||
| + | - Разработка алгоритмов получения информации о данном участке генома (гены, повторы) | ||
| + | |||
| + | - Реализация алгоритмов поиска по сжатым суффиксным массивам (CSA) | ||
Текущая версия на 11:43, 16 марта 2011
* Студент: Андрей Пржибельский * Руководитель: Николай Вяххи * Страничка проекта: http://confluence.jetbrains.net/display/GQRY/Genome+Query * Note: проект является командным, но в данной страничке описана в основном моя часть.
Описание: Основной задачей является создание веб-сервиса для поиска различных данных по геному человека. Основная функциональность включает поиск последовательностей нуклеотидов в геноме с различными опциями (поиск в хромосомах, генах, интронах/экзона, в заданных позициях), возможность просмотра различных генов и информации о них. Моей частью в данном проекте является разработка и реализация быстрых алгоритмов поиска.
Проделанная работа: За осенний семестр был разработан и реализован алгоритм, использующий индексацию блоков нуклеотидов в геноме.
Приемущества разработанного алгоритма:
- Превосходство по времени поиска над реализованными в этом же проекте алгоритмом Кнута-Морриса-Пратта и алгоритмами, использующими суффиксное дерево и суффиксный массив
- Превосходство по времени препроцессинга данных
- Возможность поиска оптимального параметра -- размер индексируемого блока (остальные алгоритмы параметров не имеют)
- Предложенная структура индексов занимает примерно 34-36 бит на нуклеотид, то есть около 13Гб для всего генома человека. Поэтому, так же как и суффиксный массив, данная структура не загружается в оперативную память, а читается с диска. Но в отличии от суффиксного массива, чтение из данной структуры производится последовательно, а не в произвольном порядке, что может существенно сказаться на производительности.
Возможные дальнейшие задачи:
- Разработка алгоритмов неточного поиска с различными системами штрафов
- Разработка алгоритмов получения информации о данном участке генома (гены, повторы)
- Реализация алгоритмов поиска по сжатым суффиксным массивам (CSA)
