§ 79. Применение в биоинформатике

Предложен принципиально новый подход к построению классификаций нуклеотидных последовательностей на основе понятия «естественной» классификации. «Естественная» классификация базируется на принципе: объекты одного класса должны подчиняться одной группе закономерностей, объекты разных классов – разным группам закономерностей. На этом принципе разработан метод построения классификации, алгоритм и программная система GeneNatClass.

Разработан метод построения классификации, алгоритм и программная система GeneNatClass, позволяющая выделять «естественные» классы подпоследовательностей – мотивы.

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

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

В отличие от упомянутых классификаций, цель «естественной» классификации состоит в познании предметной области и выявления тех скрытых, латентных отношений, понятий и закономерностей, которые важны для построения теории предметной области и обладают предсказательной силой. В этом смысле, «естественной является та, и только та классификация, которая выражает закон природы» [46] и обеспечивает:

–          предсказание максимума свойств объекта по его месту в классификации;

–          максимум общих утверждений о каждом классе;

–          сохранение структуры классов при смене классификационных признаков;

–          объективность, надежность, прогностическая сила.

Конструктивный критерий «естественной» классификации предложен в работе [14]: «Разбиение объектов на классы должно производиться в соответствии с закономерностями, которым удовлетворяют объекты. Точнее, объекты одного класса должны подчиняться одной группе закономерностей, а объекты разных классов разным группам закономерностей. Объекты одного класса также должны обладать некоторой целостностью. Целостность – взаимная согласованность закономерностей каждой группы по взаимопредсказанию свойств объектов. У групп закономерностей могут быть, кроме того, общие закономерности, устанавливающие связь признаков объектов из разных классов».

Множества закономерностей каждого класса выявляют закономерную структуру объектов класса. Как показано в работе [29], закономерная структура точно отражает процесс идеализации, поэтому саму эту структуру мы называем идеальным объектом класса, а процедуру классификации – идеализацией.

Метод «естественной» классификации [14] можно разбить на следующие этапы:

―  представление первичных знаний и формирование обучающей выборки;

―  формализация различных типов отношений, важных с точки зрения эксперта для описания выделенных объектов;

―  построение признакового пространства объектов. Построение переменных высшего порядка через примитивные переменные;

―  обнаружение закономерностей;

―  опецификация системы вложенных Rule Types;

―  генерация различного вида статистических гипотез на основе Rule Types и проверка их на обучающей выборке; поиск закономерностей, значимых для распознавания различных типов объектов;

―  поиск всех закономерных структур (идеальных объектов) классов.

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

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

Необходимо сразу же отметить, что метод обнаружения закономерностей в качестве обучающей выборки требует матрицу объект-признак. Нуклеотидные последовательности превращаются в матрицу объект-признак следующим образом. Расположим исходные последова­тель­ности друг над другом, каждую в отдельной строке матрицы. При этом первый столбец будет образован стартовыми нуклеотидами всех последовательностей, второй столбец – вторыми нуклеотидами и т.д. Значение внутри клетки этой матрицы соответствует коду нуклеотида: 1 – A, 2 – T, 3 – G, 4 – C. В этом случае набор последовательностей преобразуется в матрицу, содержащую столько строк, сколько последовательностей в обучающей выборке.

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

В общем случае множество признаков, значения которых определены для конкретных объектов, может меняться. Формально такие данные можно представить в виде XML описания или множества реляционных таблиц.

Алгоритм обнаружения закономерностей. Для обнаружения закономерностей используется реляционный подход к Data Mining методам [121], апробированный в системе Discovery, позволяющей обнаруживать и проверять практически любые типы гипотез в языке первого порядка. Система вложенных Rule Types реализует стратегию все более точного и детального анализа теории предметной области. Этот подход позволяет: 1) обрабатывать данные любого типа, измеренные в любых шкалах (частичного порядка, решеток, наименований, порядка, лог-линейных, древовидных, сетей, графов и т. д., а также смеси всех этих величин); 2) обнаруживать законопо­доб­ные правила в условиях шумов и малых обучающих выборок.

Простейшие закономерности на символьных последовательностях имеют вид

ЕСЛИ ,

ТО ,                                                                                         (1)

где , j = 0,1,…,k  означает, что в позиции ij объекта α находится (при ej = 1) или не находится (при ej = 0) одно из значений {A | T | G | C}.

Реляционный подход к Data Mining методам означает применение стратегии все более точного и детального анализа данных путем сколь угодно сложного уточнения проверяемой гипотезы. Например, для символьных последовательностей гипотезы могут включать дополнительные признаки принадлежности нуклеотидов некоторому району, специфические или допустимые расстояния между нуклеотидами, свойства самих нуклеотидов и т. д. [33].

В качестве целевого признака закономерности перебираются все признаки объектов. Посылка (Premis) играет роль фильтрующего запроса, который выбирает из выборки те объекты, в которых все признаки посылки имеют значения указанные в закономерности. Чтобы измерить силу закономерности, мы сравниваем условное распределение значений целевого при выполнении всех посылочных признаков с распределением значений целевого признака на всех объектах. Чем сильнее закономерность, тем больше отклонение условного распределения значений целевого признака от исходного. Одним из простейших способов измерения такого отклонения является статистика c2. Мы используем ее в варианте так называемого нормированного Zc2-отклонения:


