Sector 1.1
Sector of Computer Logic in Information Processes
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:
|
Dr.Sc. (Math.) |
A. Chagrov |
Dr. |
K. Gorbunov |
|
Dr.Sc. ((Biol).) |
M. Gelfand |
Dr. |
V. V'yugin |
|
Dr.Sc. (Math.) |
P. Golubtsov |
S. Shelaev |
|
|
Dr.Sc. (Math) |
N. Vereshchagin |
DIRECTIONS OF ACTIVITY:
MAIN RESULTS
An algorithm of approximately quadratic complexity, which accepts as input a set of regulatory fragments believed to be bound by some common transcription factor and outputs aligned binding sites for this factor. Thus the algorithm solves one of the classical problems of computational molecular biology that gained additional importance with the accumulation of expression data obtained using DNA chip technology and, independently, publication of complete bacterial genomes. The algorithm was implemented and successfully tested on simulated and natural sequences, in particular, upstream regions of Escherichia coli genes.
An algorithm of approximately linear complexity for finding pairs of potential hairpins capable of forming of alternative RNA secondary structures. The algorithm was implemented and tested on histidine, tryptophan, treonin and isoleucine attenuators of Escherichia coli.
An algorithm of approximately linear complexity for construction of a reconciled tree ("species tree") given a set of trees constructed for individual protein families ("gene trees"). The problem of construction of a taxonomic tree given molecular data is traditional in the evolution studies. The algorithm was implemented and applied to analysis of several data sets, including mitochondrial proteins and data from the COG database.
It was proposed an algorithm, which lifts unreliable nodes in a phylogenetic gene tree and obtains as a result the nonbinary tree, for which in each position it is determined those nucleotides from the original genetic sequences that are not essential or
emerged as a result of an error in the source data. The algorithm is implemented on a computer and applied to natural samples.
In collaboration with the groups from the State Scientific Center "GosNIIGenetika" and the Moscow State University several regulatory systems were analyzed, namely, the multidrug resistance systems of enterobacteria, metabolism of aromatic amino acids and utilization of sugar acids of gamma-proteobacteria, heat shock (CIRCE-regulon), SOS-response, and arginine metabolism in diverse taxonomic groups.
The development of the concept of effective description of objects has been continued. In these area the following results are obtained.
A non-robust property of the Birkhoff individual ergodic theorem is proved: this theorem can be failed for individual sequence if the deficiency of randomness of its initial fragments is not bounded. An analogous result holds also for the Shannon--McMillan-Breiman theorem.
The hypothesis is formulated that in any realizator of the set of circulant nxn matrixes (i.e., of matrixes with the same elements on any diagonal parallel of the main diagonal; and the elements are equal for any such two diagonals which are located on the distance n from each other) there exists a set of cardinality less or equal than exp(qn) for some q<1/2. The partial estimate exp(n^q) for each q<1/2 is proved.
Conditions on "self-definability" of the structure of real algebraic numbers are obtained, i.e., conditions for existence of a fixed formula F(∙) (where the argument (.) is an additional many-placed predicate variable P) such that F(P) is true in the structure if and only if the predicate P is definable in it.
It was shown that the complexity of the task
((a implies с) and (b implies d)) is not expressed trough the complexities of the elementary tasks a, b, c, d, their pairs, triples, the quadruple <a,b,c,d> and their conditional complexities with respect to each other.A new proof of decidability of the derivability problem for rules in the minimal normal modal logic K is obtained. The proof is an effective embedding of the rules of normal modal logic to the propositional dynamic logic, which is decidable as well-known.
The replacement theorem of equivalent strict implicative formulas in famous modal logic S3 is proved. (The full replacement theorem of equivalent formulas is not true.) For S3 29 strict implicative formulas with a one fixed variable which are not equivalent in pairs are found.
An elementary proof of Kripke lemma on finiteness of any incontractible sequence of words over a finite alphabet is obtained. The proof gives an analogous result for multisets instead of words. On this background the deductive system of S. Yu. Maslov that emerges in the mathematical modelling of the biological evolution was studied.
An optimal strategy for a game in dynamic systems with discrete time is constructed. It incorporates the approaches of the theory of nonantagonistic games and optimal control theory. The strategy is implemented in a computer algorithm.
Within the development of the concept of information transformers the problem of construction of an optimum measurement-computer system for an inexact measurement system is solved. The problem of an optimal calibration of invariant measurement systems is studied. Obtained algorithms were implemented on a computer.
It is also proved that a category of information transformers is a monoidal category of a special type. Sufficient conditions for a Kleisly category to be a monoidal category of information transformers are obtained. The most critical among these conditions is the existence of a natural transformation which assigns an "independent joint distribution" to a pair of "distributions".
PUBLICATIONS IN 2000