Vladimir Ulyantsev | publications

2024

Systemic metabolic depletion of gut microbiome undermines responsiveness to melanoma immunotherapy

Zakharevich Natalia V, Morozov Maxim D, Kanaeva Vera A, Filippov Mikhail S, Zyubko Tatyana I, Ivanov Artem B, Ulyantsev Vladimir I, Klimina Ksenia M, Olekhnovich Evgenii I

Life Science Alliance 2024

Abs URL PDF

Immunotherapy has proven to be a boon for patients battling metastatic melanoma, significantly improving their clinical condition and overall quality of life. A compelling link between the composition of the gut microbiome and the efficacy of immunotherapy has been established in both animal models and human patients. However, the precise biological mechanisms by which gut microbes influence treatment outcomes remain poorly understood. Using a robust dataset of 680 fecal metagenomes from melanoma patients, a detailed catalog of metagenome-assembled genomes (MAGs) was constructed to explore the compositional and functional properties of the gut microbiome. Our study uncovered significant findings that deepen the understanding of the intricate relationship between gut microbes and the efficacy of melanoma immunotherapy. In particular, we discovered the specific metagenomic profile of patients with favorable treatment outcomes, characterized by a prevalence of MAGs with increased overall metabolic potential and proficiency in polysaccharide utilization, along with those responsible for cobalamin and amino acid production. Furthermore, our investigation of the biosynthetic pathways of short-chain fatty acids, known for their immunomodulatory role, revealed a differential abundance of these pathways among the specific MAGs. Among others, the cobalamin-dependent Wood–Ljungdahl pathway of acetate synthesis was directly associated with responsiveness to melanoma immunotherapy.

2023

GigaScience

GADMA2: more efficient and flexible demographic inference from genetic data

Noskova Ekaterina, Abramov Nikita, Iliutkin Stanislav, Sidorin Anton, Dobrynin Pavel, Ulyantsev Vladimir

GigaScience 2023

Abs URL PDF

Inference of complex demographic histories is a source of information about events that happened in the past of studied populations. Existing methods for demographic inference typically require input from the researcher in the form of a parameterized model. With an increased variety of methods and tools, each with its own interface, the model specification becomes tedious and error-prone. Moreover, optimization algorithms used to find model parameters sometimes turn out to be inefficient, for instance, by being not properly tuned or highly dependent on a user-provided initialization. The open-source software GADMA addresses these problems, providing automatic demographic inference. It proposes a common interface for several likelihood engines and provides global parameters optimization based on a genetic algorithm.Here, we introduce the new GADMA2 software and provide a detailed description of the added and expanded features. It has a renovated core code base, new likelihood engines, an updated optimization algorithm, and a flexible setup for automatic model construction. We provide a full overview of GADMA2 enhancements, compare the performance of supported likelihood engines on simulated data, and demonstrate an example of GADMA2 usage on 2 empirical datasets.We demonstrate the better performance of a genetic algorithm in GADMA2 by comparing it to the initial version and other existing optimization approaches. Our experiments on simulated data indicate that GADMA2’s likelihood engines are able to provide accurate estimations of demographic parameters even for misspecified models. We improve model parameters for 2 empirical datasets of inbred species.
Results and lessons learned from the sbv IMPROVER metagenomics diagnostics for inflammatory bowel disease challenge

Khachatryan Lusine, Xiang Yang, Ivanov Artem, Glaab Enrico, Graham Garrett, Granata Ilaria, Giordano Maurizio, Maddalena Lucia, Piccirillo Marina, Manipur Ichcha, Baruzzo Giacomo, Cappellato Marco, Avot Batiste, Stan Adrian, Battey James, Lo Sasso Giuseppe, Boue Stephanie, Ivanov Nikolai V., Peitsch Manuel C., Hoeng Julia, Falquet Laurent, Di Camillo Barbara, Guarracino Mario R., Ulyantsev Vladimir, Sierro Nicolas, Poussin Carine

Scientific Reports 2023

Abs URL PDF

A growing body of evidence links gut microbiota changes with inflammatory bowel disease (IBD), raising the potential benefit of exploiting metagenomics data for non-invasive IBD diagnostics. The sbv IMPROVER metagenomics diagnosis for inflammatory bowel disease challenge investigated computational metagenomics methods for discriminating IBD and nonIBD subjects. Participants in this challenge were given independent training and test metagenomics data from IBD and nonIBD subjects, which could be wither either raw read data (sub-challenge 1, SC1) or processed Taxonomy- and Function-based profiles (sub-challenge 2, SC2). A total of 81 anonymized submissions were received between September 2019 and March 2020. Most participants’ predictions performed better than random predictions in classifying IBD versus nonIBD, Ulcerative Colitis (UC) versus nonIBD, and Crohn’s Disease (CD) versus nonIBD. However, discrimination between UC and CD remains challenging, with the classification quality similar to the set of random predictions. We analyzed the class prediction accuracy, the metagenomics features by the teams, and computational methods used. These results will be openly shared with the scientific community to help advance IBD research and illustrate the application of a range of computational methodologies for effective metagenomic classification.
Consistent Stool Metagenomic Biomarkers Associated with the Response To Melanoma Immunotherapy

Olekhnovich Evgenii I., Ivanov Artem B., Babkina Anna A., Sokolov Arseniy A., Ulyantsev Vladimir I., Fedorov Dmitry E., Ilina Elena N.

mSystems 2023

Abs URL PDF

In this study, we put together a list of potentially the most beneficial bacteria that were associated with a responsiveness to melanoma immunotherapy. Another important result of this study is the list of functional biomarkers of responsiveness to immunotherapy, which are dispersed among different bacterial species. The human gut microbiome plays an important role in both health and disease. Recent studies have demonstrated a strong influence of the gut microbiome composition on the efficacy of cancer immunotherapy. However, available studies have not yet succeeded in finding reliable and consistent metagenomic markers that are associated with the response to immunotherapy. Therefore, the reanalysis of the published data may improve our understanding of the association between the composition of the gut microbiome and the treatment response. In this study, we focused on melanoma-related metagenomic data, which are more abundant than are data from other tumor types. We analyzed the metagenomes of 680 stool samples from 7 studies that were published earlier. The taxonomic and functional biomarkers were selected after comparing the metagenomes of patients showing different treatment responses. The list of selected biomarkers was also validated on additional metagenomic data sets that were dedicated to the influence of fecal microbiota transplantation on the response to melanoma immunotherapy. According to our analysis, the resulting cross-study taxonomic biomarkers included three bacterial species: Faecalibacterium prausnitzii, Bifidobacterium adolescentis, and Eubacterium rectale. 101 groups of genes were identified to be functional biomarkers, including those potentially involved in the production of immune-stimulating molecules and metabolites. Moreover, we ranked the microbial species by the number of genes encoding functionally relevant biomarkers that they contained. Thus, we put together a list of potentially the most beneficial bacteria for immunotherapy success. F. prausnitzii, E. rectale, and three species of bifidobacteria stood out as the most beneficial species, even though some useful functions were also present in other bacterial species. IMPORTANCE In this study, we put together a list of potentially the most beneficial bacteria that were associated with a responsiveness to melanoma immunotherapy. Another important result of this study is the list of functional biomarkers of responsiveness to immunotherapy, which are dispersed among different bacterial species. This result possibly explains the existing irregularities between studies regarding the bacterial species that are beneficial to melanoma immunotherapy. Overall, these findings can be utilized to issue recommendations for gut microbiome correction in cancer immunotherapy, and the resulting list of biomarkers might serve as a good stepping stone for the development of a diagnostic test that is aimed at predicting patients’ responses to melanoma immunotherapy.
A 4-lineage statistical suite to evaluate the support of large-scale retrotransposon insertion data to reconstruct evolutionary trees

