Все выпуски

Статья посвящена применению методов математического анализа, поиска паттернов и изучения состава нуклеотидов в последовательностях ДНК на геномном уровне. Изложены новые методы математической биологии, которые позволили обнаружить и отобразить скрытую упорядоченность генетических нуклеотидных последовательностей, находящихся в клетках живых организмов. Исследования основаны на работах по алгебраической биологии доктора физико-математических наук С. В. Петухова, которым впервые были введены и обоснованы новые алгебры и гиперкомплексные числовые системы, описывающие генетические явления. В данной работе описана новая фаза развития матричных методов в генетике для исследования свойств нуклеотидных последовательностей (и их физико-химических параметров), построенная на принципах конечной геометрии. Целью исследования является демонстрация возможностей новых алгоритмов и обсуждение обнаруженных свойств генетических молекул ДНК и РНК. Исследование включает три этапа: параметризация, масштабирование и визуализация. Параметризация — определение учитываемых параметров, которые основаны на структурных и физико-химических свойствах нуклеотидов как элементарных составных частей генома. Масштабирование играет роль «фокусировки» и позволяет исследовать генетические структуры в различных масштабах. Визуализация включает выбор осей координатной системы и способа визуального отображения. Представленные в работе алгоритмы выдвигаются на роль расширенного инструментария для развития научно-исследовательского программного обеспечения анализа длинных нуклеотидных последовательностей с возможностью отображения геномов в параметрических пространствах различной размерности. Одним из значимых результатов исследования является то, что были получены новые биологически интерпретируемые критерии классификации геномов различных живых организмов для выявления межвидовых взаимосвязей. Новая концепция позволяет визуально и численно оценить вариативность физико-химических параметров нуклеотидных последовательностей. Эта концепция также позволяет обосновать связь параметров молекул ДНК и РНК с фрактальными геометрическими мозаиками, обнаруживает упорядоченность и симметрии полинуклеотидов и их помехоустойчивость. Полученные результаты стали обоснованием для введения новых научных терминов: «генометрия» как методология вычислительных стратегий и «генометрика» как конкретные параметры того или иного генома или нуклеотидной последовательности. В связи с результатами исследования затронуты вопросы биосемиотики и уровни иерархичности организации живой материи.

The article is devoted to the application of various methods of mathematical analysis, search for patterns and studying the composition of nucleotides in DNA sequences at the genomic level. New methods of mathematical biology that made it possible to detect and visualize the hidden ordering of genetic nucleotide sequences located in the chromosomes of cells of living organisms described. The research was based on the work on algebraic biology of the doctor of physical and mathematical sciences S. V. Petukhov, who first introduced and justified new algebras and hypercomplex numerical systems describing genetic phenomena. This paper describes a new phase in the development of matrix methods in genetics for studying the properties of nucleotide sequences (and their physicochemical parameters), built on the principles of finite geometry. The aim of the study is to demonstrate the capabilities of new algorithms and discuss the discovered properties of genetic DNA and RNA molecules. The study includes three stages: parameterization, scaling, and visualization. Parametrization is the determination of the parameters taken into account, which are based on the structural and physicochemical properties of nucleotides as elementary components of the genome. Scaling plays the role of “focusing” and allows you to explore genetic structures at various scales. Visualization includes the selection of the axes of the coordinate system and the method of visual display. The algorithms presented in this work are put forward as a new toolkit for the development of research software for the analysis of long nucleotide sequences with the ability to display genomes in parametric spaces of various dimensions. One of the significant results of the study is that new criteria were obtained for the classification of the genomes of various living organisms to identify interspecific relationships. The new concept allows visually and numerically assessing the variability of the physicochemical parameters of nucleotide sequences. This concept also allows one to substantiate the relationship between the parameters of DNA and RNA molecules with fractal geometric mosaics, reveals the ordering and symmetry of polynucleotides, as well as their noise immunity. The results obtained justified the introduction of new terms: “genometry” as a methodology of computational strategies and “genometrica” as specific parameters of a particular genome or nucleotide sequence. In connection with the results obtained, biosemiotics and hierarchical levels of organization of living matter are raised.

