Инструментальное средство поиска регуляторных мотивов в геномах
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
ом длины 15. Выборка содержит 15 последовательности длиной около 200 нуклеотидов. В обоих случаях в качестве лучшего результата был найден верный мотив (Таблица 3).
Таблица 3. Результаты тестирования нашего алгоритма на последовательностях из геномов Shewanella
Транскрипционный факторИнформационное содержаниеLogoMetJ_Shewanella (Repeat 8-0-8)14.519BirA_Shewanella (Inverted repeat 8-15-8)10.455
3.3 Сравнение с другими алгоритмам
Мы сравнили наш алгоритм с другими алгоритмами поиска мотивов в последовательностях ДНК: MEME [55] и SeSiMCMC [67]. Оба алгоритма показали высокую эффективность в проведенных ранее сравнительных экспериментах (см. обзор литературы, сравнительный анализ алгоритмов поиска мотивов), кроме того они общедоступны, удобны для пользования и работают достаточно быстро.
Алгоритм MEME не приспособлен для поиска двойных мотивов, разделенных спейсером, поэтому тестирование проводилось для палиндромных сайтов. Сравнение алгоритмов осуществлялось на двух тестовых выборках: пуриновой и аргининовой.
Пуриновая выборка изначально состояла из 19 последовательностей, содержащих 20 экспериментально определенных сайтов связывания фактора транскрипции PurR. Большинство сайтов в выборке одинарные, то есть по одному сайту в каждой последовательности. Сайты при этом довольно консервативные, с четко выраженной палиндромностью.
Аргининовая выборка изначально состояла из 8 последовательностей, содержащих 19 сайтов связывания факторов транскрипции ArgR. Сайты в выборке двойные и слабые (два сайта в одном фрагменте ДНК, каждый слабо похож на исходный мотив). Палиндромность мотива также очень слабо выражена.
Далее, один за другим мы вырезали сайты из последовательностей выборки, то есть каждый следующий тест содержал на один сайт меньше, чем предыдущий. Таким образом, все меньшее число последовательностей в тесте содержало искомый мотив. Каждый раз мы убирали самый сильный сайт, то есть сайт, имеющий наибольший вес относительно PWM.
При данном тестировании оценивалась чувствительность и специфичность рассматриваемых алгоритмов. Чувствительность (sensitivity) - это доля верно найденных сайтов из всех реально существующих сайтов в начальной выборке. Специфичность (specificity) - это доля верно найденных сайтов из всех найденных.
алгоритм регуляторный марковский модель
3.3.1 Пуриновый тест
При поиске сайтов в начальном файле с полным набором сайтов все три алгоритма нашли искомый мотив в качестве лучшего.
Чувствительность нашего алгоритма сопоставима с чувствительностью MEME. Алгоритм SeSiMCMC находит верный мотив в выборках с низким содержанием сайтов, но в целом чувствительность этого алгоритма ниже, чем у других.
Специфичность алгоритма MEME выше, чем у других алгоритмов. На выборках с большим количеством исключенных сайтов наш алгоритм показал более высокую специфичность, чем SeSiMCMC
3.3.2 Аргининовый тест
При поиске сайтов в начальном файле с полным набором сайтов все три алгоритма нашли искомый мотив в качестве лучшего. MEME нашел сайт со сдвигом на один нуклеотид.
Чувствительность и специфичность нахождения мотива на аргининовом тесте у всех алгоритмов сильно ниже, чем на пуриновом. Это объясняется тем, что мотив в аргининовой выборке значительно слабее, чем в пуриновой. На выборках с большим количеством сайтов наш алгоритм показал чувствительность, сравнимую с MEME, а на выборках с меньшим количеством сайтов превосходит его. SeSiMCMC показал относительно низкую общую чувствительность на данном тесте, однако он смог найти верный мотив в выборках с наименьшим количеством сайтов в исходных последовательностях. По специфичности (рис. 27) наш алгоритм превосходит MEME и SeSiMCMC на выборках с низким содержанием сайтов.
Заключение
Мы создали эффективный и удобный в использовании алгоритм поиска мотивов в последовательностях ДНК. Преимущество данного алгоритма состоит в том, что в нем скомбинировано несколько подходов к решению задачи: здесь используются словарные техники и скрытые марковские модели. Алгоритм приспособлен для поиска в последовательностях двойных мотивов, разделенных спейсером, длину которого можно варьировать.
Сравнение нашего алгоритма с другими известными алгоритмами показало, что наш алгоритм лучше приспособлен для поиска слабых мотивов, особенно в выборках данных, где сайт представлен небольшим количеством копий. При этом в случае поиска мотивов в выборках, где в каждой последовательности есть минимум один сайт, эффективность нашего алгоритма сопоставима с другими.
Также был разработан веб-ресурс для обеспечения открытого доступа к алгоритму и удобного просмотра результатов.
Выводы
1.Разработанный в лаборатории биоинформатики ФББ алгоритм поиска мотивов в нуклеотидных последовательностях дополнен возможностью идентификации мотивов сложной структуры с вариабельным спейсером. Для этого модифицированы все стадии базового алгоритма, в том числе разработаны новые схемы СММ. Также добавлены: начальная обработка данных, кластеризация слов-кандидатов и возможность уточнения мотивов.
.Алгоритм реализован на языке Java в среде разработки Eclipse.
.Тестирование на сгенерированных и реальных данных показало высокую эффективность алгоритма.
.Сравнение алгоритма с некоторыми другими показало, что наш алгоритм лучше других приспособлен для поиска слабых мотивов, особенно в выборках дан?/p>