Алгоритмы первой группы, как правило, базируются на процедурах динамического программирования (типа Нидельмана — Вунша [1, 2]) и требуют назначения величины штрафа за введение пробелов в выравненные последовательности (соответствующих делециям или вставкам остатков). Результат выравнивания существенно зависит от величины штрафа, но в то же время нет никаких сколько-нибудь серьезных оснований для выбора этой величины. Другой недостаток одноэтапных алгоритмов — это то, что обычно в них множественное выравнивание делается последовательно: сначала выравниваются две самые близкие последовательности, затем эта пара как целое выравнивается с третьей, затем тройка как целое выравнивается с четвертой и т. д. Если на одном из шагов выравнивание в каком-то месте было сделано неудачно, то в дальнейшем в этом месте оно будет все более искажаться.

В представляемом ниже алгоритме, относящемся ко второй группе методов, консенсусные участки, по нашему мнению, ищутся более полно и точно, чем обычно. Наш метод исходит из построения попарных карт локального сходства и основан на алгоритме DotHelix [5].

                                                                                    (1)

где А — мощность рассматриваемого консенсуса; L — длина консенсуса, т. е. общая длина входящих в него фрагментов; k — толщина консенсуса, т. е. число входящих в него слоев; b_1r, b₂,_r, ... , b_L,,_r — буквы (остатки), составляющие r-й слой консенсуса; r _b,c— вес за замену буквы b на

т = М (r ) = å r _{b, c} • p_b • р_с —                                                                                          (2)

D = k· (k- l)/2 · D (r ) + k · (k- l) · (k-2) · cov(r ₁₂ ,r ₁₃)=

= k· (k- l)/2 · å ( r _{b, c} - m)² • p_b • р_с + k · (k- l) · (k-2) x

                          b,с

x å ( r _{b, c}1 - m) • ( r _{b, c}2 - m)• p_b • р_с1 • р_{с 2} ;

p_b— частота буквы bво всем наборе последовательностей.

Для случая консенсуса толщины два обоснование этого определения приведено в [5]. Следует сказать, что формула (1) несколько огрублена по сравнению с аналогичной формулой в [5]: в формуле (1) частоты вхождения букв р_ь предполагаются одинаковыми для всех выравниваемых последовательностей. Это сделано для ускорения времени счета; такое огрубление слабо влияет на точность оценок мощности консенсусов.

Из вышеизложенного вытекает, что при поиске правильного выравнивания естественно сначала находить все консенсусные участки без пробелов, а затем цепочку из таких участков достроить до полного выравнивания последовательностей, вставляя необходимое число пробелов в зонах между этими участками. При этом из биологических соображений ясно, что в правильном выравнивании родственных последовательностей, с одной стороны, консенсусы должны быть по возможности более мощными и, с другой — пробелов должно быть немного.

Начнем с первого этапа. Для нахождения всех возможных в данном наборе последовательностей консенсусов следовало бы просмотреть все “регистры сравнения” (возможные сдвиги исходных последовательностей относительно друг друга) и для каждого из них искать совокупность непересекающихся достаточно мощных консенсусов, что можно сделать, например, с помощью программы DotHelix [5]. Однако такая процедура требует даже при сравнительно небольшом числе последовательностей (t³ 3) весьма большого времени счета, поскольку велико число разных регистров сравнения — оно порядка п^t-1, где п — средняя длина последовательности. Чтобы избежать полного перебора всех регистров сравнения, предлагается использовать последовательную процедуру нахождения наиболее мощных консенсусов. Эта процедура основана на том обстоятельстве, что в мощном консенсусе каждая или почти каждая пара слоев значимо похожи.

Соответствующий алгоритм заключается в следующем. Для каждой пары последовательностей из набора методом DotHelix находим все сходные фрагменты этих последовательностей на сравнительно низком уровне значимости. Тем самым будут найдены все достаточно мощные