Острые респираторные инфекции представляют собой серьезную проблему общественного здравоохранения, поскольку являются одной из причин заболеваемости и смерти во многих странах. В связи с этим существует большой интерес к разработке моделей и методов, позволяющих моделировать распространение этих инфекций в сообществах с целью контроля вспышек и предотвращения их распространения. Агентные модели (АМ) являются одним из важнейших инструментов эпидемиологических исследований для моделирования динамики эпидемий в реальных популяциях, но они сталкиваются со значительными трудностями, связанными с вычислительной сложностью при их использовании и калибровке эпидемиологических данных, поскольку оценка параметров обычно требует многократного моделирования в больших пространствах параметров для определения правдоподобных значений ключевых эпидемиологических показателей. В данной статье рассматривается проблема снижения вычислительных ограничений в обратной задаче калибровки АМ для моделирования распространения респираторных инфекций в Санкт-Петербурге. В статье предлагается применение суррогатного машинного обучения для связи траекторий эпидемий с лежащими в их основе эпидемиологическими параметрами, что позволяет быстро выводить оценки параметров на основе наблюдаемых эпидемических данных. Это достигается путем формулировки задачи калибровки АМ по эпидемиологическим данным как задачи контролируемого обучения, в которой последовательности, извлеченные из эпидемиологических траекторий, связываются с базовыми эпидемиологическими параметрами. Исследование было основано на оценке эффективности моделирования последовательностей на основе внимания, вероятностного глубокого обучения и распределительной регрессии для вывода оценок параметров из усеченных последовательностей эпидемических траекторий. Экспериментальные оценки продемонстрировали эффективность данного подхода и его практическое и простое применение. Результаты также указали на превосходство моделирования последовательностей на основе внимания, поскольку оно показало более стабильную производительность по всем метрикам и горизонтам, обеспечивая точную оценку параметров и достоверное количественное определение неопределенности. Моделирование распределительной регрессии также показало хорошую производительность, особенно с точки зрения точности точек, в то время как вероятностное глубокое обучение показало плохую производительность, особенно при более длительных входных горизонтах.

Acute respiratory infections are a major public health concern because they are the leading cause of illness and death in many countries. Therefore, there is great interest in developing models and methods capable of modeling the spread of these infections within communities, with the aim of controlling outbreaks and preventing their spread. Agent-based models (ABM) are one of the most important tools in epidemiological research for modeling epidemic dynamics in realistic populations, but they face significant challenges in terms of computational complexity in their operation and calibration of epidemiological data, as parameter estimation typically requires repeated simulations across large parameter spaces to determine plausible values for key epidemiological parameters. This paper addresses the problem of alleviating computational constraints in the inverse problem of calibrating an ABM model for simulating the spread of respiratory infections in Saint Petersburg. The paper proposes the application of machine learning surrogate to link epidemic trajectories to underlying epidemiological parameters, enabling them to quickly infer parameter estimates from observed epidemic data. This is done by formulating the task of calibrating ABMs against epidemiological data as a supervised learning problem, where sequences extracted from epidemiological trajectories are associated with underlying epidemiological parameters. The research was based on evaluating the performance of attention-based sequence modeling, probabilistic deep learning, and distributional regression for inferring parameter estimates from truncated sequences of epidemic trajectories. Experimental evaluations have demonstrated the effectiveness of this approach and its practical and straightforward application. The results also indicated the superiority of attention-based sequence modeling, as it showed more consistent performance across metrics and horizons in accurate parameter estimation and credible uncertainty quantification. Distributional regression modeling also showed good performance with specific strengths in point accuracy while probabilistic deep learning performed poorly, especially at longer input horizons.