Churakov G, Kuritzin A, Chukharev K, Zhang F, Wünnemann F, Ulyantsev V, Schmitz J

Systematic Biology 2023

Abs URL

Retrophylogenomics makes use of genome-wide retrotransposon presence/absence insertion patterns to resolve questions in phylogeny and population genetics. In the genomics era, evaluating high-throughput data requires the associated development of appropriately powerful statistical tools. The currently used KKSC 3-lineage statistical test for estimating the significance of retrophylogenomic data is limited by the number of possible tree topologies it can assess in one step. To improve on this, we have extended the analysis to simultaneously compare 4-lineages, enabling us to evaluate ten distinct presence/absence insertion patterns for 26 possible tree topologies plus 129 trees with different incidences of hybridization or introgression. The new tool provides statistics for cases involving multiple ancestral hybridizations/introgressions, ancestral incomplete lineage sorting, bifurcation, and polytomy. The test is embedded in a user-friendly web R-application (http : // retrogenomics.uni-muenster.de:3838/hammlet/) and is available for use by the scientific community.

2022

Hi-C Metagenomics in the ICU: Exploring Clinically Relevant Features of Gut Microbiome in Chronically Critically Ill Patients

Ivanova Valeriia, Chernevskaya Ekaterina, Vasiluev Petr, Ivanov Artem, Tolstoganov Ivan, Shafranskaya Daria, Ulyantsev Vladimir, Korobeynikov Anton, Razin Sergey V., Beloborodova Natalia, Ulianov Sergey V., Tyakht Alexander

Frontiers in Microbiology 2022

Abs URL PDF

Gut microbiome in critically ill patients shows profound dysbiosis. The most vulnerable is the subgroup of chronically critically ill (CCI) patients – those suffering from long-term dependence on support systems in intensive care units. It is important to investigate their microbiome as a potential reservoir of opportunistic taxa causing co-infections and a morbidity factor. We explored dynamics of microbiome composition in the CCI patients by combining “shotgun” metagenomics with chromosome conformation capture (Hi-C). Stool samples were collected at 2 time points from 2 patients with severe brain injury with different outcomes within a 1–2-week interval. The metagenome-assembled genomes (MAGs) were reconstructed based on the Hi-C data using a novel hicSPAdes method (along with the bin3c method for comparison), as well as independently of the Hi-C using MetaBAT2. The resistomes of the samples were derived using a novel assembly graph-based approach. Links of bacteria to antibiotic resistance genes, plasmids and viruses were analyzed using Hi-C-based networks. The gut community structure was enriched in opportunistic microorganisms. The binning using hicSPAdes was superior to the conventional WGS-based binning as well as to the bin3c in terms of the number, completeness and contamination of the reconstructed MAGs. Using Klebsiella pneumoniae as an example, we showed how chromosome conformation capture can aid comparative genomic analysis of clinically important pathogens. Diverse associations of resistome with antimicrobial therapy from the level of assembly graphs to gene content were discovered. Analysis of Hi-C networks suggested multiple “host-plasmid” and “host-phage” links. Hi-C metagenomics is a promising technique for investigating clinical microbiome samples. It provides a community composition profile with increased details on bacterial gene content and mobile genetic elements compared to conventional metagenomics. The ability of Hi-C binning to encompass the MAG’s plasmid content facilitates metagenomic evaluation of virulence and drug resistance dynamics in clinically relevant opportunistic pathogens. These findings will help to identify the targets for developing cost-effective and rapid tests for assessing microbiome-related health risks.
Machine learning of phase transitions in nonlinear polariton lattices

Zvyagintseva Daria, Sigurdsson Helgi, Kozin Valerii K., Iorsh Ivan, Shelykh Ivan A., Ulyantsev Vladimir, Kyriienko Oleksandr

Communications Physics 2022

Abs URL PDF

Polaritonic lattices offer a unique testbed for studying nonlinear driven-dissipative physics. They show qualitative changes of their steady state as a function of system parameters, which resemble non-equilibrium phase transitions. Unlike their equilibrium counterparts, these transitions cannot be characterised by conventional statistical physics methods. Here, we study a lattice of square-arranged polariton condensates with nearest-neighbour coupling, and simulate the polarisation (pseudospin) dynamics of the polariton lattice, observing regions with distinct steady-state polarisation patterns. We classify these patterns using machine learning methods and determine the boundaries separating different regions. First, we use unsupervised data mining techniques to sketch the boundaries of phase transitions. We then apply learning by confusion, a neural network-based method for learning labels in a dataset, and extract the polaritonic phase diagram. Our work takes a step towards AI-enabled studies of polaritonic systems.
Intestinal microbiome changes in an infant with right atrial isomerism and recurrent necrotizing enterocolitis: A case report and review of literature

Kaplina Aleksandra, Zaikova Ekaterina, Ivanov Artem, Volkova Yulia, Alkhova Tatiana, Nikiforov Vladimir, Latypov Alexander, Khavkina Marina, Fedoseeva Tatiana, Pervunina Tatiana, Skorobogatova Yulia, Volkova Svetlana, Ulyantsev Vladimir, Kalinina Olga, Sitkin Stanislav, Petrova Natalia

World Journal of Clinical Cases 2022

Abs URL PDF

BACKGROUND Necrotizing enterocolitis (NEC) is a multifactorial disease that predominantly affects premature neonates. Intestinal dysbiosis plays a critical role in NEC pathogenesis in premature neonates. The main risk factor for NEC in term infants is mesenteric hypoperfusion associated with ductal-dependent congenital heart disease (CHD) that eventually leads to intestinal ischemia. The incidence of NEC in neonates with critical CHD is 6.8%-13%. However, the role of the intestinal microbiome in NEC pathogenesis in infants with ductal-dependent CHD remains unclear. CASE SUMMARY A male term neonate with right atrial isomerism underwent modified Blalock-Taussig shunt placement on the 14th day of life and had persistent mesenteric hypoperfusion after surgery. The patient had episodes of NEC stage IIA on the 1st and 28th days after cardiac surgery. Fecal microbial composition was analyzed before and after cardiac surgery by sequencing region V4 of the 16S rRNA gene. Before surgery, species belonging to genera Veillonella and Clostridia and class Gammaproteobacteria were detected, Bifidobacteriaceae showed a low abundance. The first NEC episode was associated with postoperative hemodynamic instability, intestinal ischemia-reperfusion injury during cardiopulmonary bypass, and a high abundance of Clostridium paraputrificum (Clostridium sensu stricto I) (56.1%). Antibacterial therapy after the first NEC episode resulted in increased abundance of Gammaproteobacteria, decreased abundance of Firmicutes, and low alpha diversity. These changes in the microbial composition promoted the growth of Clostridium sensu stricto I (72.0%) before the second NEC episode. CONCLUSION A high abundance of Clostridium sensu stricto I and mesenteric hypoperfusion may have contributed to NEC in the present case.
GADMA2: more efficient and flexible demographic inference from genetic data

Noskova Ekaterina, Abramov Nikita, Iliutkin Stanislav, Sidorin Anton, Dobrynin Pavel, Ulyantsev Vladimir

bioRxiv 2022

Abs URL

Inference of complex demographic histories typically requires parameterized models specified manually by the researcher. With an increased variety of methods and tools, each with its own interface, model specification becomes tedious and error-prone. Moreover, optimization algorithms used to find optimal parameters sometimes turn out to be inefficient. The open source software GADMA addresses these problems, providing automatic demographic inference. It proposes a common interface for several simulation engines and provides global optimization of parameters based on a genetic algorithm. Here, we introduce new features of GADMA2, the second version of the GADMA software. It has renovated core code base, new simulation engines, an updated optimization algorithm, and flexible specification of demographic history parameters. We provide a full overview of GADMA2 enhancements and demonstrate example of their usage.
Reproducible stool metagenomic biomarkers linked to the melanoma immunotherapy positive outcome

Olekhnovich Evgenii I., Ivanov Artem B., Babkina Anna A., Sokolov Arseniy A., Ulyantsev Vladimir I., Fedorov Dmitry E., Ilina Elena N.

bioRxiv 2022

Abs URL

The human gut microbiome plays an important role both in human’s health and disease. Recent studies have shown the undeniable influence of gut microbiota composition on cancer immunotherapy efficacy. However, these researches show a lack of consensus in defining reproducible metagenomic markers for a positive immunotherapy outcome. Accordingly, extended published data re-analysis may help reveal clearer associations between the composition of the gut microbiota and treatment response. In this study, we analyzed 358 stool metagenomes from 5 studies published earlier: 210 metagenomes from melanoma patients with positive immunotherapy outcome, 148 metagenomes from melanoma patients with negative immunotherapy outcome. The biomarkers were selected by the group comparison of patients’ stool samples with different treatment responses (47 responders vs 55 non-responders, 102 metagenomes). Selected biomarkers were verified using the available data describing the influence of the fecal microbiota transplantation on melanoma immunotherapy outcomes (9 donors, 6 responders, 19 non-responders, 256 metagenomes). According to our analysis, the resulting cross-study reproducible taxonomic biomarkers correspond to 12 Firmicutes, 4 Bacteroidetes, and 3 Actinobacteria. 140 gene groups were identified as reproducible functional biomarkers, including those potentially involved in production of immune-stimulating molecules and metabolites. In addition, we ranked taxonomic biomarkers by the number of functional biomarkers found in their metagenomic context. In other words, we predicted a list of the potential “most beneficial” bacteria for a positive response to melanoma immunotherapy. The obtained results can be used to make recommendations for the gut microbiota correction in cancer immunotherapy, and the resulting list of biomarkers can be considered for potential diagnostic ways for predicting melanoma immunotherapy outcome. Another important point is the functional biomarkers of positive immunotherapy outcome are distributed in different bacterial species that can explain the lack of consensus of defining melanoma immunotherapy beneficial species between different studies.Competing Interest StatementThe authors have declared no competing interest.

2021

Evaluating the Hardness of SAT Instances Using Evolutionary Optimization Algorithms

Semenov Alexander, Chivilikhin Daniil, Pavlenko Artem, Otpuschennikov Ilya, Ulyantsev Vladimir, Ignatiev Alexey

In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021) 2021

