Методы бикластеризации для анализа интернет-данных

       

Постановка задачи и основные определения


Под термином бикластеризация понимается широкий круг задач и методов, а потому для него в научной литературе существует целый ряд синонимов: совместная кластеризация (simultaneous clustering), кокластеризация (co-clustering), двувходовая кластеризация (two-way clustering), кластеризация подпространства (subspace clustering), двумерная кластеризация (bi-dimensional) и бокс-кластеризация (box-clustering). Повышенный интерес к бикластеризации и выделение ее в самостоятельную область анализа данных возникли в связи задачей анализа массивов генетических данных (microarray data analysis). Поэтому, прежде чем дать основные определения из области бикластеризации, мы опишем задачи анализа генетических данных и то, как бикластеринг оказывается полезен для их решения.

Обычно данные генной экспрессии (gene expression data) представляют собой матрицу, в которой строки соответствуют генам, а столбцы — условиям. Каждый элемент такой матрицы отражает уровень экспрессии некоторого гена при заданном условии и представлен действительным числом, как правило, логарифмом относительного содержания информационной РНК (mRNA) гена при этом условии. Такие матрицы, как правило, изучают в двух размерностях, в размерности генов или столбцов. Этим способам анализа соответствует выявление экспрессии шаблонов генов посредством сравнения строк или столбцов. Общие задачи такого анализа включают в себя:

  • группировку генов согласно их экспрессии для множества условий;
  • классификацию нового гена по известной экспрессии его и других генов для установленной классификации;
  • группировку условий, основанная на экспрессии конкретного множества генов;
  • классификацию нового образца при известной экспрессии генов и условиях эксперимента.
  • Методы кластеризации могут быть использованы для группирования либо генов, либо условий, а потому явно решают задачи 1 и 3, указанные выше, и неявно — 2 и 4. Но применение методов кластеризации к анализу данных генной экспрессии ведет к значительным сложностям. Активационные образцы образуют группы генов только при определенных экспериментальных условиях. Таким образом, понимание клеточных процессов указывает на то, что необходимо искать множество генов, ведущих себя слаженно и совместно выраженных только при некоторых экспериментальных условиях, и почти независимо при других условиях. А значит, необходимы специальные методы поиска таких локальных образцов, которые могли бы играть ключевую роль в открытии новых генетических взаимодействий [].


    В отличие от методов кластеризации, алгоритмы бикластеризации находят группы генов, проявляющих сходную активность для некоторого подмножества экспериментальных условий. Поэтому подход бикластеризации позволяет успешно решать задачи, в которых возникает одна или сразу несколько таких ситуаций, как:

  • только небольшое множество генов, участвующих в клеточном процессе, представляют интерес;


  • интересующий исследователя клеточный процесс происходит только при некотором подмножестве условий;


  • один ген может участвовать во многих взаимодействиях, которые как могут быть совместно активными, так и не могут для всех условий.


  • Поэтому предлагаемые методы бикластеризации должны следовать требованиям, перечисленным ниже.



  • Кластер генов необходимо определять в соответствии только подмножеству условий.

  • Кластер условий необходимо определять в соответствии только подмножеству генов.

  • Кластеры не должны быть исключающими и/или полными (гены или условия могут принадлежать ко многим кластерам или вообще ни к одному, а также могуть быть сгруппированы по подмножеству условий или генов соответственно).


  • В качестве дополнительного требования можно отметить робастность, понимаемую как наличие мощного (с точки зрения сложности процесса генетической регуляции) инструмента анализа и устойчивость к шуму в исходных данных.

    Фактически, мы будем работать с матрицей размера n на m, элементы которой в общем случае представляют собой действительные числа. Абстрагируясь от задач анализа генетических данных мы будем считать, что строкам матрицы соответствуют некоторые объекты, а столбцам — признаки. Пусть дана матрица


    ,


    — строк,


    — число столбцов,


    — множество строк,


    — множество столбцов. Будем использовать


    для обозначения матрицы


    . Если


    и


    подмножества строк и столбцов соответственно, то


    определяет подматрицу


    матрицы


    .

    Кластер строк есть подматрица матрицы


    вида


    , для которой подмножество строк проявляет "сходное поведение" вдоль всего множества столбцов.



    Кластер столбцов есть подматрица матрицы


    вида


    , для которой подмножество столбцов проявляет "сходное поведение" вдоль строк. Бикластер есть подматрица матрицы


    вида


    , такая что ее строки проявляют "сходное поведение" на столбцах и наоборот.

    Отметим, что мы дали недостаточно формальное определение бикластера. В рамках моделей, представленных в работе, требования, которые предъявляются к понятию бикластера, различаются, а потому формальные определения даются нами только для конкретных случаев. Задача, которую решает алгоритм бикластеризации, заключается в нахождении такого множества бикластеров
    , которое удовлетворяет некоторым формально определенным требованиям однородности. Словосочетания "сходное поведение" и требования однородности раскрываются в подразделе в определениях типов бикластеров.


    Содержание раздела