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

Ранее нами был разработан метод MAHDS, который позволяет строить множественные выравнивания за время, линейно зависящее от количества последовательностей и квадратично от их средней длины. Данный метод показал, что он способен строить статистически значимые выравнивания последовательностей ДНК даже c количеством замен на символ равным x=4.4. В то же время для других сравниваемых с MAHDS методов (T-Coffee, Muscle, ClustalW, MAFFT, Kalign) этот показатель составил x<2.5.

Мы адаптировали MAHDS для выравнивания аминокислотных последовательностей [1]. MAHDS сравнивался с методами построения множественных выравниваний, представленными на ресурсе EMBL-EBI, для которых доступно Web API. В их число входит T-Coffee, MUSCLE, PRANK, Clustal Omega, Kalign, MAFFT. Для сравнения MAHDS с другими методами построения выравниваний использовались следующие тестовые данные: база эталонных выравниваний белковых семейств BAliBASE, искусственные последовательности с определёнными свойствами и реальные белковые семейства с низким процентом идентичности (<20%), взятые из баз данных Pfam и HOMSTRAD. Для оценивания качества выравниваний использовались критерии CS и Z. CS отражает меру сходства двух выравниваний (эталонного и оцениваемого), а Z – статистическую значимость выравнивания.

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

Перед проведением дальнейших тестов по правилу 3 сигма был определён порог статистической значимости, при котором выравнивание можно считать не случайным. Для этого оценивалось Z выравниваний множеств случайных последовательностей. Порог Zt оказался равен 10.

Для тестирования на искусственных последовательностях из случайных предковых последовательностей генерировались множества потомков путём внесения случайных вставок, делеций и замен (в итоговое множество предковая последовательность не входила). Было сгенерировано 81 различное множество искусственных последовательностей. Длина родительской последовательности составляла 600 символов. Количество дочерних последовательностей – 100. Создавались множества со свойствами из следующего диапазона. Количество вставок (и столько же делеций): [2, 5, 10]. Длина вставок (и такая же у делеций): [1, 5, 20]. Количество замен на символ: [0.3, 0.6, 0.9, 1.2, 1.5, 1.8, 2.1, 2.4, 2.7], соответственно, расстояние x между дочерними последовательностями (в заменах на символ) в сгенерированных множествах последовательностей составляло [0.6, 1.2, 1.8, 2.4, 3.0, 3.6, 4.2, 4.8, 5.4]. Было показано, что MAHDS при малом количестве и длине вставок и делеций способен строить статистически значимые выравнивания даже при расстоянии между выравниваемыми последовательностями x=4.8 замен на символ. Из остальных протестированных методов, наилучшее результаты показал MUSCLE. В таких же условиях MUSCLE способен строить статистически значимые выравнивания при x=2.4 замен на символ, что существенно хуже, чем показатель MAHDS.

При тестировании на реальных белковых последовательностях мы сравнивали MAHDS с методами T-Coffee и MUSCLE, так как именно эти 2 метода показали хорошие результаты в предыдущих тестах. Мы построили выравнивания тремя методами для 21 белкового семейства и оценили Z полученных выравниваний. Для 16 из 21 семейств MAHDS построил наиболее статистически значимые выравнивания (для других 5 семейств либо выравнивания всеми методами оказались значимыми, либо наоборот незначимыми также у всех методов). В то же время для 4 семейств (PF00915, PF10846, PF10895 и PF13944) только MAHDS оказался способен построить статистически значимое выравнивание.



1. 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, 3764 https://doi.org/10.3390/ijms23073764.

Multiple sequences alignments construction is an important task of bioinformatics which allows one to find evolutionary and functional relationships in the chains of nucleic acids and proteins of living organisms. However, this problem is NP-complete. This means that the time it takes to compute its deterministic solution depends exponentially on the size of the input (in particular, the number of sequences). For this reason, all methods used in practice for constructing multiple alignments use a variety of heuristics that allow solving this problem in an acceptable time, but with a loss of accuracy.

Previously, we developed the MAHDS method, which allows building multiple alignments in a time that depends linearly on the number of sequences and quadratically on their average length. This method has shown that it is able to build statistically significant DNA sequence alignments even with x=4.4 substitutions per symbol. At the same time, for other methods compared with MAHDS (T-Coffee, Muscle, ClustalW, MAFFT, Kalign), this value was x<2.5.

We have adapted MAHDS for amino acid sequences alignment [1]. MAHDS was compared with the multiple alignment methods presented on the EMBL-EBI resource, for which a Web API is available. These include T-Coffee, MUSCLE, PRANK, Clustal Omega, Kalign, MAFFT. To compare MAHDS with other methods, the following test datasets were used: the BAliBASE database of reference protein family alignments, artificial sequences with certain properties, and real protein families with a low percentage of identity (<20%) taken from the Pfam and HOMSTRAD databases. The CS and Z criteria were used to evaluate the quality of the alignments. CS reflects the measure of similarity of two alignments (reference and estimated), and Z is the statistical significance of the alignment.

In the course of testing on BAliBASE, the average values of CS and Z were calculated for the alignments of all protein families presented in this database. The purpose of the testing was not only to compare MAHDS with other methods, but also to select the most biologically appropriate parameters of the MAHDS method (which also affect the Z score). For the selection of parameters, we maximized CS, trying to prevent significant drops in Z. We used fixed parameters that were selected at this step further in the research. In general MAHDS showed superiority in Z, but lagging behind in CS, in comparison with other methods in the context of BAliBASE.

Before conducting further tests a threshold of statistical significance was determined according to the 3-sigma rule. It shows Z at which the alignment can be considered non-random. Alignments of sets of random sequences were estimated for this. The Zt threshold turned out to be equal to 10.

For testing on artificial sequences, sets of descendants were generated from random ancestral sequences by adding random insertions, deletions, and substitutions (the ancestral sequence was not included in the final set). 81 different sets of artificial sequences were generated. The length of the ancestral sequence was 600 characters. The number of descendant sequences is 100. Sets were created with properties from the following range. Number of insertions (and the same number of deletions): [2, 5, 10]. Insertion length (and the same for deletions): [1,5,20]. The number of substitutions per character: [0.3, 0.6, 0.9, 1.2, 1.5, 1.8, 2.1, 2.4, 2.7], respectively, the distance x between descendant sequences (in substitutions per character) in the generated sets of sequences was [0.6, 1.2, 1.8, 2.4, 3.0, 3.6, 4.2, 4.8, 5.4]. It was shown that MAHDS, in cases of a small number and length of insertions and deletions, is able to build statistically significant alignments even when distance between aligned sequences is equal to x=4.8 substitutions per symbol. MUSCLE showed the best results among other methods. Under the same conditions, MUSCLE is able to build statistically significant alignments at x=2.4 substitutions per symbol, which is significantly worse than the MAHDS score.

In the context of testing MSA methods on real protein sequences, we compared MAHDS with the T-Coffee and MUSCLE methods, because these 2 methods showed good results in previous tests. We constructed alignments using three methods for 21 protein families and scored the resulting Z alignments. For 16 out of 21 families, MAHDS constructed the most statistically significant alignments (for the other 5 families, either alignments by all methods turned out to be significant, or vice versa, they were insignificant for all methods). At the same time, for 4 families (PF00915, PF10846, PF10895, and PF13944), only MAHDS was able to construct a statistically significant alignment.



1. 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, 3764 https://doi.org/10.3390/ijms23073764.