В рамках данной работыбы ла продемонстрирована возможность использования характеристик профилей электростатического потенциала вдоль последовательностей ДНК для определения их функционального класса. Построенымо дели, позволяющие разделять промоторные и непромоторные последовательности (случайные бернуллиевские, кодирующие и псевдопромоторы) с точностью порядка 83–85%. Определены наиболее значимые участки для такого разделения, по-видимому играющие важную роль при ДНК-полимеразном узнавании.

The article is devoted to the idea of using physical properties of DNA instead of sequence along for the aspect of accurate search and annotation of various prokaryotic genomic regions. Particulary, the possibility to use electrostatic potential distribution around DNA sequence as a classifier for identification of a few functional DNA regions was demonstrated. A number of classification models was built providing discrimination of promoters and non-promoter regions (random sequences, coding regions and promoter-like sequences) with accuracy value about 83–85%. The most valueable regions for the discrimination were determined and expected to play a certain role in the process of DNA-recognition by RNA-polymerase.

Исследование влияния внешних полей на живые системы — одно их наиболее интересных и быстро развивающихся направлений современной биофизики. Однако механизмы такого воздействия до сих пор не совсем ясны. Один из подходов к изучению этого вопроса связывают с моделированием взаимодействия внешних полей с внутренней подвижностью биологических объектов. В настоящей работе этот подход применяется для исследования влияния внешних полей на движение локальных конформационных возмущений — кинков в молекуле ДНК. Понимая и учитывая, что в целом такая задача тесно связана с задачей о механизмах регуляции процессов жизнедеятельности клеток и клеточных систем, мы поставили задачу — исследовать физические механизмы, регулирующие движение кинков, а также ответить на вопрос, могут ли постоянные и периодические поля выступать в роли регуляторов этого движения. В работе рассматривается самый общий случай, когда постоянные и периодические поля включаются и выключаются асинхронно. Детально исследованы три варианта асинхронного включения/выключения. В первом варианте интервалы (или диапазоны) действия постоянного и периодического полей не перекрываются, во втором — перекрываются, а третьем — интервалы вложены друг в друга. Расчеты выполнялись для последовательности плазмиды pTTQ18. Движение кинков моделировалось уравнением МакЛафлина–Скотта, а коэффициенты этого уравнения рассчитывались в квазиоднородном приближении. Численные эксперименты показали, что постоянные и периодические поля оказывают существенное влияние на характер движения кинка и регулируют его. Так, включение постоянного поля приводит к быстрому увеличению скорости кинка и установлению стационарной скорости движения, а включение периодического поля приводит к установившимся колебаниям кинка с частотой внешнего периодического поля. Показано, что поведение кинка зависит от взаимного расположения диапазонов действия внешних полей. Причем, как оказалось, события, происходящие в одном диапазоне, могут оказывать влияние на события в другом временном диапазоне даже в том случае, когда диапазоны расположены достаточно далеко друг от друга. Показано, что перекрывание диапазонов действия постоянного и периодического полей приводит к значительному увеличению пути, проходимому кинком до полной остановки. Максимальный рост пути наблюдается в случае вложенных друг в друга диапазонов. В заключении обсуждается вопрос о том, как полученные модельные результаты могут быть связаны с важнейшей задачей биологии — задачей о механизмах регуляции процессов жизнедеятельности клеток и клеточных систем.