N – всего строк в таблице; Nk – число строк в таблице, где выполняется (k = 1), не выполняется (k = 2) посылка;  – число строк в таблице, где встречаются значения целевого признака j0 Î {A,T,G,C}; – число строк в таблице, где одновременно встречаются значения k и j0; = Nk / N – ожидаемое значение  при условии независимости k и j0.


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

Построение идеальных объектов. Следующий этап анализа нуклеотидных последовательностей – построение идеальных образов реальных последовательностей. Если объекты класса обладают некоторой целостностью, то она проявится в структуре закономерных связей, связывающих части / признаки объекта в единое целое. Структура закономерных связей и будет определять связь частей / признаков объекта в единое целое.

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

Программно процесс идеализации организован следующим образом: для некоторой реальной последовательности создается матрица M, содержащая столько строк, сколько нуклеотидов в последовательности, и 4 столбца, по одному для A, T, G и C. Просматривается все множество закономерностей R. Каждая применимая к последовательности закономерность прибавляет свои 4 предсказания в виде Zc2-отклонений (для A, T, G и C) в 4 ячейки той строки, которая соответствует целевому признаку закономерности. Если одно или больше из этих четырех значений содержатся в последовательности, то суммарный критерий самосогласования получает вклад, равный сумме предсказаний (Zc2-отклонений) этих значений (и только этих значений). Если же значение входит в последовательность с отрицательным знаком, то и соответствующий вклад тоже берется с минусом. Вхождение с отрицательным знаком означает, что в данной последовательности соответствующего нуклеотида быть не должно. Ноль означает, что данный нуклеотид просто не входит в последовательность, но при этом не требуется его отсутствие.

Определим последовательности, являющиеся идеальными объектами классов. Для этого введем критерий взаимной согласованности закономерностей по предсказанию на этих объектах:


где R – множество закономерностей, δ(i0, j0) = 1 (-1), если в текущей позиции i0 последовательности состояние нуклеотида j0 = {A | T | G | C} совпадает (не совпадает при –1) со значением(ми) в самой последовательности.

Определение 38. Идеальным объектом класса будем называть такой набор нуклеотидов <{A | T | G | C}{A | T | G | C}…{A | T | G | C}>, для которого критерий G(M) имеет локальный максимум (при удалении, добавлении любого из значений в этом наборе значение критерия строго уменьшается). Запись {A|T|G|C} означает, что на некотором месте идеального объекта может быть один или несколько нуклеотидов из указанных в фигурных скобках.

Разработана программная система GeneNatClass, реализующая описанный выше подход к построению «естественных» классификаций. Разработанная система апробирована на задачах классификации сайтов сплайсинга и сайтов связывания транскрипционных факторов и показана ее эффективность.

 
Чтобы измерить силу закономерности, мы сравниваем распределение значений целевого признака в таблице, просеянной сквозь сито посылочных признаков, с распределением значений того же целевого признака в исходной таблице данных. Чем сильнее закономерность, тем больше отклонение условного распределения от исходного. Одним из простейших способов измерения такого отклонения является статистика Хи-квадрат. Мы ее и используем, но только в варианте нормированного, так называемого Z-отклонения.

Что касается процедуры поиска и отбора закономерностей, то она устроена по принципу естественного отбора – выживания наиболее приспособленных, в данном случае наиболее сильных закономерностей. Для этого в программе выделяются три коллектора ограниченных размеров для хранения двух промежуточных и одного конечного массива закономерностей. Причем эти коллекторы сортируют вставляемые в них закономерности, так что наиболее сильные всегда оказывались наверху, выталкивая из коллектора наиболее слабые. Z-отклонение самой слабой в коллекторе закономерности является автоматически настраиваемым значением критерия, который определяет порог сохранения наиболее приспособленных.

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

Процесс превращения реальной последовательности в ее идеальный образ протекает по шагам, заканчиваясь в том момент, когда никакое точечное изменение последовательности уже не приводит к увеличению критерия самосогласования закономерностей. Критерий самосогласования закономерностей фиксирует, насколько хорошо предсказываются отдельные нуклеотиды в текущей последовательности по остальным нуклеотидам той же самой последовательности. В процессе идеализации создается матрица, содержащая столько строк, сколько нуклеотидов в последовательности, и четыре столбца, по одному для A, T, G и C. Каждая применимая к текущей последовательности закономерность прибавляет свои четыре предсказания в виде Z-отклонений (для A, T, G и C) в четыре ячейки той строки, которая соответствует целевому признаку. Если одно или больше из этих четырех значений входят в текущую последовательность, то суммарный критерий самосогласования получает вклад, равный сумме предсказаний для всех этих значений. Если же значение входит в последовательность с отрицательным знаком, то и соответствующий вклад тоже берется с минусом. Вхождение с отрицательным знаком означает, что в данной последовательности соответствующего нуклеотида быть не должно. Интерфейс программы естественной классификации приведен на Рис. 32. Программа применялась для классификации донорных сайтов сплайсинга. Были обнаружены закономерности и классы, представленные в третьем окне интерфейса программы.