Математической основой многих алгоритмов, использующихся для анализа данных и поиска закономерностей (продукции знаний), служит теория полезности для принятия решений, представленная, например, в работах Фишберна (Фишберн, 1978). Этот подход показал свою эффективность для выявления контекстных, конформационных и физико-химических характеристик регуляторных геномных последовательностей, значимых для их функционирования (Пономаренко и др., 1991; Бенюх и др., 1989; Кель и др., 1989; Kel et al., 1993). К достоинствам метода относятся: (1) возможность автоматического анализа данных при выявлении значимых структурно-функциональных характеристик РГП и построении методов их распознавания (автоматическая продукция знаний); (2) устойчивость получаемых результатов и высокая степень их воспроизводимости на контрольных выборках данных; (3) наличие статистической меры значимости (полезности) выявляемых характеристик; (4) интерпретируемость получаемых результатов.
Распределения конформационных и физико-химических свойств строятся для последовательностей позитивной выборки (функциональные сайты) и негативной выборки (случайные последовательности того же нуклеотидного состава, что и исследуемые сайты). При оценке полезности вычисляется ряд статистических и эмпирических мер различия выборочных распределений (Пономаренко и Орлов, 1989; Ponomarenko and Orlov, 1990). Если различие между распределениями оказывается значимым, то этому различию присваивается положительный вес от 0 до 1, в противном случае выбирается отрицательный вес от -1 до 0. Обобщённое различие между распределениями вычисляется как среднее по всем сравнениям. Вычисленное таким образом значение U(k) представляет собой интегральную характеристику сравнения дискриминирующей способности k-го свойства ДНК по району (k=1,2,... – номер исследуемого физико-химического свойства из таблицы свойств). Величина U называется полезностью. Она объединяет как оценки точности распознавания, так и оценки устойчивости результатов на контроле (Пономаренко и Орлов, 1989). Величина U обладает следующими свойствами:
если U(k) < 0, то k-ое свойство не значимо;
если U(k) > U(q) ³ 0, то k-ое свойство более значимо, чем q-ое.
Такой подход дал хорошие результаты как интегральное средство для объединения разнородных методов предсказания и повышения итоговой точности (Пономаренко и др., 1991; Бенюх и др., 1989; Кель и др., 1989; Kel et al., 1993).
Началом применения нейронных сетей в биоинформатике можно считать работу (Qian and Sejnowski, 1988). В ней был представлен метод предсказания вторичной структуры глобулярных белков на основе модели нейронной сети. Нейросетевая модель обучалась на известных структурах белков для предсказания вторичной структуры локальной последовательности аминокислот. Средняя точность на контрольной выборке белков составила 64.3% для трех типов вторичной структуры (a-спирали, b-листы и клубок). Такая точность была максимальна для всех существовавших ранее методов.
Нейронные сети используются для
поиска функциональных сайтов и сигналов в
банках данных генетических
последовательностей (Wu, 1997). Нейронная сеть
представляет собой совокупность
иерархически соединенных простых
вычислительных элементов (нейронов) (Рис.).
В простейшем случае нейрон осуществляет скалярное умножение вектора входных сигналов на вектор синаптических весов, к произведению добавляется смещение. Над суммой выполняется нелинейное преобразование (передаточная функция), результат которого есть выходной сигнал нейрона.
Применение нейронной сети для поиска промоторных районов в E.coli было описано в статье (Lukashin et al., 1989); показано, что можно идентифицировать от 94 до 99% промоторных последовательностей E.coli. В целом, нейронные сети широко используются для предсказания функциональных сайтов в ДНК (Milanesi et al., 1996; Reese, 2001), вторичных структур белков (Cai, 2002), пространственных белковых структур (Pollastri and Baldi, 2002; Ahmad and Gromiha, 2002) (см. также таблицы по Интернет-ресурсам предсказания структуры генов в Приложении). К достоинствам подхода следует отнести высокую точность предсказания, к недостаткам – недостаточную интерпретируемость получаемых моделей с биологической точки зрения.Поиск закономерностей в базах данных (Data Mining) все более входит в традиционные области биоинформатики (Rebhan et al., 1998; Narasimhan et al., 2002; Yeh et al., 2003; Liu and Wong, 2003; Huang et al., 2004). Это связано не только с лавинообразным ростом накопленной информации, но и с методиками, позволяющими получить качественно новые знания (Luscombe, 2001; Bertone and Gerstein, 2001). Применение методов Data Mining в молекулярной биологии включает анализ паттернов и предсказание функции белков (Baxter and Fetrow, 2001; Jonassen et al., 2002; Narasimhan et al., 2002), реконструкцию филогенетических деревьев (Jakobsen et al., 2001) исследование химических молекулярных структур (Cheng et al., 2002), анализ данных генной экспрессии по ДНК-чипам (Bumm et al., 2002). В качестве примеров можно привести анализ банка данных белков (Kretschmann et al., 2001). В этой работе стандартные алгоритмы анализа данных (С4.5) были применены для получения знаний по аннотациям ключевых слов в банке данных SWISS-PROT. Было сгенерировано более 11 тысяч правил для аннотации неизвестных последовательностей. Правила относились к таксономии организмов, в которых найден белок и некоторым паттернам их аминокислотных последовательностей. Показано, что 33% аннотаций по ключевым словам могут быть восстановлены с ошибкой 1.5%.
В работе (Sebban et al., 2002) методы анализа данных применялись к анализу пространственно разделенных олигонуклеотидов при экспериментах по генотипированию Mycobacterium tuberculosis. В статье освещен процесс получения знаний с помощью алгоритма вывода правил C4.5, использующего позиционированные логические правила.Одним из основных типов данных, используемым в базах данных, является числовое представление признака. Объекты в этом случае представляются наборами значений признаков. В работах (Витяев, 1991; Kovalerchuk and Vityaev, 2000) предложено использовать Теорию Измерений для представления этого типа данных в языке логики первого порядка и тем самым в реляционном виде. В Теории Измерений показано, что числовые значения величин определяются отношениями (Krantz et al., 1971, 1989, 1990). Следуя Теории Измерений, было показано, как наиболее известные способы представления данных – таблицы объект-признак, матрицы упорядочений и близости, множественные и парные сравнения, – могут быть представлены в языке первого порядка (Витяев, 1991; Kovalerchuk and Vityaev, 2000). Этот подход использован далее в настоящем проекте.
Методы KDD&DM, работающие в языке логики первого порядка, называются реляционными DM методами (Kovalerchuk and Vityaev, 2000). Реляционные DM методы позволяют снять ограничения стандартных DM методов, сформулировать в языке первого порядка знание о предметной области (Background Knowledge), расширить понятие типа данных (Data Type), за счет выразительной возможности языка первого порядка; использовать Теорию Измерений для представления разнородных величин в языке первого порядка, включая величины отношений, частичного порядка, и др.; ввести понятие типов правил (Rule Type) как типа гипотез, которые могут проверяться в базах данных.
В качестве типов правил могут быть сформулированы практически все типы гипотез, проверяемые различными методами анализа данных. Например, классы кусочно-линейных правил или "m-of-n" правил, используемых нейронными сетями; классы правил для любого типа деревьев; логические решающие правила; правила, проверяемые в индуктивном логическом программировании; булевы функции и т.д. (Витяев и Москвитин, 1993).
К реляционным DM методам относятся также методы индуктивного логического программирования (Inductive Logic Programming, ILP), работающие в языке первого порядка. В статье (Friedman et al., 1999) представлена теория вероятностных реляционных моделей (probabilistic relational models, PRMs в англоязычной литературе), которая позволяет свойствам (характеристикам) объектов зависеть вероятностным образом от других свойств этого объекта либо родственных объектов. В статье на примере задач генетики отмечается, что вероятностные реляционные модели (1) значительно более выразительны с точки зрения интерпретируемости, чем стандартные модели, (2) позволяют использовать реляционные базы данных без преобразования реляционных данных в единую таблицу. Действительно, основное ограничение применению индуктивного логического программирования – детерминистская природа открываемых правил (Kovalerchuk and Vityaev, 2000), поскольку в естественнонаучных областях знаний, взаимосвязи имеют не детерминистский, а вероятностный характер.