Проблема множественного выравнивания является одной из центральных проблем биоинформатики. Развитию математических алгоритмов для построения множественного выравнивания уделяется большое внимание и были разработаны различные математических методы. Динамическое программирование, прогрессивное выравнивание, итеративные методы, а также скрытые марковские модели и генетические алгоритмы наиболее часто используются для построения множественного выравнивания. Однако, все разработанные подходы в настоящее время методы и алгоритмы не позволят построить множественное выравнивание, если в анализируемых последовательностях отсутствует статистически значимое парное выравнивание. В этом случае невозможно построить статистически значимое направляющее дерево (guide tree) для прогрессивного выравнивания. Если последовательности сильно различаются, то также невозможно найти статистически значимые "зародыши" или же общие "слова". Получается, что построить множественное выравнивание для сильно отличающихся последовательностей в настоящее время крайне трудно или невозможно. Под сильно различающимися последовательностями будем понимать последовательности, накопившие более 2.5 случайных замен (x) на один нуклеотид относительно друг друга (x>2.5). Найти такое выравнивание можно было бы, если построить множественное выравнивание с применением N-мерного динамического программирования для всех анализируемых последовательностей. Но такой подход требует огромных компьютерных ресурсов и в настоящее время его реализация невозможна. Получается, что в современных методах развитых для множественного выравнивания аминокислотных или нуклеотидных последовательностей присутствует определенный пробел. В настоящей работе мы восполнили этот пробел и разработали математический метод для создания множественного выравнивания для сильно различающихся последовательностей (MAHDS), который позволяет построить множественные выравнивания для таких последовательностей, где любое парное выравнивание не обладает достаточной статистической значимостью. Мы изучили возможности программ ClustalW, Clustal-omega, T-coffee, Kalign, Mafft, Muscle and AllAlign и некоторых других по созданию множественного выравнивания нуклеотидных и аминокислотных последовательностей в зависимости от степени их эволюционной дивергенции (x). Удалось показать, что эти программы хорошо работают до значений x<2.4. Однако MAHDS позволяет строить статистически значимые выравнивания при степени эволюционной дивергенции x в интервале от 2.4 до 4.4. Это открывает новые возможности для изучения эволюционной дивергенции как нуклеотидных, так и аминокислотных последовательностей.

Основная идея метода MAHDS состоит в том, чтобы найти такой образ множественного выравнивания случайных последовательностей который бы наиболее точно описывал множественное выравнивание анализируемых последовательностей. В этом случае мы не строим множественное выравнивание для анализируемых последовательностей каким-либо методом, а только оптимизируем какие-либо образы множественных выравниваний. Оптимизация заключается в том, чтобы брать образы различных множественных выравниваний и адаптировать их к имеющимся последовательностям. В качестве оптимального множественного выравнивания для анализируемых последовательностей удобно брать такой образ (или PWM), который будет иметь экстремум функции сходства.