URL PDF
Separation of Donor and Recipient Microbial Diversity Allows Determination of Taxonomic and Functional Features of Gut Microbiota Restructuring following Fecal Transplantation

Olekhnovich Evgenii, Ivanov Artem, Ulyantsev Vladimir, Ilina Elena

mSystems 2021

Abs URL PDF

We assumed that the enrichment of successful gut microbes by lantibiotic/antibiotic resistance genes can be related to gut microbiota colonization resistance by third-party microbe phenomena and resistance to bacterium-derived or host-derived antimicrobial substances. According to this assumption, competition between the donor-derived and recipient-derived microbes as well as host immunity may play a key role in the FMT-related colonization and redistribution of recipient gut microbiota structure. Fecal microbiota transplantation (FMT) is currently used in medicine to treat recurrent clostridial colitis and other intestinal diseases. However, neither the therapeutic mechanism of FMT nor the mechanism that allows the donor bacteria to colonize the intestine of the recipient has yet been clearly described. From a biological point of view, FMT can be considered a useful model for studying the ecology of host-associated microbial communities. FMT experiments can shed light on the relationship features between the host and its gut microbiota. This creates the need for experimentation with approaches to metagenomic data analysis which may be useful for the interpretation of observed biological phenomena. Here, the recipient intestine colonization analysis tool (RECAST) novel computational approach is presented, which is based on the metagenomic read sorting process per their origin in the recipient’s post-FMT stool metagenome. Using the RECAST algorithm, taxonomic/functional annotation, and machine learning approaches, the metagenomes from three FMT studies, including healthy volunteers, patients with clostridial colitis, and patients with metabolic syndrome, were analyzed. Using our computational pipeline, the donor-derived and recipient-derived microbes which formed the recipient post-FMT stool metagenomes (successful microbes) were identified. Their presence is well explained by a higher relative abundance in donor/pre-FMT recipient metagenomes or other metagenomes from the human population. In addition, successful microbes are enriched with gene groups potentially related to antibiotic resistance, including antimicrobial peptides. Interestingly, the observed reorganization features are universal and independent of the disease. IMPORTANCE We assumed that the enrichment of successful gut microbes by lantibiotic/antibiotic resistance genes can be related to gut microbiota colonization resistance by third-party microbe phenomena and resistance to bacterium-derived or host-derived antimicrobial substances. According to this assumption, competition between the donor-derived and recipient-derived microbes as well as host immunity may play a key role in the FMT-related colonization and redistribution of recipient gut microbiota structure.
Multipole optimization of light focusing by silicon nanosphere structures

Ustimenko Nikita, Baryshnikova Kseniia, Melnikov Roman, Kornovan Danil, Ulyantsev Vladimir, Chichkov Boris, Evlyukhin Andrey

Journal of the Optical Society of America B 2021

Abs URL

We investigate the applicability of the coupled multipole model and its modification in the framework of the zero-order Born approximation for modeling of light focusing by finite-size nanostructures of silicon nanospheres, supporting electric and magnetic dipole and quadrupole resonances. The results based on the analytical approximations are verified by comparison with the numerical simulations performed by the T-matrix method. Using the evolutionary algorithm optimization, we apply the developed approach to design silicon nanosphere metalenses with predefined focusing properties. The obtained results demonstrate a strong optimization potential of the suggested calculation scheme for engineering ultrathin metalenses.
BeBoSy: Behavior Examples meet Bounded Synthesis

Chivilikhin D., Zakirzyanov I., Ulyantsev V.

