Журнал интеллектуального анализа данных в геномике и протеомике

Абстрактный

Suffix Graph — эффективный подход к анализу сетевых мотивов

Рахул Никам и Уша Чаухан

Сетевой мотив — это шаблон взаимосвязей, возникающих в сложной сети в количествах, которые значительно выше, чем в аналогичной рандомизированной сети. Основная предпосылка поиска сетевых мотивов заключается в возможности вычисления частоты подграфов. Чтобы обнаружить сетевой мотив, необходимо вычислить перепись подграфов в исходной сети, которая вычисляет частоту всех подграфов определенного типа. Затем необходимо вычислить частоту набора подграфов в рандомизированной аналогичной сети. Узким местом всего процесса обнаружения мотивов является, следовательно, вычисление частот подграфов, и это является основной вычислительной проблемой. Предлагаемая работа заключается в представлении суффикс-графа, структуры данных, которая эффективно хранит графы, и в разработке алгоритма для эффективного извлечения подграфа, который обнаруживает сетевые мотивы и применяет их к транскрипционным взаимодействиям в Escherichia coli.