Новый метод множественного выравнивания последовательностей биополимеров (программа H-Align пакета GenBee )
В работе предложен новый алгоритм множественного выравнивания биологических последовательностей. В этом алгоритме вначале на основе метода DotHelix строятся консенсусные участки в данном наборе последовательностей разной толщины и разной степени сходства, а затем из этих консенсусов составляются цеп...
Saved in:
| Published in: | Биополимеры и клетка |
|---|---|
| Date: | 1991 |
| Main Authors: | , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут молекулярної біології і генетики НАН України
1991
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/152761 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Новый метод множественного выравнивания последовательностей биополимеров (программа H-Align пакета GenBee ) / Л.И. Бродский, А.Л. Драчев, А.М. Леонтович // Биополимеры и клетка. — 1991. — Т. 7, № 1. — С. 14-22. — Бібліогр.: 6 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-152761 |
|---|---|
| record_format |
dspace |
| spelling |
Бродский, Л.И. Драчев, А.Л. Леонтович, А.М. 2019-06-12T17:46:14Z 2019-06-12T17:46:14Z 1991 Новый метод множественного выравнивания последовательностей биополимеров (программа H-Align пакета GenBee ) / Л.И. Бродский, А.Л. Драчев, А.М. Леонтович // Биополимеры и клетка. — 1991. — Т. 7, № 1. — С. 14-22. — Бібліогр.: 6 назв. — рос. 0233-7657 http://dx.doi.org/10.7124/bc.000049 https://nasplib.isofts.kiev.ua/handle/123456789/152761 577.112 В работе предложен новый алгоритм множественного выравнивания биологических последовательностей. В этом алгоритме вначале на основе метода DotHelix строятся консенсусные участки в данном наборе последовательностей разной толщины и разной степени сходства, а затем из этих консенсусов составляются цепочки, согласованные с порядком букв в последовательностях, и такие цепочки являются каркасами выравниваний. На основе алгоритма на языке Си написана программа H-Align изпакета GenBee. Рассмотрен модельный пример, иллюстрирующий эффективность предложенного алгоритма. У роботі запропоновано новий алгоритм множинного вирівнювання біологічних послідовностей. В ньому спочатку на основі методу DotHelix будуються консенсусні ділянки в даному наборі послідовностей різної товщини і ступеня схожості, а потім із цих консенсусів складаються ланцюжки, погоджені з порядком букв в послідовностях, і такі ланцюжки є каркасами вирівнювання. На основі алгоритму на мові Ci написана програма H-Align з пакету GenBee. Розглянутий модельний приклад ілюструє ефективність запропонованого алгоритму. Summary 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. ru Інститут молекулярної біології і генетики НАН України Биополимеры и клетка Новый метод множественного выравнивания последовательностей биополимеров (программа H-Align пакета GenBee ) Новий метод множинного вирівнювання послідовностей біополімерів (програма H-Align пакету GenBee) A novel method of multiple sequence alighment of biopolymers (program H-Align of the GenBee package) Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Новый метод множественного выравнивания последовательностей биополимеров (программа H-Align пакета GenBee ) |
| spellingShingle |
Новый метод множественного выравнивания последовательностей биополимеров (программа H-Align пакета GenBee ) Бродский, Л.И. Драчев, А.Л. Леонтович, А.М. |
| title_short |
Новый метод множественного выравнивания последовательностей биополимеров (программа H-Align пакета GenBee ) |
| title_full |
Новый метод множественного выравнивания последовательностей биополимеров (программа H-Align пакета GenBee ) |
| title_fullStr |
Новый метод множественного выравнивания последовательностей биополимеров (программа H-Align пакета GenBee ) |
| title_full_unstemmed |
Новый метод множественного выравнивания последовательностей биополимеров (программа H-Align пакета GenBee ) |
| title_sort |
новый метод множественного выравнивания последовательностей биополимеров (программа h-align пакета genbee ) |
| author |
Бродский, Л.И. Драчев, А.Л. Леонтович, А.М. |
| author_facet |
Бродский, Л.И. Драчев, А.Л. Леонтович, А.М. |
| publishDate |
1991 |
| language |
Russian |
| container_title |
Биополимеры и клетка |
| publisher |
Інститут молекулярної біології і генетики НАН України |
| format |
Article |
| title_alt |
Новий метод множинного вирівнювання послідовностей біополімерів (програма H-Align пакету GenBee) A novel method of multiple sequence alighment of biopolymers (program H-Align of the GenBee package) |
| description |
В работе предложен новый алгоритм множественного выравнивания биологических последовательностей. В этом алгоритме вначале на основе метода DotHelix строятся консенсусные участки в данном наборе последовательностей разной толщины и разной степени сходства, а затем из этих консенсусов составляются цепочки, согласованные с порядком букв в последовательностях, и такие цепочки являются каркасами выравниваний. На основе алгоритма на языке Си написана программа H-Align изпакета GenBee. Рассмотрен модельный пример, иллюстрирующий эффективность предложенного алгоритма.
У роботі запропоновано новий алгоритм множинного вирівнювання біологічних послідовностей. В ньому спочатку на основі методу DotHelix будуються консенсусні ділянки в даному наборі послідовностей різної товщини і ступеня схожості, а потім із цих консенсусів складаються ланцюжки, погоджені з порядком букв в послідовностях, і такі ланцюжки є каркасами вирівнювання. На основі алгоритму на мові Ci написана програма H-Align з пакету GenBee. Розглянутий модельний приклад ілюструє ефективність запропонованого алгоритму.
Summary 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.
|
| issn |
0233-7657 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/152761 |
| citation_txt |
Новый метод множественного выравнивания последовательностей биополимеров (программа H-Align пакета GenBee ) / Л.И. Бродский, А.Л. Драчев, А.М. Леонтович // Биополимеры и клетка. — 1991. — Т. 7, № 1. — С. 14-22. — Бібліогр.: 6 назв. — рос. |
| work_keys_str_mv |
AT brodskiili novyimetodmnožestvennogovyravnivaniâposledovatelʹnosteibiopolimerovprogrammahalignpaketagenbee AT dračeval novyimetodmnožestvennogovyravnivaniâposledovatelʹnosteibiopolimerovprogrammahalignpaketagenbee AT leontovičam novyimetodmnožestvennogovyravnivaniâposledovatelʹnosteibiopolimerovprogrammahalignpaketagenbee AT brodskiili noviimetodmnožinnogovirívnûvannâposlídovnosteibíopolímerívprogramahalignpaketugenbee AT dračeval noviimetodmnožinnogovirívnûvannâposlídovnosteibíopolímerívprogramahalignpaketugenbee AT leontovičam noviimetodmnožinnogovirívnûvannâposlídovnosteibíopolímerívprogramahalignpaketugenbee AT brodskiili anovelmethodofmultiplesequencealighmentofbiopolymersprogramhalignofthegenbeepackage AT dračeval anovelmethodofmultiplesequencealighmentofbiopolymersprogramhalignofthegenbeepackage AT leontovičam anovelmethodofmultiplesequencealighmentofbiopolymersprogramhalignofthegenbeepackage |
| first_indexed |
2025-11-26T02:09:09Z |
| last_indexed |
2025-11-26T02:09:09Z |
| _version_ |
1850608135374372864 |
| fulltext |
Р е з ю м е
В роботі описується пакет програм GenBee, призначений для аналізу біологічних по-
слідовностей. Пакет орієнтований головним чином на задачі теоретичної молекуляр-
ної біології і поєднує зручний для користування інтерфейс з розвинутими сучасними
алгоритмами (в тому числі оригінальні). Він написаний на мові Ci і пригодниіі для
роботи на комп'ютерах типу IBM PC.
S u m m a r y
The package of programs GenBee intended to analyze nucleotide and amino acid se-
quences is described. This package combines high-level algorithms (including original
ones) suitable for advanced theoretical studies with flexibility and user-friendly service
typical of commercially available packages. The package is designed for IBM-compatible
personal computers. Accordingly it will be useful both for researches and students with
practically no background in computer methods, and for theoreticians.
СПИСОК ЛИТЕРАТУРЫ
1. Кунин Ε. В., Чумаков К. M., Горбаленя А. Е. Метод поиска структурных мотивов
в аминокислотных последовательностях. Программа Site пакета GenBee // Биопо-
лимеры и клетка.— 1990.—6, № 6.—С. 42—48.
2. Trifonou Е. N. Translation f raming code and frame-monitoring mechanism as sugges-
ted by the analysis of mRNA and 16S-rRNA nucleotide s e q u e n c e s / / J . Мої. Biol.—
1987.— 194, N 2.— P. 643—652. '
3. Леонтович A. M., Бродский Л. И., Горбаленя Α. Ε. Построение полной карты ло-
кального сходства двух полимеров. Программа DotHelix пакета GenBee / / Био-
полимеры и клетка.— 1990.— 6, № 6.— С. 14—21.
4. Бродский Л. И., Драчев A. JI., Леонтович А. М. Новый метод множественного вы-
равнивания последовательностей биополимеров. Программа H-Align пакета
GenBee / / Т а м же.— 1991.—7, № 1.—С. 14—22.
5. Lipman D. J., Pearson W. R. Rapid and sensitive protein similarity searches // Scien-
ce.— 1985.—227, N 1.—P. 1435—1441.
6. Hartigan J. A. Clastering algorithms.— New York: John Wiley and Sons, 1975.—
256 p.
7. Чумаков К. M., Юшманов С. В. Принцип максимального топологического подо-
бия в молекулярной систематике // Молекуляр. генетика, микробиология, вирусо-
логия.— 1988.— 3, No 1.— С. 3—9.
8. Эволюция РНК-зависимых РНК-полимераз позитивных рибовирусов : сравнение
филогенетических деревьев, построенных различными способами / Е. В. Кунин,
К. М. Чумаков, С. В. Юшманов, А. Е. Горбаленя / / Т а м же — С. 16—19.
9. Gibrat J.-F., Gamier J., Robson В. Further developments of protein secondary struc-
ture prediction using information theory / / J . Мої. Biol.— 1987.—198, N 4.—
p . 425—443.
10. Гультяев А. П., Монаков Ю. Η. Метод построения вторичной структуры Р Н К на
основе принципов самоорганизации//Биополимеры и клетка.— 1991.— 7, № 1.—
С. 31—36.
Науч.-произв. кооператив «Комби», Москва Получено 28.06.90
Межфакульте'т. н.-и. лаб. им. А. Н. Белозерского, МГУ
УДК 577.112
Л. И. Бродский, A. Л. Драчев, А. М. Леонтович
НОВЫЙ МЕТОД МНОЖЕСТВЕННОГО ВЫРАВНИВАНИЯ
ПОСЛЕДОВАТЕЛЬНОСТЕЙ БИОПОЛИМЕРОВ
(ПРОГРАММА H-Align ПАКЕТА GenBee )
В работе предложен новый алгоритм множественного выравнивания биологических
последовательностей. В этом алгоритме вначале на основе метода DotHelix строятся
консенсусные участки в данном наборе последовательностей разной толщины и раз-
© Л. И. БРОДСКИЙ, А. Л. ДРАЧЕВ, А. М. ЛЕОНТОВИЧ, 1991
14 ISSN 0232-7657. БИОПОЛИМЕРЫ И КЛЕТКА. 1991. Т. 7. .Nb 1:
ной степени сходства, а затем из этих консенсусов составляются цепочки, согласо-
ванные с порядком букв в последовательностях, и такие цепочки являются каркаса-
ми выравниваний. На основе алгоритма на языке Си написана программа H-Align из-
пакета GenBee. Рассмотрен модельный пример, иллюстрирующий эффективность
предложенного алгоритма.
Введение. Как известно, процедура выравнивания широко используется
при анализе первичных структур биополимеров. Такая процедура при-
меняется, например, при поиске функционально важных участков белков
или молекул Д Н К / Р Н К , при построении филогенетических дере-
вьев и т. д.
Алгоритмы выравнивания, в частности множественного, можно раз-
бить на две основные группы: одноэтапные, оптимизирующие сразу все
выравнивание, и двухэтапные. В двухэтапной процедуре на первом шаге
находится достаточно большое количество наборов сходных между со-
бой фрагментов из разных последовательностей, а на втором — из этих
наборов составляются непротиворечивые цепочки, лучшие из которых
и являются альтернативными выравниваниями.
Алгоритмы первой группы, как правило, базируются на процедурах:
динамического программирования (типа Нидельмана-—Вунша [1, 2] )
и требуют назначения величины штрафа за введение пробелов в вырав-
ненные последовательности (соответствующих делециям или вставкам
остатков). Результат выравнивания существенно зависит от величины
штрафа, но в то же время нет никаких сколько-нибудь серьезных осно-
ваний для выбора этой величины. Другой недостаток одноэтапных алго-
ритмов— это то, что обычно в них множественное выравнивание дела-
ется последовательно: сначала выравниваются две самые близкие по-
следовательности, затем эта пара как целое выравнивается с третьей,
затем тройка как целое выравнивается с четвертой и т. д. Если па одном
из шагов выравнивание в каком-то месте было сделано неудачно, то в
дальнейшем в этом месте оно будет все более искажаться.
Основной недостаток существующих методов второго типа — это
грубость процедуры поиска «консенсусов» наборов сходных между со-
бой фрагментов последовательностей. Некоторые из реально существу-
ющих консенсусов могут быть пропущены, и вместе с тем границы най-
денных консенсусов определяются недостаточно точно.
В представляемом ниже алгоритме, относящемся ко второй группе
методов, консенсусные участки, по нашему мнению, ищутся более полно-
и точно, чем обычно. Наш метод исходит из построения попарных карт
локального сходства и основан на алгоритме DotHelix [5].
Методы. Пусть имеется несколько последовательностей биополиме-
ров (например, белков). Результат их выравнивания представляет собой
набор последовательностей одинаковой длины. К а ж д а я последователь-
ность из набора получается за счет внесения пробелов в соответству-
ющую ей исходную последовательность; эти пробелы отвечают либо де-
лециям букв в этой последовательности, либо вставкам букв, произо-
шедшим в каких-то других последовательностях исходного набора. При
этом на некоторых участках набора выравненных последовательностей
между всеми или некоторыми его слоями существует сходство. Такие
участки будем называть «консенсусами». Степень сходства между сло-
ями консенсуса характеризуется его мощностью, которая вычисляется
как нормированная сумма весов за попарные замены остатков (букв),,
стоящих в одном столбце консенсуса:
где А — мощность рассматриваемого консенсуса; L — длина консенсу-
са, т. е. общая длина входящих в него фрагментов; k — толщина консен-
суса, Т. е. ЧИСЛО ВХОДЯЩИХ B него слоев; &1,г, &2,г, ..· , bL,r — буквы (остат-
ки), составляющие г-й слой консенсуса; рь,с — вес за замену буквы Ь на
(1)
2 ISSN 0232-7657. Б И О П О Л И М Е Р Ы И КЛЕТКА. 1991. Т. 7. .Nb 1:
рь — частота буквы b во всем наборе последовательностей.
Д л я случая консенсуса толщины два обоснование этого определе-
ния приведено в [5]. Следует сказать, что формула (1) несколько огруб-
лена по сравнению с аналогичной формулой в [5] : в формуле (1) час-
тоты вхождения букв рь предполагаются одинаковыми для всех вырав-
ниваемых последовательностей. Это сделано для ускорения времени
счета; такое огрубление слабо влияет на точность оценок мощности
консенсусов.
Заметим, что для поиска функционально важных участков знание
консенсусов, по-видимому, д а ж е более важно для биолога, чем само вы-
равнивание. Поэтому процедура поиска консенсусов имеет самостоятель-
ную ценность. В сущности, таким образом мы получаем многомерный
аналог карты локальных сходств.
Из вышеизложенного вытекает, что при поиске правильного вырав-
нивания естественно сначала находить все консенсусные участки без
пробелов, а затем цепочку из таких участков достроить до полного вы-
равнивания последовательностей, вставляя необходимое число пробе-
лов в зонах между этими участками. При этом из биологических сообра-
жений ясно, что в правильном выравнивании родственных последова-
тельностей, с одной стороны, консенсусы должны быть по возможности
более мощными и, с другой — пробелов должно быть немного.
В соответствии с этим в нашем алгоритме выделяются два этапа:
во-первых, построение всех консенсусов (заметим,.что в консенсус
необязательно входят все слои);
во-вторых, перебор всех правильных с точки зрения порядка букв в
последовательностях расположений таких консенсусов относительно
друг друга и выбор среди них наилучших по двум критериям: максими-
зации суммарной мощности входящих консенсусов и минимизации об-
щего числа пробелов.
Начнем с первого этапа. Д л я нахождения всех возможных в данном
наборе последовательностей консенсусов следовало бы просмотреть все
«регистры сравнения» (возможные сдвиги исходных последовательнос-
тей относительно друг друга) и для каждого из них искать совокуп-
ность непересекающихся достаточно мощных консенсусов, что можно
сделать, например, с помощью программы DotHelix [5]. Однако такая
процедура требует даже при сравнительно небольшом числе последова-
тельностей весьма большого времени счета, поскольку велико
число разных регистров сравнения — оно порядка п1~\ где η — средняя
длина последовательности. Чтобы избежать полного перебора всех ре-
гистров сравнения, предлагается использовать последовательную про-
цедуру нахождения наиболее мощных консенсусов. Эта процедура ос-
нована на том обстоятельстве, что в мощном консенсусе к а ж д а я или
почти к а ж д а я пара слоев значимо похожи.
Соответствующий алгоритм заключается в следующем. Д л я каждой
пары последовательностей из набора методом DolHelix находим все'
сходные фрагменты этих последовательностей на сравнительно низком
уровне значимости. Тем самым будут найдены все достаточно мощные
16 ISSN 0233-7657. Б И О П О Л И М Е Р Ы II КЛI-TKA- 1991. Г. 7. .Ns !
среднее значение веса за замену букв (суммирование в (2) производит-
ся по всевозможным буквам алфавита; для белков их 20);
букву с (для белков эти веса обычно берутся из матрицы Дэйхофф [6])
(2)
консенсусы толщины два. Д а л е е происходит постепенное утолщение кон-
сенсусов: консенсусы толщины три получаются из консенсусов толщины
два, консенсусы толщины четыре получаются из консенсусов толщины
три и т. д. за счет поочередного подцепления к каждому из них подхо-
дящих фрагментов очередной последовательности. Таким образом, каж-
дый консенсус как жесткое целое сдвигается вдоль всех незадействован-
ных в этом консенсусе последовательностей и присоединяет к себе в ка-
честве дополнительного слоя подходящие фрагменты.
Опишем более подробно процедуру присоединения нового слоя. Ее
проводили методом DotHelix [5], но по несколько другим правилам вы-
числения мощности (которую мы будем называть «мощностью подцеп-
ления») . Консенсус, продолженный в обе стороны на несколько позиций,
сдвигается относительно сравниваемой последовательности, и для каж-
дого сдвига формируется диагональ карты локального сходства консен-
суса и этой последовательности (для сравнения см. [5] ) ; числа аг/·, за-
полняющие карту локального сходства, являются суммами весов за за-
мены букв из 1-го столбца консенсуса на букву из /-й позиции сравнива-
емой последовательности:
ISSN 0233-7G57. БИОПОЛИ.МЕРЫ И КЛЕТКА. 1991. Т. 7. Λ» 1 2 — 0-693 17
где k — число слоев консенсуса, 67> — буква, стоящая в r-ы слое 1-м
столбце консенсуса, Cj — буква, стоящая в /-й позиции сравниваемой с
консенсусом последовательности, ρь,с — вес за замену буквы b на букву
с. Как было указано выше, формула для мощности подцепления несколь-
ко отличается от приведенной выше формулы (1) для мощности консен-
суса. Это связано с тем, что слои консенсуса нельзя рассматривать как
независимые берпуллиевские последовательности (например, вполне ре-
альная ситуация, когда все слои консенсуса в точности совпадают меж-
ду собой). Поэтому консенсус следует рассматривать не как набор слу-
чайных, а как набор фиксированных последовательностей, состоящих из
букв bi j . В то же время вполне естественно представлять сравниваемую
последовательность бернуллиевской и независимой от слоев консенсу-
са. В результате вместо формулы (1) мощность подцепления следовало
бы вычислять так:
где L — длина отрезка диагонали, мощность которого мы вычисляем;
Pc — частота буквы с.
К сожалению, вычислять по этой громоздкой формуле приходится
очень часто, а это самым пагубным образом сказывается на скорости
счета. Поэтому в программе используется оценка мощности подцепления
по приближенной формуле. Эта оценка исходит из следующих предполо-
жений (которые, безусловно, являются лишь приблизительными): во-
первых, что частоты букв в консенсусе такие же, как во всех последо-
вательностях в совокупности; во-вторых, зависимость между слоями
консенсуса выражается только в увеличении количества совпадений
муле (2), 5 — нормированная сумма весов для консенсуса, получаемая
из значения его мощности (см. формулу (1) ) .
При процедуре присоединения нового слоя мы отбираем только те
новые консенсусы, мощность подцепления для которых выше некоторо-
го порога.
В результате всей этой работы мы получим некоторую совокупность
консенсусов разной толщины; каждому консенсусу соответствует его
мощность, рассчитанная уже по формуле (1). Неполная толщина кон-
сенсуса в окончательном наборе означает, что входящие в него последо-
вательности заведомо имеют хорошее соответствие между собой в этом
месте; что же касается пропущенных в этом консенсусе последователь-
ностей, то хорошего соответствия со слоями консенсуса там нет.
Промежуточное хранение консенсусов (для экономии памяти и вре-
мени счета) осуществляется по принципу «стека» так, что сохраняется
определенное число наилучших по мощности. При построении очередно-
го консенсуса набор переупорядочивается и худший выталкивается
из стека.
Говоря метафорически, в предложенном нами способе поиска кон-
сенсусов из рассмотрения всевозможных пар последовательностей наме-
чаются потенциальные зоны сходства, а потом некоторые из них все бо-
лее проявляются за счет сходств этого участка с фрагментами из дру-
гих последовательностей, а другие стираются ввиду отсутствия дополни-
тельных сходств.
При вышеописанном способе получения консенсусов довольно боль-
шое количество их будет шумом, мешающим последующему построению
выравнивания из этих консенсусов (увеличивается перебор). Это обсто-
ятельство в основном связано с нашей нулевой гипотезой о независимо-
сти выравниваемого набора последовательностей, хотя само желание их
выравнить предполагает обратное. Очевидно, что для зависимых (в сто-
рону возможности выравнивания) последовательностей среднее значе-
ние M (р) весов за замену букв увеличивается по сравнению с формулой
(2). В нашей программе имеется возможность учесть это обстоятельство,
увеличивая величину т . Эксперименты показывают, что такая процеду-
ра отфильтровывает значительное количество шумовых консенсусов.
Однако вопрос об оптимальном наборе величины т нуждается в даль-
нейшем изучении.
18 ISSN 0233-7657. Б И О П О Л И М Е Р Ы И КЛЕТКА. 1991. Т. 7. № 1
Здесь пеq характеризует степень согласованности в столбцах консенсуса
(по сравнению с той, которая была бы для случая берпуллиевских и не-
зависимых между собой слоев), переведенную в ожидаемое число сов-
падений букв в столбце (точнее говоря, увеличение этого числа сов-
падений по сравнению со случаем независимых слоев).
Мы вычисляем эту величину /Zeq исходя из мощности консенсуса,
предполагая, что такое значение мощности и соответствующее значение
нормированной суммы весов (стоящей в числителе формулы (1)) про-
исходит только за счет точных совпадений букв (конечно, и это пред-
положение является лишь приближенным); из этого предположения
легко следует, что
букв в его столбцах. Первое предположение приводит к тому, что Mri
тождественно равно га, в силу же второго предположения имеет место
формула
где среднее значение весов ρ ь, т вычисляется по фор
Перейдем теперь к описанию второго этапа —- построению наилуч-
ших выравниваний из консенсусов.
После выделения полного набора достаточно мощных консенсусов
нужно искать все возможные комбинации их состыковки, причем для
составления полного выравнивания, кроме пробелов, придется исполь-
зовать и «пеконсенсуспые» участки. Поскольку трудно ожидать, что в
биологических последовательностях существует значимое «отрицатель-
ное» сходство с отрицательной мощностью, т. е. маловероятное с пози-
ций случайности несходство, можно думать, что порядок расположения
букв и пробелов в некопсенсусном участке не очень существен. В пашем
алгоритме в неконсепсусных участках по каждому слою сначала идут
буквы, а затем добавляется необходимое число пробелов.
В случае наложения двух консенсусов из разных регистров (т. е. в
случае, когда эти консенсусы содержат хотя бы один общий фрагмент
какой-либо последовательности, входящей в оба эти консенсуса) с помо-
щью вставки необходимого числа пробелов можно перейти от одного
консенсуса к другому. Этот переход осуществляется у нас в том
месте, которое обеспечивает наибольшее значение суммарной
мощности.
Как было уже сказано, выбор выравнивания состоит в построении
согласованной по порядку букв в последовательностях цепочки консен-
сусов. При этом для уменьшения перебора таких цепочек все найденные
консенсусы разделяются на несколько групп по мощности (всего воз-
можно не более десяти групп). После этого вначале составляются все
возможные цепочки из сравнительно небольшой группы самых мощных
консенсусов, затем в эти цепочки всеми возможными способами вставля-
ются консенсусы из следующей группы по мощности и т. д. до исчерпа-
ния всех групп.
В итоге мы получим набор выравниваний с максимально возмож-
ным включением в каждый из построенных на первом этапе консенсу-
сов (максимальность понимается в том смысле, что цепочки насыще-
ны — больше добавить туда консенсусов нельзя) . Мерой качества вырав-
нивания служит нормированная сумма попарных весов за замены букв
из всех столбцов консенсусов соответствующей цепочки (сравни с фор-
мулой (1) ; в качестве длины L берется общая длина выравненных после-
довательностей). Видно, что при таком определении хорошее качество
имеют такие выравнивания, в которые по возможности входят мощные
консенсусы при небольшом числе вставленных пробелов.
После получения выравнивания пользователь имеет возможность
вручную поправить его, выкинув из исходного набора тот консенсус,
включение которого в цепочку заставляет сильно увеличить число встав-
ленных пробелов и затем с новым набором консенсусов вновь проделать
процедуру составления цепочек.
Окончательный выбор наилучшего выравнивания можно осущест-
вить разными способами. Например, такое наилучшее из набора най-
денных с разным числом пробелов может выбирать пользователь. Мож-
но также использовать то обстоятельство, что для того значения числа
пробелов, при котором имеет место «истинное» выравнивание (восста-
навливающее предковую последовательность, если таковая существует),
должно резко подскочить нормированное значение суммарной мощности
консенсусов.
Данный алгоритм реализован на языке Си для компьютеров типа
IBM PC в виде программы H-Align из пакета программ для анализа по-
следовательностей биополимеров GenBee, разработанного в Н П К
«Комби».
Результаты и обсуждение. В качестве проверки работоспособности
алгоритма мы исследовали следующий модельный пример. Были взяты
четыре последовательности цитохромов С из разных животных — шим-
панзе, собаки, индейки и утки (последовательности — «прародители»).
Они очень похожи и состоят из 104 аминокислотных остатков. Далее их
ISSN 0233-7657. Б И О П О Л И М Е Р Ы И КЛЕТКА. 1991. 'Г. 7. № 1 2 * 19
«мутировали»: около 45 % букв было заменено дефисами — символами
«—». На следующем шаге все дефисы были убраны. В результате полу-
чились более короткие последовательности с длинами 43, 53, 66 и 75 букв.
Эти последовательности и взяты как исходные для выравнивания . Схе-
ма модели приведена на рис. 1.
Результаты работы по программе H-Al ign представлены на рис. 2,
где изображены два набора выравненных последовательностей, полу-
ченные с использованием разных матриц весов за замены остатков: мат-
рицы Д э й х о ф ф [6] и единичной матрицы (в ней вес за совпадение букв
Последовательности -"прародители"
"Мутированные" последовательности
Рис. 1. Конструирование исходных для выравнивания последовательностей
Fig. 1. Constructing of the source sequences for an alignment
равен единице, а за несовпадение — нулю) . В обоих изображенных на-
борах выравненных последовательностей большими буквами показаны
места, входящие в консенсусы, а маленькими — в межконсенсусные
участки.
Н а рис. 2, кроме результатов выравнивания по программе H-Al ign,
приведено т а к ж е «истинное» выравнивание. Оно получается из образо-
ванных нами последовательностей с дефисами (второй набор последова-
т е л ь н о с т е й — н а рис. 1) выбрасыванием столбцов, состоящих из одних
дефисов.
Сравнение трех выравниваний показызает , что все они достаточно
хорошо соответствуют друг другу, однако выравнивание с использова-
нием единичной матрицы более похоже на «истинное». Это обстоятель-
ство объясняется способом построения исходных последовательностей, в
результате чего практически все соответствующие друг другу буквы
«истинного» выравнивания совпадают между собой. Поэтому единичная
матрица весов, стремящаяся выделить консенсусы с совпадением букв,
больше подходит для выравнивания таких последовательностей, чем
матрица Дэйхофф.
Кроме того, отметим, что в межконсенсусных участках места рас-
положения дефисов указываются не вполне точно. Это объясняется тем,
20 !SSN 02:;.,-7,.,87. Бі:ОПОЛ!ПЕРЬІ II К Л H IV Λ. 1991. т. 7. .Vo 1
Исходные для выравнивания последовательности
Выравненные по матрице Дэйхофф последовательности
Выравненные по единичной матрице последовательности
1 : k g — K K I F GKHKTGPNLH KNKGIIWGDTLYLENpky
1 : gdvkgKKIFVQK TVEk NLHGlfGRKTpgfsy-KNKGITWGe
1 : gdkg VQKCSQTVEkGKHKTGPNLH GRKTGegfs-KNKGITWGDTLYLEN
1 : KKIFVQKCSQTVE KGGPNLHG—GRKTGqaegtdanGITgeDTEYLEN
61 : IPGTKMIFra DLIAYLKka—
61 : LIA
61 : IPGTKMI— GIKKKServDLIAYLKdats
61: IPGTKMIFaGIKKKSatak
"Истинное" выравнивание
1 : KGKKIF GKHKTGPNLH KmGIIWG-DT
1 : GDVKGKKIFVQK TVEK NLHGLFGRKT PGFSY KNKGITWGE—
1 : GD-KG VQKCSQTVEK-GKHKTGPNLH GRKTG—EGFS KNKGITWG-DT
! : KKIFVQKCSQTVEKG GPNLHG—GRKTGQAEG TDAN GIT-GEDT
Рис. 2. Результаты выравнивания по программе H-Align исходных последовательностей
с использованием разных весовых матриц (Дэйхофф и единичной), а также «истинное»
выравнивание
Fig. 2. H-Align program output al ignmet of the source sequences with two different
weight matr ices (Dayhoff and identi ty) . The «true» al ignment is represented also
что наш алгоритм действует по правилу сдвига всех таких мест в конец
соответствующего участка. Однако на таких участках искать какое-либо
соответствие невозможно (по крайней мере, без использования биологи-
ческих соображений), поскольку наблюдаемое на них сходство между
буквами находится на уровне случайного.
Р е з ю м е
У роботі запропоновано новий алгоритм множинного вирівнювання біологічних по-
слідовностей. В ньому спочатку на основі методу DotHelix будуються консенсусні ді-
лянки в даному наборі послідовностей різної товщини і ступеня схожості, а потім із
цих консенсусів складаються ланцюжки, погоджені з порядком букв в послідовно-
стях, і такі ланцюжки є каркасами вирівнювання. На основі алгоритму на мові Ci напи-
сана програма H-Align з пакету GenBee. Розглянутий модельний приклад ілюструє
ефективність запропонованого алгоритму.
S u m m a r y
Generalizat ion of the multiple a l ignment is central to the entire field of biological
sequence analysis. The algori thm of al ignment by p rogram Η-al ign incorporated in
GenBee package is a result of development of the local similarity search principle. It
has two s tages:
ISSN 0233-7G57. Б И О П О Л И М Е Р Ы И КЛЕТКА. I99l. Т. 7. № 1 2 ί
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 С. D. A general method applicable to the search for simi-
larities in the amino acid sequence of two p r o t e i n s / / ! . Мої. Biol.— 1970.— 48, N 2.—
P. 443—453.
2. Gotoh 0. Alignment of three biological sequences with an efficient traseback proce-
d u r e / / J . Theor. Biol.— 1986.— 121, N 1.— P. 327—337.
3. Sobel E., Marttinez H. Af. A multiple sequence alignment program / / NucL Acids
Res.— 1986.— 14, N 2.— P. 363—374.
4. Bacon D. J., Anderson W. J. Multiple sequence a l i g n m e n t / / J . Мої. Biol.— 1986.—
191, N 1.—P. 153—161.
5. Леонтович A. M., Бродский Л. И., Горбаленя Α. Ε. Построение полной карты ло-
кального сходства двух полимеров (программа DotHelix пакета GenBee / / Биопо-
лимеры и клетка.— 1990.—6, № 6.—С. 14—21.
6. Dayhoff М. О., Barker Ψ. С., Hunt L. Т. Establishing homologies in protein sequen-
ces / / M e t h . Enzymol.— 1983.—91.—P. 524—545.
Науч.-произв. кооператив «Комби», Москва Получено 28.06.90
Межфакультет, н.-и. лаб. им. А. Н. Белозерского, МГУ
УДК 576.315.42
В. А. Шепелев
АЛГОРИТМ УСКОРЕННОГО ПОСТРОЕНИЯ
ТОЧЕЧНЫХ МАТРИЦ ГОМОЛОГИИ
Метод анализа гомологичных участков с помощью точечных матриц гомологии за-
ключается в нахождении и отображении на прямоугольной матрице общих для двух
последовательностей слов, в которых совпадает определенное количество букв. Пред-
ложен алгоритм ускоренного построения таких матриц с различными параметрами
фильтрации.
Введение. Метод исследования гомологичных участков с использовани-
ем точечных матриц гомологии [1] состоит в том, чтобы на прямоуголь-
ной матрице найти общие для двух последовательностей слова, то есть
подпоследовательности длиной W9 в которых совпадает не менее M букв.
П а р а м е т р ы W n M называются параметрами фильтрации, а величина
W — размером окна. Такое построение обладает большой наглядно-
стью, так как гомологичные участки выявляются в виде диагональных
линий. При W = M= 1 матрица для двух случайных последовательно-
стей оказывается забитой случайными (с вероятностью около 1/4) точ-
ками, отмечающими совпадение отдельных букв. Вообще число точек
на матрице для двух случайных последовательностей можно оценить по
формуле
Z = P -L 1 -L 2 ,
где
PV^ /^k Jk / і
= 2jCwp (1 — ρ) .
/г=M
φ Β. Α. ШЕПЕЛЕВ, 1991
22 ISSN 0232-7657. Б И О П О Л И М Е Р Ы И КЛЕТКА. 1991. Т. 7. .Nb 1:
|