Разработанный нами математический метод был применен для выравнивания промоторных последовательностей из геномов A.thaliana [Korotkov и др., 2021a], Oriza sativa [Korotkov и др., 2021b], Capsicum annuum [Rudenko, Korotkov, 2022]. Промоторные последовательности были взяты из банка данных EPD (https://epd.epfl.ch//index.php). В данной работе показано, что многие районы промоторных последовательностей от -499 до +1 являются сильно консервативными. Также участки от +1 до +70 вносят большой вклад в создание множественного выравнивания промоторов. Всего удалось получить от 5 до 16 классов множественных выравниваний промоторов для изученных геномов, которые содержат от 55 до 75% известных промоторов. Созданные множественные выравнивания были использованы для поиска потенциальных промоторных последовательностей в геноме риса [Korotkov и др., 2021b]. В геноме Oriza sativa было обнаружено 145277 потенциальных промоторных последовательностей (ППП). Из них 18563 есть промоторные последовательности известных генов, 87,233 ППП входят в состав транспозонов и 37390 ППС найдены в неаннотированных последовательностях. Для генома Capsicum annuum (размер генома ~3 миллиарда нуклеотидов) число ППП примерно 960 тысяч при числе ложных позитивов менее 1%. Для генома человека нами было найдено ППП более 1 миллиона.

Разработанный метод был также применен для выравнивания аминокислотных последовательностей из сильно дивергировавших белковых семейств [Kostenko, Korotkov, 2022]. Было показано на примере 21 белкового семейства, что MASHDS позволяет найти более статистически значимые выравнивания, чем все ранее разработанные методы. Любой пользователь может построить множественное выравнивание методом MAHDS на сайте http://victoria.biengi.ac.ru/mahds/auth.



1. Korotkov E. V. и др. Multiple alignment of promoter sequences from the arabidopsis thaliana l. Genome // Genes (Basel). 2021a. Т. 12. № 2. С. 1–21.

2. Korotkov E. V. и др. Mathematical Algorithm for Identification of Eukaryotic Promoter Sequences // Symmetry 2021, Vol. 13, Page 917. 2021b. Т. 13. № 6. С. 917.

3. Kostenko D.O., Korotkov E. V. Application of the MAHDS Method for Multiple Alignment of Highly Diverged Amino Acid Sequences // Int. J. Mol. Sci. 2022. Т. 23. № 7. С. 3764.

4. Rudenko V., Korotkov E. Database of Potential Promoter Sequences in the Capsicum annuum Genome // Biol. 2022, Vol. 11, Page 1117. 2022. Т. 11. № 8. С. 1117.

The problem of multiple alignment is one of the central problems of bioinformatics. Much attention has been paid to the development of mathematical algorithms for constructing multiple alignments, and various mathematical methods have been developed. Dynamic programming, progressive alignment, iterative methods, as well as hidden Markov models and genetic algorithms are most commonly used to construct multiple alignments. However, all currently developed approaches, methods and algorithms will not allow building multiple alignment if there is no statistically significant pairwise alignment in the analyzed sequences. In this case, it is not possible to construct a statistically significant guide tree for progressive alignment. If the sequences are very different, then it is also impossible to find statistically significant "seeds" or common "words". It turns out that it is currently extremely difficult or impossible to build a multiple alignment for very different sequences. By strongly differing sequences we mean sequences that have accumulated more than 2.5 random substitutions (x) per nucleotide relative to each other (x>2.5). It would be possible to find such an alignment by constructing a multiple alignment using N-dimensional dynamic programming for all analyzed sequences. But such an approach requires huge computer resources and is currently impossible to implement. It turns out that in modern methods developed for multiple alignment of amino acid or nucleotide sequences there is a certain gap. In the present work, we filled this gap and developed a mathematical method for generating multiple alignments for highly diverged sequences (MAHDS), which allows the construction of multiple alignments for such sequences where any pairwise alignment does not have sufficient statistical significance. We explored the possibilities of ClustalW, Clustal-omega, T-coffee, Kalign, Mafft, Muscle and AllAlign and some other programs to create multiple alignments of nucleotide and amino acid sequences depending on the degree of their evolutionary divergence (x). It was possible to show that these programs work well up to x<2.0. However, MAHDS makes it possible to build statistically significant alignments for the degree of evolutionary divergence x in the range from 2.5 to 4.4. This opens up new possibilities for studying the evolutionary divergence of both nucleotide and amino acid sequences.

The main idea of the MAHDS method is to find such an image of the multiple alignment of random sequences that would most accurately describe the multiple alignment of the analyzed sequences. In this case, we do not build a multiple alignment for the analyzed sequences by any method, but only optimize some images of multiple alignments. The optimization is to take images of different multiple alignments and adapt them to the available sequences. As an optimal multiple alignment for the analyzed sequences, it is convenient to take such a pattern (or PWM) that will have an extremum of the similarity function.

The mathematical method we developed was applied to align promoter sequences from the genomes of A. thaliana [Korotkov et al., 2021a], Oriza sativa [Korotkov et al., 2021b], Capsicum annuum [Rudenko, Korotkov, 2022]. Promoter sequences were taken from the EPD databank (https://epd.epfl.ch//index.php). This work shows that many regions of promoter sequences from -499 to +1 are highly conserved. Also, the +1 to +70 regions contribute greatly to creating a multiple promoter alignment. In total, it was possible to obtain from 5 to 16 classes of multiple promoter alignments for the studied genomes, which contain from 55 to 75% of known promoters. The generated multiple alignments were used to search for potential promoter sequences in the rice genome [Korotkov et al., 2021b]. In the genome of Oriza sativa, 145277 potential promoter sequences (PPS) were found. Of these, 18,563 are promoter sequences of known genes, 87,233 PPPs are part of transposons, and 37,390 PPPs are found in unannotated sequences. For the Capsicum annuum genome (genome size ~3 billion nucleotides), the number of PPPs is approximately 960 thousand, with the number of false positives less than 1%. For the human genome, we have found more than 1 million PPPs.

The developed method was also applied to align amino acid sequences from highly divergent protein families [Kostenko and Korotkov, 2022]. Using 21 protein families as an example, it was shown that MASHDS allows finding more statistically significant alignments than all previously developed methods. Any user can build a multiple alignment using the MAHDS method at http://victoria.biengi.ac.ru/mahds/auth.

1. Korotkov E. V. и др. Multiple alignment of promoter sequences from the arabidopsis thaliana l. Genome // Genes (Basel). 2021a. Т. 12. № 2. С. 1–21.

2. Korotkov E. V. и др. Mathematical Algorithm for Identification of Eukaryotic Promoter Sequences // Symmetry 2021, Vol. 13, Page 917. 2021b. Т. 13. № 6. С. 917.

3. Kostenko D.O., Korotkov E. V. Application of the MAHDS Method for Multiple Alignment of Highly Diverged Amino Acid Sequences // Int. J. Mol. Sci. 2022. Т. 23. № 7. С. 3764.

4. Rudenko V., Korotkov E. Database of Potential Promoter Sequences in the Capsicum annuum Genome // Biol. 2022, Vol. 11, Page 1117. 2022. Т. 11. № 8. С. 1117.