Investigation of the influence of external fields on living systems is one of the most interesting and rapidly developing areas of modern biophysics. However, the mechanisms of such an impact are still not entirely clear. One approach to the study of this issue is associated with modeling the interaction of external fields with internal mobility of biological objects. In this paper, this approach is used to study the effect of external fields on the motion of local conformational distortions — kinks, in the DNA molecule. Realizing and taking into account that on the whole this task is closely connected with the problem of the mechanisms of regulation of vital processes of cells and cellular systems, we set the problem — to investigate the physical mechanisms regulating the motion of kinks and also to answer the question whether permanent and periodic fields can play the role of regulators of this movement. The paper considers the most general case, when constant and periodic fields are switching on and off asynchronously. Three variants of asynchronous switching on/off are studied in detail. In the first variant, the time intervals (or diapasons) of the actions of the constant and periodic fields do not overlap, in the second — overlap, and in the third — the intervals are putting in each other. The calculations were performed for the sequence of plasmid pTTQ18. The kink motion was modeled by the McLaughlin–Scott equation, and the coefficients of the equation were calculated in a quasi-homogeneous approximation. Numerical experiments showed that constant and periodic fields exert a significant influence on the character of the kink motion and regulate it. So the switching on of a constant field leads to a rapid increase of the kink velocity and to the establishment of a stationary velocity of motion, and the switching on of a periodic field leads to the steady oscillations of the kink with the frequency of the external periodic field. It is shown that the behavior of the kink depends on the mutual arrangement of the diapasons of the action of the external fields. As it turned out, events occurring in one of the two diapasons can affect the events in the other diapason, even when the diapasons are sufficiently far apart. It is shown that the overlapping of the diapasons of action of the constant and periodic fields leads to a significant increase in the path traversed by the kink to a complete stop. Maximal growth of the path is observed when one diapason is putting in each other. In conclusion, the question of how the obtained model results could be related to the most important task of biology — the problem of the mechanisms of regulation of the processes of vital activity of cells and cellular systems is discussed.

Решение общей проблемы информационного взрыва связано с системами автоматической обработки цифровых данных, включая их распознавание, сортировку, содержательную обработку и представление в виде, приемлемом для восприятия человеком. Естественным решением является создание интеллектуальных систем извлечения знаний из неструктурированной информации. При этом явные успехи в области обработки структурированных данных контрастируют со скромными достижениями в области анализа неструктурированной информации, в частности в задачах обработки текстовых документов. В настоящее время данное направление находится в стадии интенсивных исследований и разработок. Данная работа представляет собой системный обзор международных и отечественных публикаций, посвященных ведущему тренду в области автоматической обработки потоков текстовой информации, а именно интеллектуальному анализу текстов или Text Mining (TM). Рассмотрены основные задачи и понятия TM, его место в области проблемы искусственного интеллекта, а также указаны сложности при обработке текстов на естественном языке (NLP), обусловленные слабой структурированностью и неоднозначностью лингвистической ин- формации. Описаны стадии предварительной обработки текстов, их очистка и селекция признаков, которые, наряду с результатами морфологического, синтаксического и семантического анализа, являются компонентами TM. Процесс интеллектуального анализа текстов представлен как отображение множества текстовых документов в «знания», т.е. в очищенную от избыточности и шума совокупность сведений, необходимых для решения конкретной прикладной задачи. На примере задачи трейдинга продемонстрирована формализация принятия торгового решения, основанная на совокупности аналитических рекомендаций. Типичными примерами TM являются задачи и технологии информационного поиска (IR), суммаризации текста, анализа тональности, классификации и кластеризации документов и т. п. Общим вопросом для всех методов TM является выбор типа словоформ и их производных, используемых для распознавания контента в последовательностях символов NL. На примере IR рассмотрены типовые алгоритмы поиска, основанные на простых словоформах, фразах, шаблонах и концептах, а также более сложные технологии, связанные с дополнением шаблонов синтаксической и семантической информацией. В общем виде дано описание механизмов NLP: морфологический, синтаксический, семантический и прагматический анализ. Приведен сравнительный анализ современных инструментов TM, позволяющий осуществить выбор платформы, исходя из особенности решаемой задачи и практических навыков пользователя.