Опишем более подробно процедуру присоединения нового слоя. Ее проводили методом DotHelix [5], но по несколько другим правилам вычисления мощности (которую мы будем называть “мощностью подцепления”) . Консенсус, продолженный в обе стороны на несколько позиций, сдвигается относительно сравниваемой последовательности, и для каждого сдвига формируется диагональ карты локального сходства консенсуса и этой последовательности (для сравнения см. [5]); числа а_i,j , заполняющие карту локального сходства, являются суммами весов за замены букв из i-го столбца консенсуса на букву из j-й позиции сравниваемой последовательности:

где k — число слоев консенсуса, b_ir — буква, стоящая в r-м слое i-м столбце консенсуса, с_j — буква, стоящая в j-й позиции сравниваемой с консенсусом последовательности, р_b,с — вес за замену буквы b на букву с. Как было указано выше, формула для мощности подцепления несколько отличается от приведенной выше формулы (1) для мощности консенсуса. Это связано с тем, что слои консенсуса нельзя рассматривать как независимые бернуллиевские последовательности (например, вполне реальная ситуация, когда все слои консенсуса в точности совпадают между собой). Поэтому консенсус следует рассматривать не как набор случайных, а как набор фиксированных последовательностей, состоящих из букв b_i,r. В то же время вполне естественно представлять сравниваемую последовательность бернуллиевской и независимой от слоев консенсуса. В результате вместо формулы (1) мощность подцепления следовало бы вычислять так:

где L — длина отрезка диагонали, мощность которого мы вычисляем;

p_c —частота буквы с.

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

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

Мы вычисляем эту величину n_eq исходя из мощности консенсуса, предполагая, что такое значение мощности и соответствующее значение нормированной суммы весов (стоящей в числителе формулы (1)) про-исходит только за счет точных совпадений букв (конечно, и это пред-положение является лишь приближенным); из этого предположения легко следует, что

