Введение к работе
Актуальность работы. Во многих прикладных исследованиях встречаются задачи, связанные с полиномиальными моделями и системами полиномиальных уравнений. Например, к таким задачам относится задача нахождения дробного факторного плана и задача нахождения множества моделей, идентифицирумых заданным планом [1] в теории планирования эксперимента.
Микробиология также нуждается в полиномиальных моделях, чтобы по экспериментальным данным находить закономерности в процессах, проистекающих в живых клетках [2]. Возможность прямого наблюдения химических реакций в клетке исключена: реакции происходят с огромной частотой и не поддаются визуальному анализу. Однако, есть техническая возможность измерять уровень присутствия в клетке какого-либо вещества или белка в фиксированные моменты времени. В роли математической модели изучаемого процесса выступает динамическая система с дискретным временем, состояние которой определяется уровнем присутствия различных белков и веществ. Несколько этапов измерений, выполненных подряд, дают таблицу состояний этой системы. Состояние системы меняется в результате химических реакций.
Природу процессов, происходящих в клетке, принято представлять в форме т.н. биохимической сети. Биохимическая сеть кодирует зависимости между объектами-участниками происходящего процесса. Для получения информации о зависимостях требуется определить функции перехода между состояниями. В известных работах в данной области параметры состояния системы представляются дискретными величинами, чаще всего булевыми (есть белок А / нет белка А, есть вещество В / нет вещества В, и т.д.). Функции перехода между состояниями, таким образом, являются функциями в конечном поле. Следовательно, они являются полиномами, и задача сводится к построению полиномиальной модели зависимости состояния системы от состояния её в предыдущий момент времени.
При исследовании клетки нередки ситуации, когда на основании конкретных экспериментальных данных можно построить более одной полиномиальной модели, которая бы согласовалась с этими данными. Важным для исследований является вопрос: как получить все возможные модели, согласующиеся с экспериментальными данными? Аналогичный вопрос поднимается в теории планирования эксперимента: как получить полное множество полиномиальных моделей, идентифицируемым заданным экспериментальным планом? В работах по биохимическим системам, как и в работе [1] по планированию эксперимента, для получения множества полиномиальных моделей используются методы алгебраической статистики, возникшей в 1996 году [3]. В основе этих методов лежит связь полиномиальных моделей с нульмерными полиномиальными идеалами, и с особыми базисами этих идеалов — базисами Грёбнера, которые были придуманы в 1965 г. для символьного решения систем полиномиальных уравнений.
Однако, использование в алгебраической статистике базисов Грёбнера — алгебраической конструкции, предназначенной изначально для решения полиномиальных уравнений — не является естественным. Базисы Грёбнера в общем случае не дают исчерпывающего ответа на поставленный вопрос. Во многих случаях модели, имеющие право на существование, будут пропущены, что признаётся авторами соответствующих методов. В связи с этим является актуальной разработка нового подхода, лишённого указанного недостатка.
Целью диссертационной работы является создание инструмента для разработки и анализа полиномиальных моделей биохимических и других природных процессов. Новый инструмент, в отличие от имеющихся, позволит находить все без исключений полиномиальные модели, согласующиеся с исходными данными.
Математический аппарат, использованный для достижения поставленной цели, имеет в своей основе диаграммы Юнга — простые математические объекты, которые имеют прямое отношение к теории базисов Грёбнера. Например, в статье [4] построение базиса Грёбнера основано на построении диаграммы Юнга, мономы которой порождают факторалгебру нульмерного идеала.
Переход от базисов Грёбнера к диаграммам Юнга позволил разработать алгоритм полного перебора полиномиальных моделей. Создание этого алгоритма было невозможно без решения ряда частных практических задач:
Разработка алгоритмов для осуществления разнообразных операций с диаграммами Юнга.
ями и базисами Грёбнера.
грамм Юнга.
Методы исследования. В работе использованы методы вычислительной коммутативной и компьютерной алгебры, теории базисов Грёбнера, теории представлений, методы математического моделирования, комбинаторные методы дискретной математики, методы вычислительной математики. Для реализации алгоритмов используется среда программирования Common Lisp, а также пакеты компьютерных прикладных программ Maxima и GFan.
На защиту выносятся следующие основные результаты:
Предложен алгоритм, позволяющий эффективно осуществлять построение и анализ полиномиальных моделей различных природных процессов. Алгоритм основан на новом подходе к комбинаторике диаграмм Юнга, также предложенном в диссертации. Детально рассмотрено применение алгоритма в теории биохимических сетей. Решена задача построения биохимической сети процесса, происходящего в живой клетке (такого, как метаболизм лактозы или трансдукция различных сигналов), по набору последовательных дискретных состояний, полученных экспериментально. Доказана корректность работы алгоритма и показан синтетический пример, демонстрирующий его преимущества перед имеющимися алгоритмами.
перимента: решена задача нахождения статистического веера (statistical fan) полиномиальных моделей, идентифицируемых заданным планом эксперимента. (Из предыдущих работ были известны лишь алгоритмы нахождения алгебраического веера, algebraic fan). С помощью численного эксперимента исследованы отличия статистического веера от алгебраического для известных планов экперимента (Бокса- Бенкена, Бокса-Уилсона) в пространствах различной размерности.
В процессе работы над диссертацией обнаружилось, что алгоритмы комбинаторного перебора диаграмм Юнга, изначально созданные автором для исследования полиномиальных моделей, имеют более широкое применение. Список дополнительных результатов диссертации выглядит следующим образом:
размерности, соответствующих слабодопустимым, выпуклым и стро- годопустимым конечным мономиальным упорядочениям; найдено и доказано соответствие между конечными строгодопустимыми упорядочениями и начальными сегментами сигнатурных последовательностей.
сального базиса Грёбнера (EUGB): конструкции, не зависящей от строгого упорядочения мономов. Разработан алгоритм вычисления
EUGB. Доказано несовпадение в общем случае UGB с EUGB. Обнаружено явление «сильной ненётеровости» полиномиальной редукции относительно набора полиномов, не зависящее от выбора конкретного полинома для деления.
Реализован алгоритм порождения случайных двумерных диаграмм Юнга, распределённых по мере Планшереля. Проведены эксперименты по нахождению мат. ожидания и максимума нормализованной размерности неприводимых представлений.
Реализован алгоритм порождения случайных ^-мерных диаграмм Юнга, распределённых по мере Ричардсона. Предложен численный метод вычисления предельной формы многомерных диаграмм Юнга, а также численный метод анализа сходимости фронта диаграммы к предельной форме.
Научная новизна. Следующие результаты, полученные в диссертации, являются новыми:
намической системы, имеющих право на существование при полученном наборе результатов измерений. Аналогичный алгоритм предложен для нахождения полного веера полиномиальных моделей, идентифицируемых заданным планом эксперимента. Существовавшие ранее алгоритмы не давали в общем случае полного результата.
лиц Юнга произвольной размерности, соответствующих выпуклым и строгодопустимым конечным мономиальным упорядочениям.
pa (EUGB) и разработан алгоритм вычисления EUGB.
дукции.
Теоретическая и практическая значимость. В руках исследователей (например, микробиологов) должен быть инструмент построения полиномиальных моделей, выдающий полный, а не частичный результат, и такой инструмент был создан в диссертации. Недостатки предыдущих инструментов признаются исследователями в их статьях прошлых лет.
Теоретическая значимость проделанной работы заключается прежде всего в том, что разработанные алгоритмы применяются и могут применяться в дальнейшем для установления и проверки различных гипотез из теории представлений и теории базисов Грёбнера; так, используя метод, предложенный в диссертации, автору удалось найти контрпример к оши-
бочно доказанной теореме в препринте статьи [5].
Другим значимым теоретическим результатом работы можно считать открытие явления «сильной ненётеровости».
Апробация работы. Основные результаты работы докладывались и обсуждались на;
Международной конференции по полиномиальной компьютерной алгебре (PCA) (ММИ имени Эйлера, Санкт-Петербург, 2008, 2009, 2011);
на, 2008);
Санкт-Петербург, 2009). Санкт-Петербург, 2009) ре (Тамбов, 2010)
Достоверность результатов. Полученные в диссертации результаты обоснованы корректным использованием математических методов вычислительной коммутативной алгебры и комбинаторики. Достоверность подтверждается сопоставлением с результатами, доступными в открытой печати.
Публикации. Материалы диссертации опубликованы в 5 статьях в рецензируемых журналах [1-5], рекомендованных ВАК РФ для опубликования результатов кандидатских диссертаций.
Личный вклад автора. Работы [1, 3, 4] выполнены в соавторстве.
Вклад соискателя в них заключается в:
граммах Юнга.
Структура и объем диссертации. Диссертация состоит из введения, пяти глав, заключения, списка цитируемой литературы и трёх приложений. Объем диссертации составляет 143 страницы (из них 13 занимают приложения). Кроме основного текста диссертация содержит 24 рисунка и список литературы из 89 наименований.
