In this study, we developed a new mathematical method for performing multiple alignment of highly divergent sequences (MAHDS), i.e., sequences that have on average more than 2.5 substitutions per position (x). We generated sets of artificial DNA sequences with x ranging from 0 to 4.4 and applied MAHDS as well as currently used multiple sequence alignment algorithms, including ClustalW, MAFFT, T-Coffee, Kalign, and Muscle to these sets. The results indicated that most of the existing methods could produce statistically significant alignments only for the sets with x < 2.5, whereas MAHDS could operate on sequences with x = 4.4. We also used MAHDS to analyze a set of promoter sequences from the Arabidopsis thaliana genome and discovered many conserved regions upstream of the transcription initiation site (from −499 to +1 bp); a part of the downstream region (from +1 to +70 bp) also significantly contributed to the obtained alignments. The possibilities of applying the newly developed method for the identification of promoter sequences in any genome are discussed. A server for multiple alignment of nucleotide sequences has been created.

We have developed a de novo method for the identification of dispersed repeats based on the use of random position-weight matrices (PWMs) and an iterative procedure (IP). The created algorithm (IP method) allows detection of dispersed repeats for which the average number of substitutions between any two repeats per nucleotide (x) is less than or equal to 1.5. We have shown that all previously developed methods and algorithms (RED, RECON, and some others) can only find dispersed repeats for x ≤ 1.0. We applied the IP method to find dispersed repeats in the genomes of E. coli and nine other bacterial species. We identify three families of approximately 1.09 × 10⁶, 0.64 × 10⁶, and 0.58 × 10⁶ DNA bases, respectively, constituting almost 50% of the complete E. coli genome. The length of the repeats is in the range of 400 to 600 bp. Other analyzed bacterial genomes contain one to three families of dispersed repeats with a total number of 10³ to 6 × 10³ copies. The existence of such highly divergent repeats could be associated with the presence of a single-type triplet periodicity in various genes or with the packing of bacterial DNA into a nucleoid.

Statistically significant multiple sequence alignment construction is an important task that has many biological applications. We applied the method for multiple alignments of highly divergent sequences (MAHDS) to construct multiple sequence alignments (MSAs) for 490 protein families with less than 20% identity between family members. The method uses random symmetric position–weight matrices (PWMs) and a genetic algorithm to construct a multiple alignment. PWM symmetry is essential because it makes PWMs comparable and recoverable at all steps of the MAHDS algorithm, which reduces the optimal MSA search task to a PWM optimization task. A Monte Carlo method is applied to assess the statistical significance of the resulting alignments. The statistical significance of the constructed MSAs was compared with that of MSAs obtained using T-Coffee and MUSCLE algorithms. The results showed that for 476 of the 490 families, the MAHDS method created much more statistically significant MSAs than T-Coffee and MUSCLE, whereas for 138 families, only MAHDS could construct statistically significant MSAs. These findings indicate that MAHDS calculate statistically significant alignments in cases when the other methods create purely random MSAs and are, therefore, the most appropriate method to construct MSAs for families of proteins with weak sequence similarities for amino acid annotation.

Proteomes are typically analyzed at the level of individual proteins or protein families. In this study, we introduce a bottom-up approach that treats proteomes as holistic entities by examining the properties of k-mers within entire proteomes and protein groups. We performed a comprehensive analysis of short amino acid k-mer (k = 1, 2, 3) distributions across all proteins in a given proteome. Using 86 bacterial proteomes representing 18 clades, we evaluated whether k-mer frequencies characterize uniquely the analyzed organisms. Remarkably, in a post hoc analysis, we found that the k-mer frequency vector unambiguously coevolves with the entire proteome—a pattern not observed even within specific protein groups, such as conserved ribosomal proteins or more variable nucleotide-binding proteins. This finding holds regardless of the k-mer calculation parameters or the distance metrics employed. Our results show that even a simple analysis based on tripeptide frequencies can precisely position proteomes within the k-mer space. Moreover, relationships derived from k-mer comparisons highly correlate with evolutionary relationships derived from phylogenetic trees, reaching up to 99% match with reference classification of the proteomes within major bacterial clades. These findings establish k-mer-based proteomic analysis as an additional robust and powerful feature for characterizing evolutionary relationships, opening new pathways in phylogenetics and evolutionary genomics.

In this work, we searched for and analyzed highly divergent dispersed repeats (DRs) in the genomes of four plants: Arabidopsis thaliana, Capsicum annuum, Daucus carota, and Zea mays. DRs were detected using the iterative procedure method which has shown efficacy in searches for highly divergent repeats in bacteria and algae. The results indicated that the number of DRs in the plant genomes depended on the genome size, whereas the number of repeat families did not. The DRs covered from 36 to 50% of the studied genomes. The shortest repeats were observed in the D. carota genome, but their consensus lengths were similar to those in the other species. Analysis of periodicity in various DR families showed that most periods were 3 bp long. We created a database of the detected DRs, which contains 5,392,216 DRs grouped in 150 families and which can be accessed on the Research Center of Biotechnology RAS server. The server makes it possible to search for repeats based on various criteria and to download the obtained data.