Инструментальное средство поиска регуляторных мотивов в геномах
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
геномов, среди которых присутствуют как очень близкие в эволюционном отношении (штаммы), так и далекие (типы и выше). В этом случае построить выравнивание трудно. К тому же, если в наборе исходных данных есть несколько групп разного размера, состоящих из очень близких видов, то с точки зрения алгоритма поиска большую значимость будут иметь мотивы, присутствующие в самой многочисленной группе. Даже использования методов взвешивания последовательностей не достаточно, чтобы решить такую проблему.
Клифтен и др. [80] использовали филогенетический футпринтинг для поиска мотивов в шести геномах Saccharomyces. Авторы применили СLUSTAL W для выравнивания последовательностей. Они обнаружили множество статистически достоверных консервативных участков. Но этот результат был получен только потому, что геномы для исследования были тщательно отобраны так, чтобы расстояние между ними было оптимальным.
.3.3 Алгоритмы, комбинирующие различные подходы
Комбинированные алгоритмы могут обрабатывать данные, состоящие из последовательностей и перед совместно регулируемыми генами, и перед ортологичными генами. При этом они используют различные методы поиска мотивов, в том числе и филогенетический футпринтинг. Такие алгоритмы учитывают два важнейших аспекта определения значимости мотивов: перепредставленность и межвидовую консервативность.
Алгоритм Келлиса и др. [81] осуществляет поиск в две стадии: сначала в смешанных данных находятся высоко консервативные участки, а уже среди них ищутся перепредставленные. Пракаш и др. [82] разработали алгоритм OrthoMeme, использующий метод максимизации ожидания, в котором два вида поиска в смешанных данных осуществляется одновременно.
Ванг и Стормо [83] разработали алгоритм PhyloCon, основанный на алгоритме Consensus [52]. В нем поиск осуществляется в две стадии. Сначала для областей перед ортологичными генами строится множественные выравнивания и выделяются консервативные области, по которым составляются PWM. Далее с помощью полученных PWM мотивы ищутся перед всеми генами каждого генома. Авторы показали, что PhyloCon имеет очень низкий уровень перепредсказаний. Алгоритм хорошо работает как на коротких, так и на длинных последовательностях.
Особенностью алгоритма, разработанного Синха и др. [84] является то, что при построении множественного выравнивания допускается условие, что мотив может встретиться не во всех последовательностях. Авторы протестировали алгоритм на последовательностях из геномов дрожжей, мухи и даже человека. Сравнение с такими алгоритмами, как MEME, OrthoMEME, PhyloGibbs [85], EMnEm [86] и GIBBS (Wadsworth Gibbs sampler) [87] показало, что алгоритм более эффективен в большинстве случаев.
.3.4 Сравнительный анализ алгоритмов поиска мотивов
Сейчас доступно огромное количество алгоритмов поиска мотивов. К сожалению, невозможно выделить один универсальный алгоритм: каждый из них имеет свои ограничения. В литературе описано несколько работ по сравнению алгоритмов.
Томпа и др. [88] сравнили 13 алгоритмов поиска мотивов: AlignACE, ANN-Spec [89], Consensus, GLAM [90], Improbizer [91], MEME, MITRA, MotifSampler, Oligo/Dyad-Analysis, QuickScore [92], SeSiMCMC [67], Weeder и YMF. Для этого были созданы наборы данных, состоящие из последовательностей, содержащих известные сайты связывания транскрипционных факторов из базы данных TRANSFAC [13]. Авторам алгоритмов было предложено протестировать свои инструменты на данных наборах с четко установленными параметрами и предоставить для сравнения лучший полученный результат. Сравнение результатов показало общую низкую эффективность работы всех алгоритмов. Однако алгоритм Weeder превзошел другие в большинстве случаев. При этом SeSiMCMC оказался эффективнее при тестировании на последовательностях из геномов мух, а MEME3 (разновидность MEME) и YMF - на последовательностях из геномов мышей. Авторы предположили, что алгоритмы, использующие различные подходы для поиска мотивов, будут более эффективны и универсальны.
Хью и др. [69] также сравнили различные алгоритмы, но при этом использовали последовательности из базы данных регулонов E.coli RegulonDB [93], а также позволили авторам самим подбирать оптимальные параметры поиска и предоставлять не только лучший, но и другие полученные результаты. В эксперименте участвовали пять алгоритмов: AlignACE, MEME, BioProspector, MDScan и MotifSampler. К сожалению, это исследование также показало общую низкую эффективность всех алгоритмов. Основной проблемой практически всех алгоритмов была длина последовательностей - при увеличении значения этого параметра, результаты резко ухудшались. Лидером был признан популярный алгоритм MEME, показавший эффективность в 52% относительно среднего уровня 15%-35%.
1.4 Скрытые марковские модели и вспомогательные алгоритмы
Скрытая марковская модель (СММ, Hidden Markov Model, HMM) - статистическая модель, имитирующая работу процесса, похожего на марковский процесс с неизвестными параметрами. Задача состоит в оценке неизвестных параметров по наблюдаемым данным. Полученные параметры могут быть использованы в дальнейшем анализе. СММ может быть рассмотрена как сеть условных Байесовских вероятностей [33].
Первые заметки о скрытых марковских моделях опубликовал Баум в 1960-х, и уже в 70-х их впервые применили при распознавании речи. С середины 1980-х СММ применяются при анализе биологических последовательностей, в частности, ДНК.
Элементами скрытой марковской модели являются состояния. Обозначим состояние в момент времени t через x(t) (рис. 9.). Каждое состояние имеет эмиссионные вероятности - распределение ср