In general, solving the information explosion problem can be delegated to systems for automatic processing of digital data. These systems are intended for recognizing, sorting, meaningfully processing and presenting data in formats readable and interpretable by humans. The creation of intelligent knowledge extraction systems that handle unstructured data would be a natural solution in this area. At the same time, the evident progress in these tasks for structured data contrasts with the limited success of unstructured data processing, and, in particular, document processing. Currently, this research area is undergoing active development and investigation. The present paper is a systematic survey on both Russian and international publications that are dedicated to the leading trend in automatic text data processing: Text Mining (TM). We cover the main tasks and notions of TM, as well as its place in the current AI landscape. Furthermore, we analyze the complications that arise during the processing of texts written in natural language (NLP) which are weakly structured and often provide ambiguous linguistic information. We describe the stages of text data preparation, cleaning, and selecting features which, alongside the data obtained via morphological, syntactic, and semantic analysis, constitute the input for the TM process. This process can be represented as mapping a set of text documents to «knowledge». Using the case of stock trading, we demonstrate the formalization of the problem of making a trade decision based on a set of analytical recommendations. Examples of such mappings are methods of Information Retrieval (IR), text summarization, sentiment analysis, document classification and clustering, etc. The common point of all tasks and techniques of TM is the selection of word forms and their derivatives used to recognize content in NL symbol sequences. Considering IR as an example, we examine classic types of search, such as searching for word forms, phrases, patterns and concepts. Additionally, we consider the augmentation of patterns with syntactic and semantic information. Next, we provide a general description of all NLP instruments: morphological, syntactic, semantic and pragmatic analysis. Finally, we end the paper with a comparative analysis of modern TM tools which can be helpful for selecting a suitable TM platform based on the user’s needs and skills.

Рассматривается технология создания паттернов из слов (понятий) естественного языка по текстовым данным в модели «мешок слов». Паттерны применяются для снижения размерности исходного пространства в описании документов и поиска семантически связанных слов по темам. Процесс снижения размерности реализуется через формирование по паттернам латентных признаков. Исследуется многообразие структур отношений документов для разбиения их на темы в латентном пространстве.

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

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

Состав признаков в наборах (паттернах из слов) формируется из упорядоченной по значениям устойчивости последовательности. Процесс формирования паттернов и латентных признаков на их основе реализуется по правилам иерархической агломеративной группировки.

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

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

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

The technology of creating patterns from natural language words (concepts) based on text data in the bag of words model is considered. Patterns are used to reduce the dimension of the original space in the description of documents and search for semantically related words by topic. The process of dimensionality reduction is implemented through the formation of patterns of latent features. The variety of structures of document relations is investigated in order to divide them into themes in the latent space.

It is considered that a given set of documents (objects) is divided into two non-overlapping classes, for the analysis of which it is necessary to use a common dictionary. The belonging of words to a common vocabulary is initially unknown. Class objects are considered as opposition to each other. Quantitative parameters of oppositionality are determined through the values of the stability of each feature and generalized assessments of objects according to non-overlapping sets of features.

To calculate the stability, the feature values are divided into non-intersecting intervals, the optimal boundaries of which are determined by a special criterion. The maximum stability is achieved under the condition that the boundaries of each interval contain values of one of the two classes.

The composition of features in sets (patterns of words) is formed from a sequence ordered by stability values. The process of formation of patterns and latent features based on them is implemented according to the rules of hierarchical agglomerative grouping.

A set of latent features is used for cluster analysis of documents using metric grouping algorithms. The analysis applies the coefficient of content authenticity based on the data on the belonging of documents to classes. The coefficient is a numerical characteristic of the dominance of class representatives in groups.

To divide documents into topics, it is proposed to use the union of groups in relation to their centers. As patterns for each topic, a sequence of words ordered by frequency of occurrence from a common dictionary is considered.

The results of a computational experiment on collections of abstracts of scientific dissertations are presented. Sequences of words from the general dictionary on 4 topics are formed.

Мы рассматриваем портфель с опционом колл и соответствующим базовым активом при стандартном предположении, что рыночная цена является случайной величиной с логнормальным распределением. Минимизируя дисперсию (риск хеджирования) портфеля на дату погашения опциона, мы находим оптимальное соотношение опциона и актива в портфеле. Как прямое следствие мы получим статистически справедливую цену опциона колл в явной форме (случай опциона пут может быть рассмотрен аналогичным образом). В отличие от известной теории Блэка–Шоулза, любой портфель не может рассматриваться свободным от риска, потому что никаких дополнительных сделок в течение контракта не предполагается, но среднестатистический риск, относящийся к достаточно большому количеству независимых портфелей, стремится к нулю асимптотически. Это свойство иллюстрируется в экспериментальном разделе на основе ежедневных цен акций 37-ми лидирующих американских компаний за период времени, начиная с апреля 2006 года по январь 2013 года.

