[Protein families specific for plastoms in small taxonomy groups of algae and protozoa].

Protein clustering is useful for refinement of protein annotation as well as cluster finding by its phylogenetic profile. We performed clustering of plastid encoded proteins from Rhodophyta as well as other plastid containing species related to Rhodophyta branch on species tree. Data base for cluster finding by its phylogenetic profile is available on http://lab6.iitp.ru/ppc/redline. By means of the database distinctive proteins for plastoms from small taxonomy groups of algae and protozoa were found. We performed finding and analysis of RNA polymerases encoded in Apicomplexa nuclei.

[A fast algorithm to build a supertree with a set of gene trees].

Important desired properties of an algorithm to construct a supertree (species tree) by reconciling input trees are its low complexity and applicability to large biological data. In its common statement the problem is proved to be NP-hard, i.e. to have an exponential complexity in practice. We propose a reformulation of the supertree building problem that allows a computationally effective solution. We introduce a biologically natural requirement that the supertree is sought for such that it does not contain clades incompatible with those existing in the input trees. The algorithm was tested with simulated and biological trees and was shown to possess an almost square complexity even if horizontal transfers are allowed. If HGTs are not assumed, the algorithm is mathematically correct and possesses the longest running time of n3 x[V0]3, where n is the number of input trees and [V0] is the total number of species. The authors are unaware of analogous solutions in published evidence. The corresponding inferring program, its usage examples and manual are freely available at http://lab6.iitp.ru/en/super3gl. The available program does not implement HGTs. The generalized case is described in the publication "A tree nearest in average to a set of trees" (Information Transmission Problems, 2011).

[Attenuation regulation of amino acid and amino acyl-tRNA biosynthetic operons in bacteria: comparative genomics analysis].

We performed a large-scale search for attenuation regulation in bacteria based on two original computer programs modeling attenuation regulation and multiple alignment along a phylogenetic tree. The programs are available from http://lab6.iitp.ru. Candidate attenuations are predicted in many bacteria from alpha-, beta-, gamma-, delta-proteobacteria, Actinobacteria, Bacteroidetes/Chlorobi, Firmicutes and Thermotogae; in Cloroflexi--upstream genes hisG, hisZ, hisS, pheA, pheST, trpEG, trpA, trpB, trpE, trpS, thrA, thrS, leuA, leuS, ilvB, ilvI, ilvA, ilvC, ilvD, ilvG. Other bacterial taxa were not predicted to have attenuation; searches were conducted across all bacterial genomes contained in GenBank, NCBI. Evolution of attenuation is discussed.

[Reconstructing genes evolution along a species tree].

A model and algorithm are proposed to infer evolution of a gene family, given the gene tree, with respect to species evolution, given the species tree. The model describes such evolution using the "nested tree" concept. Performance of the algorithm is verified on several orthologous protein groups. The evolutionary events inferred are: speciation, gene duplication and loss, horizontal gene transfer retaining the original gene copy. A transfer event with the loss of original gene copy is considered a combination of gene transfer and loss. The model maps gene evolution events onto the species phylogeny.

[Modeling evolution of regulatory signals for gene expression in bacteria].

A model of evolution of a regulatory signal along the phylogenetic tree of species taking into account the secondary RNA structure is suggested. Based on this model, an algorithm is presented. It inputs the extant primary structure of a signal for the leaves of the phylogenetic tree and computes the primary and secondary structures of all the nodes. Another result of the algorithm is a multiple alignment of extant sites of a regulatory signal taking into account the secondary structure of the signal. The algorithm ha s been implemented and successfully tested on biological data representing three types of regulation in bacteria.

[Mechanism of manganese transport regulation based on the long RNA helix in Brucella].

It has been found that divalent cation transporters of the Nramp family in cell phagosomes and bacteria that parasitize on the cell compete for metals, which is crucial for bacterial survival. Long helices were determined by means of our algorithm for each mRNA in the 5'-untranslated region in Brucella. Conserved long RNA helices were found in mRNA that encode manganese transporters as well as Ni-dependent Glyoxalase I. We suggest that long helices in these regions are involved in the regulation of RNA stability.

[Model of genes expression regulation in bacteria by means of formation of secondary RNA structures].

