Полиномиальные модели, основанные на диаграммах Юнга

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

Микробиология также нуждается в полиномиальных моделях, чтобы по экспериментальным данным находить закономерности в процессах, проистекающих в живых клетках [2]. Возможность прямого наблюдения химических реакций в клетке исключена: реакции происходят с огромной частотой и не поддаются визуальному анализу. Однако, есть техническая возможность измерять уровень присутствия в клетке какого-либо вещества или белка в фиксированные моменты времени. В роли математической модели изучаемого процесса выступает динамическая система с дискретным временем, состояние которой определяется уровнем присутствия различных белков и веществ. Несколько этапов измерений, выполненных подряд, дают таблицу состояний этой системы. Состояние системы меняется в результате химических реакций.

Природу процессов, происходящих в клетке, принято представлять в форме т.н. биохимической сети. Биохимическая сеть кодирует зависимости между объектами-участниками происходящего процесса. Для получения информации о зависимостях требуется определить функции перехода между состояниями. В известных работах в данной области параметры состояния системы представляются дискретными величинами, чаще всего булевыми (есть белок, А / нет белка А, есть вещество В / нет вещества В, и т. д.). Функции перехода между состояниями, таким образом, являются функциями в конечном поле. Следовательно, они являются полиномами, и задача сводится к построению полиномиальной модели зависимости состояния системы от состояния её в предыдущий момент времени.

При исследовании клетки нередки ситуации, когда на основании конкретных экспериментальных данных можно построить более одной полиномиальной модели, которая бы согласовалась с этими данными. Важным для исследований является вопрос: как получить все возможные модели, согласующиеся с экспериментальными данными? Аналогичный вопрос поднимается в теории планирования эксперимента: как получить полное множество полиномиальных моделей, идентифицируемым заданным экспериментальным планом? В работах по биохимическим системам, как и в работе [1] по планированию эксперимента, для получения множества полиномиальных моделей используются методы алгебраической статистики, возникшей в 1996 году [3]. В основе этих методов лежит связь полиномиальных моделей с нульмерными полиномиальными идеалами, и с особыми базисами этих идеалов — базисами Грёбнера, которые были придуманы в 1965 г. для символьного решения систем полиномиальных уравнений.

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

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

Математический аппарат, использованный для достижения поставленной цели, имеет в своей основе диаграммы Юнга — простые математические объекты, которые имеют прямое отношение к теории базисов Грёб-нера. Например, в статье [4] построение базиса Грёбнера основано на построении диаграммы Юнга, мономы которой порождают факторалгебру нульмерного идеала.

Переход от базисов Грёбнера к диаграммам Юнга позволил разработать алгоритм полного перебора полиномиальных моделей. Создание этого алгоритма было невозможно без решения ряда частных практических задач:

• Разработка алгоритмов для осуществления разнообразных операций с диаграммами Юнга. в Исследование связи диаграмм Юнга с мономиальными упорядочениями и базисами Грёбнера.

• Формулирование задач алгебраической статистики в терминах диаграмм Юнга.

Методы исследования. В работе использованы методы вычислительной коммутативной и компьютерной алгебры, теории базисов Грёбнера, теории представлений, методы математического моделирования, комбинаторные методы дискретной математики, методы вычислительной математики. Для реализации алгоритмов используется среда программирования Common Lisp, а также пакеты компьютерных прикладных программ Maxima и GFan.

На защиту выносятся следующие основные результаты:

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

• Разработанный алгоритм применен также в теории планирования эксперимента: решена задача нахождения статистического веера (statistical fan) полиномиальных моделей, идентифицируемых заданным планом эксперимента. (Из предыдущих работ были известны лишь алгоритмы нахождения алгебраического веера, algebraic fan). С помощью численного эксперимента исследованы отличия статистического веера от алгебраического для известных планов экперимента (Бокса-Бенкена, Бокса-Уилсона) в пространствах различной размерности.

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

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

• В теорию базисов Грёбнера введено понятие расширенного универсального базиса Грёбнера (EUGB): конструкции, не зависящей от строгого упорядочения мономов. Разработан алгоритм вычисления EUGB. Доказано несовпадение в общем случае UGB с EUGB. Обнаружено явление «сильной ненётеровости» полиномиальной редукции относительно набора полиномов, не зависящее от выбора конкретного полинома для деления.

• Реализован алгоритм порождения случайных двумерных диаграмм Юнга, распределённых по мере Планшереля. Проведены эксперименты по нахождению мат. ожидания и максимума нормализованной размерности неприводимых представлений.

• Реализован алгоритм порождения случайных d-мерных диаграмм Юнга, распределённых по мере Ричардсона. Предложен численный метод вычисления предельной формы многомерных диаграмм Юнга, а также численный метод анализа сходимости фронта диаграммы к предельной форме.

Научная новизна. Следующие результаты, полученные в диссертации, являются новыми:

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

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

• Введено новое понятие расширенного универсального базиса Грёбне-ра (EUGB) и разработан алгоритм вычисления EUGB. в Обнаружено явление «сильной ненётеровости» полиномиальной редукции.

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

Теоретическая значимость проделанной работы заключается прежде всего в том, что разработанные алгоритмы применяются и могут применяться в дальнейшем для установления и проверки различных гипотез из теории представлений и теории базисов Грёбнератак, используя метод, предложенный в диссертации, автору удалось найти контрпример к ошибочно доказанной теореме в препринте статьи [5].

Другим значимым теоретическим результатом работы можно считать открытие явления «сильной ненётеровости».

Апробация работы. Основные результаты работы докладывались и обсуждались на:

• Международной конференции по полиномиальной компьютерной алгебре (РСА) (ММИ имени Эйлера, Санкт-Петербург, 2008, 2009, 2011);

• Международном рабочем совещании по компьютерной алгебре (Дубна, 2008);

• Семинаре по теории представлений и динамическим системам (ПОМИ, Санкт-Петербург, 2009).

• Научном семинаре кафедры прикладной математики (ФМФ СПбГПУ,.

Санкт-Петербург, 2009).

• Международной конференции по параллельной компьютерной алгебре (Тамбов, 2010) в Научном семинаре в РУДН (Москва, 2012).

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

Публикации. Материалы диссертации опубликованы в 5 статьях в рецензируемых журналах [6−10], рекомендованных ВАК РФ для опубликования результатов кандидатских диссертаций.

Личный вклад автора. Работы [6, 8, 9] выполнены в соавторстве. Вклад соискателя в них заключается в:

• Разработке и реализации алгоритмов.

• Проведении численного моделирования случайных процессов на диаграммах Юнга.

Структура и объем диссертации

Диссертация состоит из введения, пяти глав, заключения, списка цитируемой литературы и трёх приложений. Объем диссертации составляет 143 страницы (из них 13 занимают приложения). Кроме основного текста диссертация содержит 24 рисунка и список литературы из 89 наименований.

Основные результаты, полученные в диссертации.

Итоги сделанной работе уже были подведены во вступлении, воспроизведём их здесь:

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

• Разработанный алгоритм применен также в теории планирования эксперимента: Решена задача нахождения полного веера (statistical fan) полиномиальных моделей, идентифицируемых заданным планом эксперимента. (Из предыдущих работ были известны лишь алгоритмы нахождения алгебраического веера, algebraic fan). С помощью численного эксперимента исследованы отличия полного веера от алгебраического для известных экспериментальных планов (Бокса-Бенкена, Бокса-Уилсона) в пространствах различной размерности.

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

• В теорию базисов Грёбнера введено понятие расширенного универсального базиса Грёбнера (Е11СВ): конструкции, не зависящей от строгого упорядочения мономов. Разработан алгоритм вычисления Е1ЮВ. Доказано несовпадение в общем случае 1ЮВ с Е11СВ. Обнаружено явление «сильной ненётеровости» полиномиальной редукции относительно набора полиномов, не зависящее от выбора конкретного полинома для деления. Это явление, имеющее место при некоторых недопустимых упорядочениях, было названо «сильной ненёте-ровостыо». Обнаруженный результат является уточнением результата [31] о «слабой» ненётеровости.

• Реализован алгоритм порождения случайных двумерных диаграмм Юнга, распределённых по мере Планшереля. Повторены и расширены до больших п эксперименты по нахождению мат. ожидания [67] и максимума [66] нормализованной размерности неприводимых представлений Зп.

• Реализован алгоритм порождения случайных ¿—мерных диаграмм Юнга, распределённых по мере Ричардсона. Предложен численный метод вычисления предельной формы многомерных диаграмм Юнга, а также численный метод анализа сходимости фронта диаграммы к предельной форме.

Благодарности.

Автор выражает свою искреннюю признательность H.H. Васильеву за поставленные задачи и чуткое руководство, за постоянную поддержку и математическую интуицию.

Неоценимой в процессе работы над четвёртой главой была помощь.

A. М. Вершика, его кругозор, большое количество идей и богатейшая библиотека собственных публикаций, благодаря которой автор теперь испытывает живейший интерес к теории представлений.

Третья глава не была бы написана без К. Усевича, благодаря которому автор познакомился с теорией планирования эксперимента и узнал о её связи с полиномиальной алгеброй.

Автор благодарит также: С. Шлосмана и А. Буфетова за любезно предоставленные статьиЮ. А. Блинкова, В. П. Гердта, В. В. Корняка, А. Зобнина, Г. И. Малашонка, Е. Горячко, Ф. Петрова, Н. Цилевич, В. А. Пальмова, С. В. Стахова, A.A. Иванкова за ценные замечания и дискуссии на докладах и вне ихВ. Е. Клавдиева, И. В. Штурца, С. Ю. Жукова, Ф. А. Новикова,.

B. А. Галинского и Т. И. Курсиш за годы учёбы и участие.

За заботу и развитие автор признателен родителям, всем родственникам и отдельно дяде Мише и семье Минаевых.

Автор передаёт привет друзьям по походам: Н. Комлеву, И. Васильевой, их дочери Надежде, А. Бавыкину, В. Иващенко, В. Куликову, JI. Ма-лофеевой, В. Рыбко.

Автор бы ничего не сделал без поддержки своих друзей. Алексей, Валя, Денис, Дима, Женя, Игорь, Коля, Олег, Паша, спасибо вам.

Автор благодарен свой жене Даше за доброту, терпение и постоянную помощь во время работы.

Благодарности за программы.

Об этом не принято говорить,'но программы действительно иногда помогают людям, и подчас их помошь незаменима. Автор благодарен создателям:

SBCL — за прекрасную реализацию Common LispGNU Emacs и SLIME — за текстовый редактор и среду разработкиШрифта Terminus и цветовой схемы charcoal-black — за то, что не болят глаза;

GFan — за знакомство с удивительными свойствами базисов Грёбне-ра;

Т^Ки ВТ^К— за компьютерную типографию;

Debian GNU/Linux — за операционную систему, на которой работает всё вышеперечисленное;

Google, Google Books, Google Scholar, Gigapedia.org, MathNet.ru, сайта препринтов ПОМИ — за возможность ходить в библиотеку, не вставая с кресла.

Заключение

.