We consider a portfolio with call option and the corresponding underlying asset under the standard assumption that stock-market price represents a random variable with lognormal distribution. Minimizing the variance hedging risk of the portfolio on the date of maturity of the call option we find a fraction of the asset per unit call option. As a direct consequence we derive the statistically fair lookback call option price in explicit form. In contrast to the famous Black–Scholes theory, any portfolio cannot be regarded as  risk-free because no additional transactions are supposed to be conducted over the life of the contract, but the sequence of independent portfolios will reduce risk to zero asymptotically. This property is illustrated in the experimental section using a dataset of daily stock prices of 37 leading US-based companies for the period from April 2006 to January 2013.

Задачи негладкой оптимизации нередко возникают во многих приложениях. Вопросы разработки эффективных вычислительных процедур для негладких задач в пространствах больших размерностей весьма актуальны. В таких случаях разумно применятьмет оды первого порядка (субградиентные методы), однако в достаточно общих ситуациях они приводят к невысоким скоростным гарантиям. Одним из подходов к этой проблеме может являться выделение подкласса негладких задач, допускающих относительно оптимистичные результаты о скорости сходимости в пространствах больших размерностей. К примеру, одним из вариантов дополнительных предположений может послужитьуслови е острого минимума, предложенное в конце 1960-х годов Б. Т. Поляком. В случае доступности информации о минимальном значении функции для липшицевых задач с острым минимумом известен субградиентный метод с шагом Б. Т. Поляка, который гарантирует линейную скорость сходимости по аргументу. Такой подход позволил покрыть ряд важных прикладных задач (например, задача проектирования точки на выпуклый компакт или задача отыскания общей точки системы выпуклых множеств). Однако как условие доступности минимального значения функции, так и само условие острого минимума выглядят довольно ограничительными. В этой связи в настоящей работе предлагается обобщенное условие острого минимума, аналогичное известному понятию неточного оракула. Предложенный подход позволяет расширить класс применимости субградиентных методов с шагом Б. Т. Поляка на ситуации неточной информации о значении минимума, а также неизвестной константы Липшица целевой функции. Более того, использование в теоретической оценке качества выдаваемого методом решения локальных аналогов глобальных характеристик целевой функции позволяет применять результаты такого типа и к более широким классам задач. Показана возможностьпр именения предложенного подхода к сильно выпуклым негладким задачам и выполнено экспериментальное сравнение с известным оптимальным субградиентным методом на таком классе задач. Более того, получены результаты о применимости предложенной методики для некоторых типов задач с релаксациями выпуклости: недавно предложенное понятие слабой $\beta$-квазивыпуклости и обычной квазивыпуклости. Исследовано обобщение описанной методики на ситуацию с предположением о доступности на итерациях $\delta$-субградиента целевой функции вместо обычного субградиента. Для одного из рассмотренных методов найдены условия, при которых на практике можно отказаться от проектирования итеративной последовательности на допустимое множество поставленной задачи.

