Head of the Sector – Dr.Sc. (Mathematics), Prof. Vassily Lyubetsky

Tel.: (095) 299-83-54, (095) 413-46-43; E-mail: lyubetsk@iitp.ru

The leading researchers of the laboratory include:

An algorithm of less then quadratic complexity that embeds many given genome trees into the initial species tree, evaluates the quality of this simultaneous embedding and iteratively transforms the species tree to increase monotonously the quality of this joint embedding is investigated.

An algorithm of quadratic complexity that searches for a common signal in a given set of DNA sequences, i.e. a system of similar words of a fixed length and satisfying some certain conditions, is under development.

A method for extraction of regulatory signals in DNA of bacteria based on comparative analysis of several genomes has been developed. Some bacterial regulons (purine, aromatic amino acids, arginine, riboflavin, SOS-response etc.) and regulons of archaebacteria (purine, tryptophan, heat shock, nitrogen utilization) are described. A method for prediction of trasporter specificity based on analysis of their regulation has been proposed, that allowed to describe important families of purine and riboflavin transporters.

RNA regulatory signals in Haemophilus influenzae ribosomal protein operons (spc, S10, L11, S15), and attenuators of transcription of aromatic amino acid biosynthetic operons (trpEDCBA, phe, pheST) from Salmonella typhi, Yersinia pestis, Erwinia herbicola, Vibrio cholerae, Haemophilus influenzae, Actinobacillus actinomycetem-comitans, Xanthonomas cmpestris, and Chlamydia trachomatis have been predicted using comparison with known Escherichia coli signals.

A method of prediction of human genes in genome sequences with errors has been developed. The algorithms has been implemented and is currently being tested.

A model theoretic description of some certain classes of information transformers (ITs) and axiomatic description of an arbitrary class of ITs is developed. The Bayes approach to decision making problems is developed and the Bayes principle is proved for the classes of linear, many-valued, fuzzy ITs and for any axiomatic given class of ITs.

The principles of construction of categories of dynamical ITs are investigated. A category of linear nondeterministic discrete time dynamical ITs is constructed. The problem of optimal synthesis of an image formation system with continuous vision field is investigated and reduced to Fredholm equation of the second kind. The proposed algorithm for this problem is tested.

A variant of the Shannon-McMillan-Breiman theorem for individual random sequences is proved. The evaluations of complexity of the applicability for the maximal series success length law are worked out. The dependence of likelihood functions on the complexity of probability distribution is investigated. The equivalence of two definitions of Bernoully sequence (by Kolmogorov and on the base of permutation measures) is proved.

An experimental evaluation of the preciseness of lineal properties of the space is done. The experimental data shows that if the observer was asked first to divide visually a given interval into n parts and then to visually lengthen the n-th part by n times, then, in average, the resulted inreval is more than the initial one, if n is odd, and is less, if n is even. And the relative error is essentially less if the length of the initial interval is no more than 10 sm. An experimental investigation of the preciseness of evaluation of the length of an interval under the condition of Ponzo illusion is done. An experimental evaluation of the quantitative value for some word combinations with the meaning of general quantifiers (“half”, “most”, “allmost all” etc.) in the Russian language is done. Some preliminary models that aimed to explain these experiments are proposed. (These experiments were made in collaboration with Laboratory of Bioinformatics of Cell Processes and Motocontrol).

A new effectively defined wide class of descriptions (theories) such that any sentence can be reduced to quantifier free or some other simple form is deduced.

A translation of formal proofs in a classical theory into the proofs in the corresponding intuitionistic theory of the lineal complexity is deduced; in part, it makes possible, having a classical proof of existence of some dependent magnitude, to construct effectively an algorithm that calculates this magnitude.

A general method of construction of essentialy more simple algorithms calculate boolean functions (i.e. boolean decision trees of the height 2M log N) is deduced. The notions can be defined as boolean functions such that i-th argument shows the existence/absence of the i-th indication for a given object. More simple algorithms to calculate boolean functions give more adequate representations of the corresponding notions.

It is proved that for any words x and y there exist transformers p (of x into y) and q (of y into x) such that the both have the minimal length and “independent” (i.e., with the joint information of the order of log of the complexities of x and y). If the “independence” is understood as log of the conditional complexities x/y and y/x, then such p and q may not exist.

It is proved that if a word x is simple relatively any rather complex word y, then there exists a simple algorithm that transforms allmost all y into the given x.

The complexity of some important tasks that can be formulated in terms of conjunction, disjunction and implication of two sets of words is calculated. A propositional formula that is not deducible in the intuitionistic propositional calculus such that the complexity of the corresponding task is of the logarithmical order of the argument complexities is found.

It is proved that there exist such words A, B, C that the complexity of the formula “A or B imply C” is close to the sum of Kolmogorov complexities K(C|A) + K(C|B).

The upper evaluations of the (tree) width of graphs that do not contain the flat lattices of the given size r as minors are proved. These evaluations are exp(p(r)), where p is a fixed polynom, for arbitraty graphs and lineal relatively r for flat graphs. This gives the same evaluations for the size of the graph CF-grammar bores all graphs of a bounded degree and do not contain the flat lattices of the given size as minors. The definition of n-divisible graph (which is ised in computer genetics) is proposed, and a polynomial algorithm that checks wherther a given graph G is n-divisible for a given n and makes the n-division is done.

It is proved that any generally complete (by Post) tabular modal logic that extends K4 has the interpolation property (the important connection of the notions of “information saturation” for any logic).

It is proved that there exists modal logic that have inffinitely many complete (by Post) extentions but all such extentions are tabular.

Decision algorithms for modal predicate logics K, K4, T, S4, S5 relatively to the classical predicate logic is done and proved.