IEEE Access 2021

Abs URL

Bounded synthesis generates a state machine satisfying given temporal specification in linear temporal logic (LTL) while bounding the number of states of the target solution. Bounded synthesis methods currently do not support finite-length behavior examples, which are often helpful when formulating the specification of the desired state machine. In this work we show how to incorporate behavior examples into bounded synthesis methods and exemplify the approach by presenting BeBoSy (Behavior Examples meet BoSy), an extension of the bounded synthesis tool BoSy based on reductions to Boolean satisfiability (SAT) and Quantified Boolean formula satisfiability (QSAT) problems. The proposed approach is to augment encodings used in BoSy with additional constraints that ensure the compliance of the generated state machine with the given behavior examples. Experiments with openly available data from the annual reactive synthesis competition SYNTCOMP augmented with random behavior examples show that the efficiency of the proposed approach is superior to both BoSy (with naïve representation of behavior examples with LTL formulas) and a state-of-the-art counterexample-guided approach EFSM-tools.

2020

GigaScience

GADMA: Genetic algorithm for inferring demographic history of multiple populations from allele frequency spectrum data

Noskova Ekaterina, Ulyantsev Vladimir, Koepfli Klaus-Peter, O’Brien Stephen J, Dobrynin Pavel

GigaScience 2020

Abs URL PDF