Non-smooth optimization often arises in many applied problems. The issues of developing efficient computational procedures for such problems in high-dimensional spaces are very topical. First-order methods (subgradient methods) are well applicable here, but in fairly general situations they lead to low speed guarantees for large-scale problems. One of the approaches to this type of problem can be to identify a subclass of non-smooth problems that allow relatively optimistic results on the rate of convergence. For example, one of the options for additional assumptions can be the condition of a sharp minimum, proposed in the late 1960s by B. T. Polyak. In the case of the availability of information about the minimal value of the function for Lipschitz-continuous problems with a sharp minimum, it turned out to be possible to propose a subgradient method with a Polyak step-size, which guarantees a linear rate of convergence in the argument. This approach made it possible to cover a number of important applied problems (for example, the problem of projecting onto a convex compact set). However, both the condition of the availability of the minimal value of the function and the condition of a sharp minimum itself look rather restrictive. In this regard, in this paper, we propose a generalized condition for a sharp minimum, somewhat similar to the inexact oracle proposed recently by Devolder – Glineur – Nesterov. The proposed approach makes it possible to extend the class of applicability of subgradient methods with the Polyak step-size, to the situation of inexact information about the value of the minimum, as well as the unknown Lipschitz constant of the objective function. Moreover, the use of local analogs of the global characteristics of the objective function makes it possible to apply the results of this type to wider classes of problems. We show the possibility of applying the proposed approach to strongly convex nonsmooth problems, also, we make an experimental comparison with the known optimal subgradient method for such a class of problems. Moreover, there were obtained some results connected to the applicability of the proposed technique to some types of problems with convexity relaxations: the recently proposed notion of weak $\beta$-quasi-convexity and ordinary quasiconvexity. Also in the paper, we study a generalization of the described technique to the situation with the assumption that the $\delta$-subgradient of the objective function is available instead of the usual subgradient. For one of the considered methods, conditions are found under which, in practice, it is possible to escape the projection of the considered iterative sequence onto the feasible set of the problem.

Предложен метод отображения промежуточных представлений C-, C++-программ в пространство векторов (эмбеддингов) для оценки производительности программ на этапе компиляции, без необходимости исполнения. Использование эмбеддингов для данной цели позволяет не проводить сравнение графов исследуемых программ непосредственно, что вычислительно упрощает задачу сравнения программ. Метод основан на серии трансформаций исходного промежуточного представления (IR), таких как: инструментирование — добавление фиктивных инструкций в оптимизационном проходе компилятора в зависимости от разности смещений в текущей инструкции обращения к памяти относительно предыдущей, преобразование IR в многомерный вектор с помощью технологии IR2Vec с понижением размерности по алгоритму t-SNE (стохастическое вложение соседей с t-распределением). В качестве метрики производительности предлагается доля кэш-промахов 1-го уровня (D1 cache misses). Приводится эвристический критерий отличия программ с большей долей кэш-промахов от программ с меньшей долей по их образам. Также описан разработанный в ходе работы проход компилятора, генерирующий и добавляющий фиктивные инструкции IR согласно используемой модели памяти. Приведено описание разработанного программного комплекса, реализующего предложенный способ оценивания на базе компиляторной инфраструктуры LLVM. Проведен ряд вычислительных экспериментов на синтетических тестах из наборов программ с идентичными потоками управления, но различным порядком обращений к одномерному массиву, показано, что коэффициент корреляции между метрикой производительности и расстоянием до эмбеддинга худшей программы в наборе отрицателен вне зависимости от инициализации t-SNE, что позволяет сделать заключение о достоверности эвристического критерия. Также в статье рассмотрен способ генерации тестов. По результатам экспериментов, вариативность значений метрики производительности на исследуемых множествах предложена как метрика для улучшения генератора тестов.

The method for mapping of intermediate representations (IR) set of C, C++ programs to vector embedding space is considered to create an empirical estimation framework for static performance prediction using LLVM compiler infrastructure. The usage of embeddings makes programs easier to compare due to avoiding Control Flow Graphs (CFG) and Data Flow Graphs (DFG) direct comparison. This method is based on transformation series of the initial IR such as: instrumentation — injection of artificial instructions in an instrumentation compiler’s pass depending on load offset delta in the current instruction compared to the previous one, mapping of instrumented IR into multidimensional vector with IR2Vec and dimension reduction with t-SNE (t-distributed stochastic neighbor embedding) method. The D1 cache miss ratio measured with perf stat tool is considered as performance metric. A heuristic criterion of programs having more or less cache miss ratio is given. This criterion is based on embeddings of programs in 2D-space. The instrumentation compiler’s pass developed in this work is described: how it generates and injects artificial instructions into IR within the used memory model. The software pipeline that implements the performance estimation based on LLVM compiler infrastructure is given. Computational experiments are performed on synthetic tests which are the sets of programs with the same CFGs but with different sequences of offsets used when accessing the one-dimensional array of a given size. The correlation coefficient between performance metric and distance to the worst program’s embedding is measured and proved to be negative regardless of t-SNE initialization. This fact proves the heuristic criterion to be true. The process of such synthetic tests generation is also considered. Moreover, the variety of performance metric in programs set in such a test is proposed as a metric to be improved with exploration of more tests generators.

