Инструментальное средство поиска регуляторных мотивов в геномах
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
уются марковские цепи от нулевого до третьего порядка для построения фонового распределения. Параметры для них задаются пользователем или вычисляются по исходным последовательностями. Во-вторых, алгоритм позволяет искать двойные мотивы, разделенные спейсером, и палиндромные мотивы. Алгоритм использовали для поиска сайтов связывания как в прокариотах, так и эукариотах (дрожжах).
Шида [62] разработал алгоритм поиска мотивов GibbsSt, использующий метод имитации теплового отжига (simulated annealing [63]) совместно с алгоритмом Gibbs sampling. Позже стало известно, что этот метод гораздо лучше решает проблемы, связанные с нахождением локально лучшего решения [64]. В биоинформатке метод имитации теплового отжига в основном применяется для улучшения методов поиска в пространстве решений [65, 66]. В алгоритме GibbsST метод имитации теплового отжига используется для улучшения работы алгоритма Gibbs sampling.
Другие подходы
Хью и др. [69] использовали комбинированный подход для создания алгоритма поиска мотивов EMD [70]. Алгоритм основан на кластеризации. В нем используется комбинация предсказаний, полученных из множества пробегов одного или более различных алгоритмов поиска: AlignACE, Bioprospector, MDScan [71], MEME и MotifSampler. Алгоритм в 22.4% случаев показал более высокий результат, нежели все компоненты алгоритма отдельно. EMD показал наибольшую эффективность в случае поиска в коротких последовательностях. В случае поиска в длинных последовательностях, он всегда более или по крайней мере также эффективен, как отдельные элементы алгоритма.
Каплан и др. [31] создали алгоритм, использующий помимо последовательностей ДНК информацию о структуре ДНК-связывающих доменов известных транскрипционных факторов. По ним предсказываются возможные сайты связывания, которые ищутся в последовательностях.
Лью и др. [72] разработали алгоритм, основанный на нейронных сетях, для поиска мотивов в последовательностях ДНК и белковых последовательностях. Сеть содержит несколько уровней. Предсказание мотивов происходит поступательно: на верхнем уровне последовательность разбивается на небольшие участки, а на нижнем эти участки классифицируются на мотивные и фоновые. При этом полученные данные сохраняются и используются для уточнения результатов в следующих тестах. Основное преимущество такого алгоритма в том, что он хорошо работает с длинными последовательностями
Кингсфорд и др. [73] разработали алгоритм для поиска мотивов в последовательностях ДНК, который ищет набор подпоследовательностей определенного размера таким образом, чтобы сумма попарных расстояний между ними была минимальна. Для этого используется целочисленное линейное программирование (ILP). Преимуществом данного алгоритма является то, что он работает относительно небольшое время на выборках любой величины. Тестирование на последовательностях из E.coli показало эффективность алгоритма, сопоставимую с эффективностью некоторых методов, основанных на алгоритме Gibbs sampling.
Ле и др. [74] создали генетический алгоритм HIGEDA, использующий в начальной стадии алгоритм EM для поиска лучших параметров модели мотива. Помимо этого, HIGEDA может искать мотивы не только с мутациями, но и с инсерциями и делециями.
.3.2 Алгоритмы, основанные на методе филогенетического футпринтинга
Основное преимущество филогенетического футпринтинга по сравнению с подходом, использующим совместно регулируемые гены, состоит в том, что определить ортологичные гены часто бывает проще, чем совместно регулируемые. На сегодняшний день в открытом доступе находится большое количество аннотированных геномов, в том числе близкородственных, что позволяет применять технику филогенетического футпринтинга для поиска мотивов. Для определения регуляторных элементов в последовательностях чаще всего строится множественное выравнивание промоторных областей ортологичных генов, а затем на нем выделяются особо консервативные участки. Построение множественного выравнивания осуществляется при помощи таких алгоритмов, как CLUSTAL W [75].
К сожалению, было показано [76-78], что алгоритмы, использующие филогенетический футпринтинг не всегда применимы. Если сравниваемые виды слишком близки друг другу в смысле эволюционного расстояния (например, различные штаммы одного вида) выравнивание последовательностей очевидно, но не информативно, поскольку функциональные элементы не более консервативны, чем окружающая нефункциональная последовательность. Если же последовательности очень сильно разошлись, сложно построить удовлетворительное выравнивание. В этом случае совместно с филогенетическим футпринтингом часто используются такие существующие алгоритмы поиска мотивов, как MEME, Consensus или Gibbs sampling.
Клифтен и др. [76] использовали AlignACE для поиска мотивов в сравнительном анализе последовательностей ДНК нескольких видов Saccharomyces, и получили хорошие результаты в тех случаях, когда построить глобальное выравнивание было невозможно. Маккью и др. [79] использовали алгоритм Gibbs sampling совместно с филогенетическим футпринтингом для поиска мотивов в геномах протеобактерий.
Бланшетт и Томпа [77] создали эффективно работающий алгоритм поиска мотивов, использующий филогенетический футпринтинг совместно с динамическим программированием. В своей работе Бланшетт и Томпа отметили, что алгоритмы поиска мотивов часто не учитывают степень эволюционной близости последовательностей и считают их независимыми. Это особенно критично в случае, если производится анализ большого количества