где m_eq = å r _b,b— среднее значение весов r _{ь ь} , т вычисляется по формуле (2,

S — нормированная сумма весов для консенсуса, получаемая из значения его мощности (см. формулу (1)).

В результате всей этой работы мы получим некоторую совокупность консенсусов разной толщины; каждому консенсусу соответствует его мощность, рассчитанная уже по формуле (1). Неполная толщина консенсуса в окончательном наборе означает, что входящие в него последовательности заведомо имеют хорошее соответствие между собой в этом месте; что же касается пропущенных в этом консенсусе последовательностей, то хорошего соответствия со слоями консенсуса там нет.

Говоря метафорически, в предложенном нами способе поиска консенсусов из рассмотрения всевозможных пар последовательностей намечаются потенциальные зоны сходства, а потом некоторые из них все более проявляются за счет сходств этого участка с фрагментами из других последовательностей, а другие стираются ввиду отсутствия дополнительных сходств.

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

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

В итоге мы получим набор выравниваний с максимально возможным включением в каждый из построенных на первом этапе консенсусов (максимальность понимается в том смысле, что цепочки насыщены — больше добавить туда консенсусов нельзя). Мерой качества выравнивания служит нормированная сумма попарных весов за замены букв из всех столбцов консенсусов соответствующей цепочки (сравни с формулой (1); в качестве длины L берется общая длина выравненных последовательностей) . Видно, что при таком определении хорошее качество имеют такие выравнивания, в которые по возможности входят мощные консенсусы при небольшом числе вставленных пробелов.

Данный алгоритм реализован на языке Си для компьютеров типа IBM PC в виде программы H-Align из пакета программ для анализа последовательностей биополимеров GenBee, разработанного в НПК “Комби”.

“мутировали”: около 45% букв было заменено дефисами — символами “—”. На следующем шаге все дефисы были убраны. В результате получились более короткие последовательности с длинами 43, 53, 66 и 75 букв. Эти последовательности и взяты как исходные для выравнивания. Схема модели приведена на рис. 1.

Результаты работы по программе H-Align представлены на рис. 2, где изображены два набора выравненных последовательностей, полученные с использованием разных матриц весов за замены остатков: матрицы Дэйхофф [6] и единичной матрицы (в ней вес за совпадение букв равен единице, а за несовпадение — нулю). В обоих изображенных наборах выравненных последовательностей большими буквами показаны места, входящие в консенсусы, а маленькими — в межконсенсусные участки.

1:GDVEKGKKIFIMKCSQCHTVEKGGKHKTGPNLHGLFGRKTGQAPGYSYTAANKNKGIIWG 
1:GDVEKGKKIFVQKCAQCHTVEKGGKHKTGPNLHGLFGRKTGQAPGFSYTDANKNKGITWG 
1:GDIEKGKKIFYQKCSQCHTVEKGGKHKTGPNLHGLFGRKTGQAEGFSYTDANKNKGITWG 
1:GDVEKGKKIPVQKCSQCHTVEKGGKHKTGPNLHGLFGRKTGQAEGFSYTDANKNKGITWG

61:EDTLMEYLENPKKYIFGTKMIPVGIKKKEERADLIAYLKKATNE
61:EETLMEYLENPKKYIPGTKMIFAGIKKTGERADLIAYLKKATKE
61:EDTLMEYLENPKKYIPGTKMIFAGIKKKSERVDLIAYLKDATSK
61:EDTLMEYLENPKKYIPGTKMIFAGIKKKSERADLIAYLKDATAK

1:----KGKKIF-------------GKHKTGPNLH------------------KNKGIIWG
1:GDV-KGKKIFVQK----TVEK--------NLHGLFGRKT---PGFSY----KNKGITWG
1:GD—KG----VQKCSQ—ТVEK-GКНKTGРNLH---GRKTG--—EGFS-----KNKGITWG
1:------KKIFVQKCSQ—TVEKG-----GPNLHG—GRKTGQAE-G---TDAN---GIT-G

61:-DTL--YLENPK-YIPGTKMIF--------RADLIAYLKKA---
61:E--------------------------------LIA--------
61:-DTL--YLEN----IPGTKMI--GIKKKSERVDLIAYLKDATS-
61:EDT--EYLEN----IPGTKMIFAGIKKKS-----------АТАК

1:KGKKIFGKHKTGPNLHKNKGIIWGDTLILENPKYIPGTKMIFRAD LIAYLKKA
1:GDVKGKKIFVQKTVEKNLHGLFGRKTPGFSYKNKGITWGELIA
1:GDKGVQKCSQTVEKGKHKTGPNLHGRKTGEGFSKNKGITWGDTLYLENIPGTKMIGIKKK 
1:KKIFVQKCSQTVEKGGPNLHGGRKTGQAEGTDANGITGEDTEYLENIFGTKMIPAGIKKK

61:
61:
61:SERVDLIAYLKDATS
61:SATAK

На рис. 2, кроме результатов выравнивания по программе H-Align, приведено также “истинное” выравнивание. Оно получается из образованных нами последовательностей с дефисами (второй набор последовательностей— на рис. 1) выбрасыванием столбцов, состоящих из одних дефисов.

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

1:kg---KKIP----------GKHKTGPNLH--------------KNKGIIWGDTLYLENpky
1:gdvkgKKIFVQKtv---------- EKNLHglfGRKtpgfsy-KNKGITWGE---------
1:gdkg-----VQKCSQTVekGKHKTGPNIH---GRKtgegfs--KNKGITWGDTLYLEN---
1:-----KKIFVQKCSQTV----EKGGPNIHg—GRKtggaegtda-N-GITGEDTEYLEN---

61:IPGTKMIfra--------DLIAYLKka--
61:-------------------LIA-------
61:IPGTKMI--GIKKKservDLIAYLKdats
61:IPGTKMIfaGIKKKsatak----------

1:kg---KKIP----------GKHKTGPNLH---------------KNKGIIWGDTLYLENpky
1:gdvkgKKIFVQK---TVEk-------NLHGlfGRKTpgfsy---KNKGITWGe---------
1:gdkg-----VQKCSQTVEkGKHKTGPNLH---GHKIGegfs---KNKGITWGDTLYLEN---
1:-----KKIFVQKCSQTVE----KGGPNLHG—GRKTGqaegtdan---GITgeDTEYLEN---

61:IPGTKMIFra--------DLIAYLKka—
61:-------------------LIA------
61:IPGTKMI—GIKKKServDLIAYLKdats
61:IPGTKMIFaGIKKKSatak---------

1:---KGKKIF-----------GKHKTGPNLH------------------KNKGIIWG-DT
1:GDVKGKKIFVQK---TVEK--------NLHGLFGRKT---PGFSY---KNKGITWGE--
1:GD-KG----VQKCSQTVEK-GKHKTGPNLH---GRKTG—EGFS-----KNKGITWG-DT
1:-----KKIFVQKCSQTVEKG-----GPNLHG—GRKTGQAEG---TDAN---GIT-GEDT

61:L--YLENPK-YIPGTKMIF--------RADLIAYLKKA---
61:------------------------------LIA--------
61:L--YLEN----IPGTKMI--GIKKKSERVDLIAYLKDATS-
61:--EYLEN----IPGTKMIFAGIKKKS-----------АТАК

Рис. 2. Результаты выравнивания по программе H-Align исходных последовательностей с использованием разных весовых матриц (Дэйхофф и единичной), а также “истинное” выравнивание

У роботi запропоновано новий алгоритм множинного вирiвнювання бiологiчних по-слiдовностей. В ньому спочатку на основi методу DotHelix будуються консенсуснi дiлянки в даному наборi послiдовностей piзнoi товщини i ступеня схожостi, а потiм iз цих консенсусiв складаються ланцюжки, погодженi з порядком букв в послiдовностях, i такi ланцюжки е каркасами вирiвнювання. На основi алгоритму на мовi Сi написана програма H-Align з пакету GenBee. Розглянутий модельний приклад iлюструе ефективнiсть запропонованого алгоритму.

Generalization of the multiple alignment is central to the entire field of biological sequence analysis. The algorithm of alignment by program H-align incorporated in GenBee package is a result of development of the local similarity search principle. It has two stages:

1) generalization of all the conservative regions (they cannot be present in all the aligning sequences).