The demographic history of any population is imprinted in the genomes of the individuals that make up the population. One of the most popular and convenient representations of genetic information is the allele frequency spectrum (AFS), the distribution of allele frequencies in populations. The joint AFS is commonly used to reconstruct the demographic history of multiple populations, and several methods based on diffusion approximation (e.g., ∂a∂i) and ordinary differential equations (e.g., moments) have been developed and applied for demographic inference. These methods provide an opportunity to simulate AFS under a variety of researcher-specified demographic models and to estimate the best model and associated parameters using likelihood-based local optimizations. However, there are no known algorithms to perform global searches of demographic models with a given AFS.Here, we introduce a new method that implements a global search using a genetic algorithm for the automatic and unsupervised inference of demographic history from joint AFS data. Our method is implemented in the software GADMA (Genetic Algorithm for Demographic Model Analysis, https://github.com/ctlab/GADMA).We demonstrate the performance of GADMA by applying it to sequence data from humans and non-model organisms and show that it is able to automatically infer a demographic model close to or even better than the one that was previously obtained manually. Moreover, GADMA is able to infer multiple demographic models at different local optima close to the global one, providing a larger set of possible scenarios to further explore demographic history.
Evolutionary and genetic algorithms for design of metadevices working on electric dipole resonance

Melnikov Roman, Baryshnikova Kseniia, Petrov Mihail, Ulyantsev Vladimir, Evlyukhin Andrey, Chichkov Boris

Journal of Physics: Conference Series 2020

Abs URL PDF

All-dielectric nanophotonics is a rapidly growing field of modern science. Metasurfaces and other planar devices based on all-dielectric nanoparticles lead to manage the light propagation at the nanoscale. Impressive effects such as perfect absorption, invisibility, chirality effects, negative refraction, light focusing in the area with size smaller than wavelength, nano-lasing etc - can be achieved with all-dielectric technologies. While it is needed to use more and more complicated designs for solution of modern nanophotonics’ currents tasks, non-classical methods of optimization become relevant. For example, to design reconfigurable metalenses with an additional degree of freedom such as polarizability or temperature dependence, evolutionary or genetic algorithms show their high applicability. In this work, we show a new approach to design metalenses with evolutionary and genetic algorithms.
MoG-VQE: Multiobjective genetic variational quantum eigensolver

Chivilikhin D., Samarin A., Ulyantsev V., Iorsh I., Oganov A. R., Kyriienko O.

2020

URL
Gut microbiota alterations due to fecal transplant

Olekhnovich Evgenii, Ivanov Artem, Ulyantsev Vladimir, Ilina Elena

bioRxiv 2020

Abs URL

Background Fecal microbiota transplantation (FMT) is currently used to treat recurrent clostridial colitis and other diseases. However, neither the therapeutic mechanism of the FMT nor the mechanism that allows the donor bacteria to colonize the intestine of the recipient has yet been described. Moreover, FMT is a great model for studying the ecology of host-associated microbial communities. This creates the need for experimentation with approaches to metagenomic data analysis which may be useful to the interpretation of observed biological phenomena.Methods Here the RECAST (Recipient intestinE Colonisation AnalysiS Tool) computational approach is presented, which is based on the shotgun reads sorting process in accordance with their origin in recipient metagenome. Using the RECAST algorithm, taxonomic/functional annotation, and machine learning, the shotgun metagenomic data from three FMT studies including healthy volunteers, patients with clostridial colitis and metabolic syndrome were analyzed.Results According to the analysis results, the colonizing and remaining microbial diversity in the post-FMT recipient metagenomic samples is clearly separated from the non-colonizers and lost. It is well explained by higher relative abundance in donor/pre-FMT recipient, Human Microbiome project metagenomes, and taxonomy. Moreover, the colonizing and remaining microbes are associated with lantibiotic and tetracyclines resistance genes.Conclusion Based on obtained results, the previously proposed “core” human gut microbiome concept may be elaborated. The top microbes of gut microbiota form “cores”, which, moreover, are mutually integrable between humans. Also, we assume that redistribution of microbial diversity in post-FMT recipients’ metagenomes is due to competition of donor/recipient microbes and to host immunity. The associations of top gut microbes with lantibiotic/antibiotic resistance can be related to gut microbiota colonization resistance phenomena or anthropogenic impact.Competing Interest StatementThe authors have declared no competing interest.FMTfecal microbiota transplantation.IBDinflammatory bowel disease.GRMgenome-resolved metagenomics.NMDSNon-metric multidimensional scaling.CDIClostridioides difficile infection.SNVSingle nucleotide variant.WGSWhole genome sequencing.MSmetabolic syndrome.KEGGkyoto encyclopedia of genes and genomes.KOKEGG orthology.ARantibiotic resistance.
A 4-lineage statistical suite to evaluate the support of large-scale retrotransposon insertion data to reconstruct evolutionary trees

Churakov G, Kuritzin A, Chukharev K, Zhang F, Wünnemann F, Ulyantsev V, Schmitz J

bioRxiv 2020

Abs URL

Retrophylogenomics makes use of genome-wide retrotransposon presence/absence insertion patterns to resolve questions in phylogeny and population genetics. In the genomics era, evaluating high-throughput data requires the associated development of appropriately powerful statistical tools. The currently used KKSC 3-lineage statistical test for evaluating the significance of data is limited by the number of possible tree topologies it can assess in one step. To improve on this, we have now extended the analysis to simultaneously compare 4-lineages, which now enables us to evaluate ten distinct presence/absence insertion patterns for 26 possible tree topologies plus 129 trees with different incidences of hybridization. Moreover, the new tool includes statistics for multiple ancestral hybridizations, ancestral incomplete lineage sorting, bifurcation, and polytomy. The test is embedded in a user-friendly web R-application (http://retrogenomics.uni-muenster.de:3838/hammlet/) and is available for use by the general scientific community.Competing Interest StatementThe authors have declared no competing interest.
Genome-wide sequence analyses of ethnic populations across Russia

Zhernakova Daria V., Brukhin Vladimir, Malov Sergey, Oleksyk Taras K., Koepfli Klaus Peter, Zhuk Anna, Dobrynin Pavel, Kliver Sergei, Cherkasov Nikolay, Tamazian Gaik, Rotkevich Mikhail, Krasheninnikova Ksenia, Evsyukov Igor, Sidorov Sviatoslav, Gorbunova Anna, Chernyaeva Ekaterina, Shevchenko Andrey, Kolchanova Sofia, Komissarov Alexei, Simonov Serguei, Antonik Alexey, Logachev Anton, Polev Dmitrii E., Pavlova Olga A., Glotov Andrey S., Ulyantsev Vladimir, Noskova Ekaterina, Davydova Tatyana K., Sivtseva Tatyana M., Limborska Svetlana, Balanovsky Oleg, Osakovsky Vladimir, Novozhilov Alexey, Puzyrev Valery, O’Brien Stephen J.

Genomics 2020

Abs URL

The Russian Federation is the largest and one of the most ethnically diverse countries in the world, however no centralized reference database of genetic variation exists to date. Such data are crucial for medical genetics and essential for studying population history. The Genome Russia Project aims at filling this gap by performing whole genome sequencing and analysis of peoples of the Russian Federation. Here we report the characterization of genome-wide variation of 264 healthy adults, including 60 newly sequenced samples. People of Russia carry known and novel genetic variants of adaptive, clinical and functional consequence that in many cases show allele frequency divergence from neighboring populations. Population genetics analyses revealed six phylogeographic partitions among indigenous ethnicities corresponding to their geographic locales. This study presents a characterization of population-specific genomic variation in Russia with results important for medical genetics and for understanding the dynamic population history of the world’s largest country.

2019

Efficient Symmetry Breaking for SAT-Based Minimum DFA Inference

Zakirzyanov Ilya, Morgado Antonio, Ignatiev Alexey, Ulyantsev Vladimir, Marques-Silva Joao

In Language and Automata Theory and Applications 2019

Abs URL PDF

Inference of deterministic finite automata (DFA) finds a wide range of important practical applications. In recent years, the use of SAT and SMT solvers for the minimum size DFA inference problem (MinDFA) enabled significant performance improvements. Nevertheless, there are many problems that are simply too difficult to solve to optimality with existing technologies. One fundamental difficulty of the MinDFA problem is the size of the search space. Moreover, another fundamental drawback of these approaches is the encoding size. This paper develops novel compact encodings for Symmetry Breaking of SAT-based approaches to MinDFA. The proposed encodings are shown to perform comparably in practice with the most efficient, but also significantly larger, symmetry breaking encodings.
Evolutionary Computation Techniques for Constructing SAT-Based Attacks in Algebraic Cryptanalysis

Pavlenko Artem, Semenov Alexander, Ulyantsev Vladimir

In Applications of Evolutionary Computation 2019

Abs URL PDF

In this paper we present the results on applying evolutionary computation techniques to construction of several cryptographic attacks. In particular, SAT-based guess-and-determine attacks studied in the context of algebraic cryptanalysis. Each of these attacks is built upon some set of Boolean variables, thus it can be specified by a Boolean vector. We use two general evolutionary strategies to find an optimal vector: (1+1)-EA and GA. Based on these strategies parallel algorithms (based on modern SAT-solvers) for solving the problem of minimization of a special pseudo-Boolean function are implemented. This function is a fitness function used to evaluate the runtime of a guess-and-determine attack. We compare the efficiency of (1+1)-EA and GA with the algorithm from the Tabu search class, that was earlier used to solve related problems. Our GA-based solution showed the best results on a number of test instances, namely, cryptanalysis problems of several stream ciphers (cryptographic keystream generators).
Fitness Comparison by Statistical Testing in Construction of SAT-Based Guess-and-Determine Cryptographic Attacks

Pavlenko Artem, Buzdalov Maxim, Ulyantsev Vladimir

In Proceedings of the Genetic and Evolutionary Computation Conference 2019

Abs URL PDF

Algebraic cryptanalysis studies breaking ciphers by solving algebraic equations. Some of the promising approaches use SAT solvers for this purpose. Although the corresponding satisfiability problems are hard, their difficulty can often be lowered by choosing a set of variables to brute force over, and by solving each of the corresponding reduced problems using a SAT solver, which is called the guess-and-determine attack. In many successful cipher breaking attempts this set was chosen analytically, however, the nature of the problem makes evolutionary computation a good choice.We investigate one particular method for constructing guess-and-determine attacks based on evolutionary algorithms. This method estimates the fitness of a particular guessed bit set by Monte-Carlo simulations. We show that using statistical tests within the comparator of fitness values, which can be used to reduce the necessary number of samples, together with a dynamic strategy for the upper limit on the number of samples, speeds up the attack by a factor of 1.5 to 4.3 even on a distributed cluster.
Function Block Finite-State Model Identification Using SAT and CSP Solvers

Chivilikhin Daniil, Ulyantsev Vladimir, Shalyto Anatoly, Vyatkin Valery

IEEE Transactions on Industrial Informatics 2019

URL PDF
Smart Contract Design Meets State Machine Synthesis: Case Studies

Suvorov Dmitrii, Ulyantsev Vladimir

2019

URL PDF

2018

Bioinf

MetaCherchant: analyzing genomic context of antibiotic resistance genes in gut microbiota

Olekhnovich Evgenii, Vasilyev Artem, Ulyantsev Vladimir, Kostryukova Elena, Tyakht Alexander

Bioinformatics 2018

Abs URL PDF

Antibiotic resistance is an important global public health problem. Human gut microbiota is an accumulator of resistance genes potentially providing them to pathogens. It is important to develop tools for identifying the mechanisms of how resistance is transmitted between gut microbial species and pathogens.We developed MetaCherchant—an algorithm for extracting the genomic environment of antibiotic resistance genes from metagenomic data in the form of a graph. The algorithm was validated on a number of simulated and published datasets, as well as applied to new ‘shotgun’ metagenomes of gut microbiota from patients with Helicobacter pylori who underwent antibiotic therapy. Genomic context was reconstructed for several major resistance genes. Taxonomic annotation of the context suggests that within a single metagenome, the resistance genes can be contained in genomes of multiple species. MetaCherchant allows reconstruction of mobile elements with resistance genes within the genomes of bacteria using metagenomic data. Application of MetaCherchant in differential mode produced specific graph structures suggesting the evidence of possible resistance gene transmission within a mobile element that occurred as a result of the antibiotic therapy. MetaCherchant is a promising tool giving researchers an opportunity to get an insight into dynamics of resistance transmission in vivo basing on metagenomic data.Source code and binaries are freely available for download at https://github.com/ctlab/metacherchant. The code is written in Java and is platform-independent.Supplementary data are available at Bioinformatics online.
Exact finite-state machine identification from scenarios and temporal properties

Ulyantsev Vladimir, Buzhinsky Igor, Shalyto Anatoly

International Journal on Software Tools for Technology Transfer 2018

Abs URL PDF

Finite-state models, such as finite-state machines (FSMs), aid software engineering in many ways. They are often used in formal verification and also can serve as visual software models. The latter application is associated with the problems of software synthesis and automatic derivation of software models from specification. Smaller synthesized models are more general and are easier to comprehend, yet the problem of minimum FSM identification has received little attention in previous research. This paper presents four exact methods to tackle the problem of minimum FSM identification from a set of test scenarios and a temporal specification represented in linear temporal logic. The methods are implemented as an open-source tool. Three of them are based on translations of the FSM identification problem to SAT or QSAT problem instances. Accounting for temporal properties is done via counterexample prohibition. Counterexamples are either obtained from previously identified FSMs, or based on bounded model checking. The fourth method uses backtracking. The proposed methods are evaluated on several case studies and on a larger number of randomly generated instances of increasing complexity. The results show that the Iterative SAT-based method is the leader among the proposed methods. The methods are also compared with existing inexact approaches, i.e., the ones which do not necessarily identify the minimum FSM, and these comparisons show encouraging results.
Active Learning of Formal Plant Models For Cyber-Physical Systems

Ovsiannikova P., Chivilikhin D., Ulyantsev V., Stankevich A., Zakirzyanov I., Vyatkin V., Shalyto A.

In IEEE 16th International Conference on Industrial Informatics (INDIN) 2018

PDF
Counterexample-guided inference of controller logic from execution traces and temporal formulas

Chivilikhin D., Buzhinsky I., Ulyantsev V., Stankevich A., Shalyto A., Vyatkin V.

In 2018 IEEE 23rd International Conference on Emerging Technologies and Factory Automation (ETFA) 2018

URL PDF
BFS Enumeration for Breaking Symmetries in Graphs

Moklev Vyacheslav, Ulyantsev Vladimir

2018

URL
Finding All Minimum-Size DFA Consistent with Given Examples: SAT-Based Approach

Zakirzyanov Ilya, Shalyto Anatoly, Ulyantsev Vladimir

In Software Engineering and Formal Methods. SEFM 2017 2018

Abs URL PDF

Deterministic finite automaton (DFA) is a fundamental concept in the theory of computation. The NP-hard DFA identification problem can be efficiently solved by translation to the Boolean satisfiability problem (SAT). Previously we developed a technique to reduce the problem search space by enforcing DFA states to be enumerated in breadth-first search (BFS) order. We proposed symmetry breaking predicates, which can be added to Boolean formulae representing various automata identification problems. In this paper we continue the study of SAT-based approaches. First, we propose new predicates based on depth-first search order. Second, we present three methods to identify all non-isomorphic automata of the minimum size instead of just one—the P-complete problem which has not been solved before. Third, we revisited our implementation of the BFS-based approach and conducted new evaluation experiments. It occurs that BFS-based approach outperforms all other exact algorithms for DFA identification and can be effectively applied for finding all solutions of the problem.

2017

Applying Reinforcement Learning and Supervised Learning Techniques to Play Hearthstone

Kachalsky I., Zakirzyanov I., Ulyantsev V.

In 2017 16th IEEE International Conference on Machine Learning and Applications (ICMLA) 2017

URL
Closed-loop verification of a compensating group drive model using synthesized formal plant model

Ovsiannikova P., Chivilikhin D., Ulyantsev V., Shalyto A.

In 2017 22nd IEEE International Conference on Emerging Technologies and Factory Automation (ETFA) 2017

URL
Plant trace generation for formal plant model inference: Methods and case study

Avdyukhin D., Chivilikhin D., Korneev G., Ulyantsev V., Shalyto A.

In 2017 IEEE 15th International Conference on Industrial Informatics (INDIN) 2017
CSP-based inference of function block finite-state models from execution traces

Chivilikhin D., Ulyantsev V., Shalyto A., Vyatkin V.

In 2017 IEEE 15th International Conference on Industrial Informatics (INDIN) 2017

URL

2016

Bioinf

MetaFast: fast reference-free graph-based comparison of shotgun metagenomic data

Ulyantsev Vladimir, Kazakov Sergey, Dubinkina Veronika, Tyakht Alexander, Alexeev Dmitry

Bioinformatics 2016

Abs URL

Motivation: High-throughput metagenomic sequencing has revolutionized our view on the structure and metabolic potential of microbial communities. However, analysis of metagenomic composition is often complicated by the high complexity of the community and the lack of related reference genomic sequences. As a start point for comparative metagenomic analysis, the researchers require efficient means for assessing pairwise similarity of the metagenomes (beta-diversity). A number of approaches were used to address this task, however, most of them have inherent disadvantages that limit their scope of applicability. For instance, the reference-based methods poorly perform on metagenomes from previously unstudied niches, while composition-based methods appear to be too abstract for straightforward interpretation and do not allow to identify the differentially abundant features.Results: We developed MetaFast, an approach that allows to represent a shotgun metagenome from an arbitrary environment as a modified de Bruijn graph consisting of simplified components. For multiple metagenomes, the resulting representation is used to obtain a pairwise similarity matrix. The dimensional structure of the metagenomic components preserved in our algorithm reflects the inherent subspecies-level diversity of microbiota. The method is computationally efficient and especially promising for an analysis of metagenomes from novel environmental niches.Availability and Implementation: Source code and binaries are freely available for download at https://github.com/ctlab/metafast. The code is written in Java and is platform independent (tested on Linux and Windows x86_64). Supplementary information:Supplementary data are available at Bioinformatics online.
Assessment of k-mer spectrum applicability for metagenomic dissimilarity analysis

Dubinkina Veronika, Ischenko Dmitry, Ulyantsev Vladimir, Tyakht Alexander, Alexeev Dmitry

BMC bioinformatics 2016

Abs URL

A rapidly increasing flow of genomic data requires the development of efficient methods for obtaining its compact representation. Feature extraction facilitates classification, clustering and model analysis for testing and refining biological hypotheses. “Shotgun” metagenome is an analytically challenging type of genomic data - containing sequences of all genes from the totality of a complex microbial community. Recently, researchers started to analyze metagenomes using reference-free methods based on the analysis of oligonucleotides (k-mers) frequency spectrum previously applied to isolated genomes. However, little is known about their correlation with the existing approaches for metagenomic feature extraction, as well as the limits of applicability. Here we evaluated a metagenomic pairwise dissimilarity measure based on short k-mer spectrum using the example of human gut microbiota, a biomedically significant object of study.
Modified ant colony algorithm for constructing finite state machines from execution scenarios and temporal formulas

Chivilikhin Daniil, Ulyantsev Vladimir, Shalyto Anatoly

Automation and Remote Control 2016

Abs URL

We solve the problem of constructing extended finite state machines with execution scenarios and temporal formulas. We propose a new algorithm pstMuACO that combines a scenario filtering procedure, an exact algorithm efsmSAT for constructing finite state machines from execution scenarios based on a reduction to the Boolean satisfiability problem, and a parallel ant colony algorithm pMuACO. Experiments show that constructing several initial solutions for the ant colony algorithm with reduced sets of scenarios significantly reduces the total time needed to find optimal solutions. The proposed algorithm can be used for automated construction of reliable control systems.

2015

Modification of the method of generation of control finite-state machines with continuous actions based on training examples

Buzhinsky I, Kazakov S, Ulyantsev V, Tsarev F, Shalyto A

Journal of Computer and Systems Sciences International 2015

Abs URL

Control finite-state machines can be used in the development of reliable control systems due to their clarity and because it is possible to formally verify them. The paper deals with resolving the problem of the generation of machines that control plants with complex behavior based on training examples. The input and output actions of the machines are given by real numbers. A method for the generation of machines is proposed. It is a modification of the previously proposed approaches based on the genetic and ant colony optimization algorithms. Changes include a new way of representing machines and improving the fitness function. The method makes it possible to generate machines whose behavior is more consistent with training examples than the behavior of machines generated by the known approaches.
Constructing parsimonious hybridization networks from multiple phylogenetic trees using a SAT-solver

Ulyantsev Vladimir, Melnik Mikhail

In International Conference on Algorithms for Computational Biology. ALCoB 2015 2015

Abs URL

We present an exact algorithm for constructing minimal hybridization networks from multiple trees which is based on reducing the problem to the Boolean satisfiability problem. The main idea of our algorithm is to iterate over possible hybridization numbers and to construct a Boolean formula for each of them that is satisfiable iff there exists a network with such hybridization number. The proposed algorithm is implemented in a software tool PhyloSAT. The experimental evaluation of our algorithm on biological data shows that our method is as far as we know the fastest exact algorithm for the minimal hybridization network construction problem.
Evolutionary approach to coverage testing of IEC 61499 function block applications

Buzhinsky I., Ulyantsev V., Veijalainen J., Vyatkin V.

In 2015 IEEE 13th International Conference on Industrial Informatics (INDIN) 2015

Abs URL

The paper addresses the problem of coverage testing of industrial automation software represented in the IEC 61499 standard, one of the recent standards for distributed control system design. Contrary to model-based testing (MBT), the paper focuses on implementation coverage, not model coverage. An approach based on evolutionary algorithms is presented which generates coverage test suites for both basic and composite IEC 61499 function blocks. It employs two third-party tools, FBDK and EvoSuite. The evaluation of the approach was performed on a set of control applications for two lab-scale demonstration plants. Results show that the approach is applicable and shows good performance at least on basic function blocks. The generated tests suites helped to discover several unreachable system parts, which pinpointed errors in the systems under test.
BFS-based symmetry breaking predicates for DFA identification

Ulyantsev Vladimir, Zakirzyanov Ilya, Shalyto Anatoly

In International Conference on Language and Automata Theory and Applications 2015

Abs URL PDF

It was shown before that the NP-hard problem of deterministic finite automata (DFA) identification can be translated to Boolean satisfiability (SAT). Modern SAT-solvers can efficiently tackle hard DFA identification instances. We present a technique to reduce SAT search space by enforcing an enumeration of DFA states in breadth-first search (BFS) order. We propose symmetry breaking predicates, which can be added to Boolean formulae representing various DFA identification problems. We show how to apply this technique to DFA identification from both noiseless and noisy data. The main advantage of the proposed approach is that it allows to exactly determine the existence or non-existence of a solution of the noisy DFA identification problem.

2014

Combining Exact and Metaheuristic Techniques for Learning Extended Finite-State Machines from Test Scenarios and Temporal Properties

Chivilikhin D., Ulyantsev V., Shalyto A.

In 2014 13th International Conference on Machine Learning and Applications 2014

Abs URL

This paper addresses the problem of learning extended finite-state machines (EFSMs) from user-specified behavior examples (test scenarios) and temporal properties. We show how to combine exact EFSM inference algorithms (that always find a solution if it exists) and metaheuristics to derive an efficient combined EFSM learning algorithm. We also present a new exact EFSM inference algorithm based on Constraint Satisfaction Problem (CSP) solvers. Experimental results are reported showing that the new combined algorithm significantly outperforms a previously used metaheuristic.
Inferring Automata-Based Programs from Specification with Mutation-Based Ant Colony Optimization

Chivilikhin Daniil, Ulyantsev Vladimir

In Proceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation 2014

Abs URL

In this paper we address the problem of constructing correct-by-design programs with the use of the automata-based programming paradigm. A recent algorithm for learning finite-state machines (FSMs) MuACOsm is applied to the problem of inferring extended finite-state machine (EFSM) models from behavior examples (test scenarios) and temporal properties, and is shown to outperform the genetic algorithm (GA) used earlier.
Improving the Quality of Supervised Finite-State Machine Construction Using Real-Valued Variables

Buzhinsky Igor, Chivilikhin Daniil, Ulyantsev Vladimir, Tsarev Fedor

In Proceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation 2014

Abs URL

The use of finite-state machines (FSMs) is a reliable choice for control system design since they can be formally verified. In this paper a problem of constructing FSMs with real-valued input and control parameters is considered. It is supposed that a set of human-created behavior examples, or tests, is available. One of the earlier approaches for solving the problem suggested using genetic algorithms together with a transition labeling algorithm. This paper improves this approach via the use of real-valued variables which are calculated using the FSM’s input data. FSMs with real-valued variables are represented as systems of linear controllers. The new approach allows to synthesize FSMs of better quality than it was possible earlier.
Inducing finite state machines from training samples using ant colony optimization

Buzhinsky IP, Ulyantsev VI, Chivilikhin DS, Shalyto AA

Journal of Computer and Systems Sciences International 2014

Abs URL

A method for control finite state machine (FSM) induction in which an ant colony optimization algorithm is used for search optimization is proposed. The efficiency of this method is estimated using the generation of FSMs for controlling a model of an unmanned aerial vehicle (UAV). It is shown that the proposed method outperforms the method based on genetic algorithms both in terms of performance and quality.
Extended finite-state machine inference with parallel ant colony based algorithms

Chivilikhin D, Ulyantsev V, Shalyto A

In Proceedings of the Student Workshop on Bioinspired Optimization Methods and their Applications, BIOMA 2014 2014

Abs URL

This paper addresses the problem of inferring extended finite-state machines (EFSMs) with parallel algorithms. We propose a number of parallel versions of a recent EFSM inference algorithm MuACO. Two of the proposed algorithms demonstrate super-linear speedup.

2013

Learning Finite-State Machines: Conserving Fitness Function Evaluations by Marking Used Transitions

Chivilikhin D., Ulyantsev V.

In 2013 12th International Conference on Machine Learning and Applications 2013

Abs URL

This paper is dedicated to the problem of learning finite-state machines (FSMs), which plays a key role in automata-based programming. Metaheuristic algorithms commonly applied to this problem often use FSM mutations (small changes in the FSM structure) for solution construction. Most of them do not employ the specifics of FSMs in their work. We propose a new simple method for improving performance of these algorithms. The basic idea is to mark those transitions of FSMs that were used during fitness evaluation. Then, if a FSM mutation changes a transition that was not used in fitness evaluation, the fitness function value need not be calculated for the mutated FSM. This observation allows to conserve fitness evaluations, which often have high computational costs. The proposed method has been incorporated into several traditional and recent FSM learning algorithms based on evolutionary strategies, genetic algorithms and ant colony optimization. Experimental results are reported showing that the new method significantly improves performance of two methods based on evolutionary strategies and ant colony optimization.
Learning Finite-State Machines with Classical and Mutation-Based Ant Colony Optimization: Experimental Evaluation

Chivilikhin D., Ulyantsev V.

In 2013 BRICS Congress on Computational Intelligence and 11th Brazilian Congress on Computational Intelligence 2013

Abs URL

The problem of learning finite-state machines (FSM) is tackled by three Ant Colony Optimization (ACO) algorithms. The first two classical ACO algorithms are based on the classical ACO combinatorial problem reduction, where nodes of the ACO construction graph represent solution components, while full solutions are built by the ants in the process of foraging. The third recently introduced mutation-based ACO algorithm employs another problem mapping, where construction graph nodes represent complete solutions. Here, ants travel between solutions to find the optimal one. In this paper we try to take a step back from the mutation-based ACO to find out if classical ACO algorithms can be used for learning FSMs. It was shown that classical ACO algorithms are inefficient for the problem of learning FSMs in comparison to the mutation-based ACO algorithm.
Search-Based Construction of Finite-State Machines with Real-Valued Actions: New Representation Model

Buzhinsky Igor, Ulyantsev Vladimir, Tsarev Fedor, Shalyto Anatoly

In Proceedings of the 15th Annual Conference Companion on Genetic and Evolutionary Computation 2013

Abs URL

In this paper a search-based method for constructing finite-state machines (FSMs) with continuous (real-valued) output actions is improved. A more flexible FSM representation model is presented and compared with the previous one on the problem of unmanned aircraft control.
MuACOsm: A New Mutation-Based Ant Colony Optimization Algorithm for Learning Finite-State Machines

Chivilikhin Daniil, Ulyantsev Vladimir

In Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation 2013

Abs URL

In this paper we present MuACOsm - a new method of learning Finite-State Machines (FSM) based on Ant Colony Optimization (ACO) and a graph representation of the search space. The input data is a set of events, a set of actions and the number of states in the target FSM. The goal is to maximize the given fitness function, which is defined on the set of all FSMs with given parameters. The new algorithm is compared with evolutionary algorithms and a genetic programming related approach on the well-known Artificial Ant problem.
Test-Based Induction of Finite-State Machines with Continuous Output Actions

Buzhinsky Igor, Ulyantsev Vladimir, Shalyto Anatoly

IFAC Proceedings Volumes 2013

Abs URL PDF

In this paper we improve an earlier developed method of finite-state machine (FSM) induction for controlling objects with complex behavior. This method allows to construct FSMs with continuous (real-valued) output actions. A set of human-created training samples serves as input data for it. We apply an ant colony optimization algorithm and a (μ, λ)-evolution strategy for solving the problem as more effective than a genetic algorithm used in the initial method. The modification of the method is evaluated on the problem of unmanned aircraft control.
Solving Five Instances of the Artificial Ant Problem with Ant Colony Optimization

Chivilikhin Daniil S., Ulyantsev Vladimir I., Shalyto Anatoly A.

IFAC Proceedings Volumes 2013

Abs URL PDF

The Artificial Ant problem is a common benchmark problem often used for metaheuristic algorithm performance evaluation. The problem is to find a strategy controlling an agent (called an Artificial Ant) in a game performed on a square toroidal field. Some cells of the field contain “food” pellets, which are distributed along a certain trail. In this paper we use Finite-State Machines (FSM) for strategy representation and present a new algorithm –MuACOsm – for learning finite-state machines. The new algorithm is based on an Ant Colony Optimization algorithm (ACO) and a graph representation of the search space. We compare the new algorithm with a genetic algorithm (GA), evolutionary strategies (ES), a genetic programming related approach and reinforcement learning on five instances of the Artificial Ant Problem.

2012

Learning finite-state machines with ant colony optimization

Chivilikhin Daniil, Ulyantsev Vladimir

In International Conference on Swarm Intelligence. ANTS 2012. 2012

Abs URL PDF

In this paper we present a new method of learning Finite-State Machines (FSM) with the specified value of a given fitness function, which is based on an Ant Colony Optimization algorithm (ACO) and a graph representation of the search space. The input data is a set of events, a set of actions and the number of states in the target FSM and the goal is to maximize the given fitness function, which is defined on the set of all FSMs with given parameters. Comparison of the new algorithm and a genetic algorithm (GA) on benchmark problems shows that the new algorithm either outperforms GA or works just as well.
Test-Based Extended Finite-State Machines Induction with Evolutionary Algorithms and Ant Colony Optimization

Chivilikhin Daniil, Ulyantsev Vladimir, Tsarev Fedor

In Proceedings of the 14th Annual Conference Companion on Genetic and Evolutionary Computation 2012

Abs URL PDF

In this paper we consider the problem of extended finite-state machines induction. The input data for this problem is a set of tests. Each test consists of two sequences - an input sequence and a corresponding output sequence. We present a new method of Extended Finite-State Machines (EFSM) induction based on an Ant Colony Optimization algorithm (ACO) and a new meaningful test-based crossover operator for EFSMs. New algorithms are compared with a genetic algorithm (GA) using a traditional crossover, a (1+1) evolutionary strategy and a random mutation hill climber. This comparison shows that the use of test-based crossover greatly improves performance of GA. GA on average also significantly outperforms the hill climber and evolutionary strategy. ACO outperforms GA, and the difference between average performance of ACO and GA hybridized with hill climber is insignificant.
Extended Finite-State Machine Induction using SAT-Solver

Ulyantsev Vladimir I., Tsarev Fedor N.

IFAC Proceedings Volumes 2012

Abs URL PDF

In the paper we describe the extended finite-state machine (EFSM) induction method which uses SAT-solver. Input data for the induction algorithm is a set of test scenarios. The algorithm consists of several steps: scenarios tree construction, compatibility graph construction, Boolean formula construction, SAT-solver invocation and finite-state machine construction from the satisfying assignment. These extended finite-state machines can be used in automata-based programming, where programs are designed using automated controlled objects. Each controlled object contains a finite-state machine and a controlled object. The described method has been tested on randomly generated scenario sets containing 250 to 1500 elements and on the alarm clock controlling EFSM induction problem where it has greatly outperformed genetic algorithm.

2011

Extended Finite-State Machine Induction Using SAT-Solver

Ulyantsev V., Tsarev F.

In 2011 10th International Conference on Machine Learning and Applications and Workshops 2011

Abs URL PDF

In the paper we describe the extended finite-state machine (EFSM) induction method that uses SAT-solver. Input data for the induction algorithm is a set of test scenarios. The algorithm consists of several steps: scenarios tree construction, compatibility graph construction, Boolean formula construction, SAT-solver invocation and finite-state machine construction from satisfying assignment. These extended finite-state machines can be used in automata-based programming, where programs are designed as automated controlled objects. Each automated controlled object contains a finite-state machine and a controlled object. The method described has been tested on randomly generated scenario sets of size from 250 to 2000 and on the alarm clock controlling EFSM induction problem where it has greatly outperformed genetic algorithm.