In this article a model, first, classical attenuation RNA regulation of gene expression by means of transcription termination is offered. The model bases on representation about a macrostate of secondary structure in RNA regulatory region between a ribosome and a RNA polymerase, on the formulas of a resonant type defining the value of deceleration of a RNA polymerase by a set of hairpins in the same region. The special attention is given to selection of parameters of model. To check of model the computer simulation is carried out and the dependences of transcription termination probability from the value of concentration charged tRNA are obtained, in particular, and from concentration of amino acid for many regulatory regions in genomes of bacteria (here data are presented for trpE genes in Streptomyces spp., Bradyrhizobium japonicum and Escherichia coli) and at various values of three parameters, which authors consider as the main. The obtained dependences are compounded with the accessible experimental data; including, under the form of the graphs concerning to activity of an enzyme depending on concentration of amino acid (for example, anthranilate synthase from tryptophan in S. venezuela). One possible usage: now attenuation is predicted usually by means of multiple alignment, it needs some sequences; the obtaining with the help of model on an individual sequence characteristic for attenuation or its absence of a curve at approaching parameters could be considered as argument for the benefit of presence or absence of attenuation.

[Identification of ancestral genes untroducing incongruence between gene and species tree].

The article introduces two novel approaches to detect potential incongruence between the protein family tree and the species tree. The first approach implements substitution of a known mapping of gene tree G into species tree S with somewhat analogous multivalued G-into-S "mapping". The second approach is based on elementary concepts from the fuzzy-set theory. Detailed description of the two corresponding algorithms is provided with demonstration of their performance on a model example and on three biological COGs.

[Computer analysis of regulating metabolism of glycerol-3-phosphate in proteobacteria genome]. / Komp'iuternyi analiz reguliatsii metabolizma glitserol-3-fosfata v genomakh proteobakterii.

Comparative computer-assisted analysis was used to study putative GlpR-regulons responsible for metabolism of glycerol and glycerol-3-phosphate in genomes of alpha-, beta-, and gamma-proteobacteria. New palindromic GlpR-binding signals were identified in gamma-proteobacteria; consensus sequences being TGTTCGATAACGAACA for Enterobacteriaceae, wTTTTCGTATACGAAAAw for Pseudomonadaceae, and AATGCTCGATCGAGCATT for Vibrionaceae. The signals in alpha- and beta-proteobacteria were also identified: they contained 3-4 direct TTTCGTT repeats separated by 3-4 nucleotide pairs.

[Search for alternative secondary structures of RNA, regulating expression of bacterial genes]. / Poisk al'ternativnykh vtorichnykh struktur RNK, reguliruiushchikh ékspressiiu bakterial'nykh genov.

Expression of many bacterial genes is regulated by formation of alternative secondary RNA structure within the leader mRNA sequence. Our algorithm designed to search for these structures (basing on analysis of one nucleotide sequence) was applied to analyze operons of amino acid biosynthesis in alpha- and gamma-proteobacteria. The attenuators of these operons are predicted for genomes of some poorly known gamma-proteobacteria including Shewanella putrefaciens, attenuators of the tryptophan operon in some alpha-proteobacteria are also predicted.

[Search for conservative secondary structures of RNA]. / Poisk konservativnykh vtorichnykh struktur RNK.

We suggest a new algorithm to search a given set of the RNA sequences for conserved secondary structures. The algorithm is based on alignment of the sequences for potential helical strands. This procedure can be used to search for new structured RNAs and new regulatory elements. It is efficient for the genome-scale analysis. The results of various tests run with this algorithm are shown.

[Identification of the horizontal gene transfer based on phylogenetic data]. / Identifikatsiia gorizontal'no perenesennykh genov na osnove filogeneticheskikh dannykh.

We suggest a new procedure to search for the genes with horizontal transfer events in their evolutionary history. The search is based on analysis of topology difference between the phylogenetic trees of gene (protein) groups and the corresponding phylogenetic species trees. Numeric values are introduced to measure the discrepancy between the trees. This approach was applied to analyze 40 prokaryotic genomes classified into 132 classes of orthologs. This resulted in a list of the candidate genes for which the hypothesis of horizontal transfer in evolution looks true.

[Tree reconciliation: reconstruction of species evolution by phylogenetic gene trees]. / Soglasovanie derev'ev: rekonstruktsiia évoliutsii vidov po filogeneticheskim derev'iam genov.

It is well known that phylogenetic trees derived from different protein families are often incongruent. This is explained by mapping errors and by the essential processes of gene duplication, loss, and horizontal transfer. Therefore, the problem is to derive a "consensus" tree best fitting the given set of gene trees. This work presents a new method of deriving this tree. The method is different from the existing ones, since it considers not only the topology of the initial gene trees, but also the reliability of their branches. Thereby one can explicitly take into account the possible errors in the gene trees caused by the absence of reliable models of sequence evolution, by uneven evolution of different gene families and taxonomic groups, etc.

[Algorithms for isolating regulatory signals in DNA sequences]. / Algoritm vydeleniia reguliatornykh signalov v posledovatel'nostiakh DNK.

An algorithm is proposed for extracting regulatory signals from DNA sequences. The algorithm complexity is nearly quadratic. The results of testing the algorithm on artificial and natural sequences are presented.