2) optimal arrangement of these regions using two criteria — maximization of the total power of the conservative regions and minimization of the total number of spaces.

This algorithm has at least two advantages over traditional algorithms (such as Needleman-Wunsch's one) : no penalty for insertion / deletion; not subsequent pair aligning procedure. The efficiency of the algorithm is shown at model example.

1. Needleman S. В., Wunch C. D. A general method applicable to the search for similarities in the amino acid sequence of two proteins//J. Mol. Biol.— 1970.— 48, N 2.— P. 443—453.

2. Gotoh O. Alignment of three biological sequences with an efficient traseback procedure//J. Theor. Biol.—1986.—121, N 1.—P. 327—337.

3. Sobel E., Marttinez H. M. A multiple sequence alignment program//Nucl. Acids Res.— 1986.— 14, N 2.—P. 363—374.

4. Bacon D. /., Anderson W. J. Multiple sequence alignment//J. Mol Biol.— 1986 — 191, N 1.—P. 153—161.

5. Леонтович A. M., Бродский Л. И., Горбаленя А. Е. Построение полной карты локального сходства двух полимеров (программа DotHelix пакета GenBee // Биополимеры и клетка.— 1990.—6, № 6.—С. 14—21.

6. Dayhoff M. О., Barker W. С., Hunt L. Т. Establishing homologies in protein sequences //Meth. Enzymol.— 1983.— 91.— P. 524—545.