Фотосинтетический аппарат растительной клетки состоит из множества фотосинтетических электронтранспортных цепей (ЭТЦ), каждая из которых участвует в усвоении квантов света, сопряженном с переносом электрона между элементами цепи. Эффективность усвоения квантов света варьирует в зависимости от физиологического состояния растения. Энергия той части квантов, которую не удается усвоить, диссипирует в тепло либо высвечивается в виде флуоресценции. При действии возбуждающего света уровень флуоресценции постепенно растет, доходя до максимума. Кривая роста уровня флуоресценции в ответ на действие возбуждающего света называется кривой индукции флуоресценции (КИФ). КИФ имеет сложную форму, которая претерпевает существенные изменения при различных изменениях состояния фотосинтетического аппарата, что позволяет использовать ее для получения информации о текущем состоянии растения.

В реальном эксперименте, при действии возбуждающего света, мы наблюдаем ответ системы, представляющей собой ансамбль миллионов фотосинтетических ЭТЦ. С целью воспроизведения вероятностной природы процессов в фотосинтетической ЭТЦ разработана кинетическая модель Монте-Карло, в которой для каждой индивидуальной цепи определены вероятности возбуждения молекул светособирающей антенны при попадании кванта света, вероятности захвата энергии либо высвечивания кванта света реакционным центром и вероятности переноса электрона с донора на акцептор в пределах фотосинтетических мультиферментных комплексов в тилакоидной мембране и между этими комплексами и подвижными переносчиками электронов. События, происходящие в каждой из цепей фиксируются, суммируются и формируют кривую индукции флуоресценции и кривые изменения долей различных редокс-состояний переносчиков электрона, входящих в состав фотосинтетической электронтранспортной цепи. В работе описаны принципы построения модели, изучены зависимости кинетики регистрируемых величин от параметров модели, приведены примеры полученных зависимостей, соответствующие экспериментальным данными по регистрации флуоресценции хлорофилла реакционного центра фотосистемы 2 и окислительно-восстановительных превращений фотоактивного пигмента фотосистемы 1 — хлорофилла.

Photosynthetic apparatus of a plant cell consists of multiple photosynthetic electron transport chains (ETC). Each ETC is capable of capturing and utilizing light quanta, that drive electron transport along the chain. Light assimilation efficiency depends on the plant’s current physiological state. The energy of the part of quanta that cannot be utilized, dissipates into heat, or is emitted as fluorescence. Under high light conditions fluorescence levels gradually rise to the maximum level. The curve describing that rise is called fluorescence rise (FR). It has a complex shape and that shape changes depending on the photosynthetic apparatus state. This gives one the opportunity to investigate that state only using the non invasive measuring of the FR.

When measuring fluorescence in experimental conditions, we get a response from millions of photosynthetic units at a time. In order to reproduce the probabilistic nature of the processes in a photosynthetic ETC, we created a Monte Carlo model of this chain. This model describes an ETC as a sequence of electron carriers in a thylakoid membrane, connected with each other. Those carriers have certain probabilities of capturing light photons, transferring excited states, or reducing each other, depending on the current ETC state. The events that take place in each of the model photosynthetic ETCs are registered, accumulated and used to create fluorescence rise and electron carrier redox states accumulation kinetics. This paper describes the model structure, the principles of its operation and the relations between certain model parameters and the resulting kinetic curves shape. Model curves include photosystem II reaction center fluorescence rise and photosystem I reaction center redox state change kinetics under different conditions.