Генетические алгоритмы в биоинформатике

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2019
Hauptverfasser:	Гупал, А.М., Гупал, Н.А.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2019
Schriftenreihe:	Компьютерная математика
Schlagworte:	Математические модели в биологии и медицине
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/161939
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Генетические алгоритмы в биоинформатике / А.М. Гупал, Н.А. Гупал // Компьютерная математика. — 2019. — № 1. — С. 100-108. — Бібліогр.: 3 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-161939
record_format	dspace
spelling	irk-123456789-1619392019-12-28T01:26:25Z Генетические алгоритмы в биоинформатике Гупал, А.М. Гупал, Н.А. Математические модели в биологии и медицине В генетических алгоритмах в качестве начальной популяции использованы таблицы полярности на основе трех типов информации, и таким образом построены оптимальные варианты несимметричных кодов, а также кодов, имеющих примерно такие же характеристики, как у стандартного кода. Проведено порівняння стандартного генетичного коду з генетичними кодами, що випадково згенерували, а також з оптимальними кодами, отриманими за допомогою генетичного алгоритму. У генетичних алгоритмах як «організми» популяції використовувалися таблиці полярності на основі трьох типів інформації, і таким чином вдалося побудувати оптимальні варіанти несиметричних кодів, а також коди, що мають приблизно такі ж характеристики як у стандартного коду. The standard genetic code is compared with randomly generated genetic codes and with the optimal codes obtained by genetic algorithm. In genetic algorithms, polarity tables are used as the "organisms" of a population based on three types of information, and, thus, the optimal variants of asymmetric codes are constructed, as well as the codes with approximately the same characteristics as a standard code. 2019 Article Генетические алгоритмы в биоинформатике / А.М. Гупал, Н.А. Гупал // Компьютерная математика. — 2019. — № 1. — С. 100-108. — Бібліогр.: 3 назв. — рос. 2616-938Х http://dspace.nbuv.gov.ua/handle/123456789/161939 519.217.268 ru Компьютерная математика Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Математические модели в биологии и медицине Математические модели в биологии и медицине
spellingShingle	Математические модели в биологии и медицине Математические модели в биологии и медицине Гупал, А.М. Гупал, Н.А. Генетические алгоритмы в биоинформатике Компьютерная математика
description	В генетических алгоритмах в качестве начальной популяции использованы таблицы полярности на основе трех типов информации, и таким образом построены оптимальные варианты несимметричных кодов, а также кодов, имеющих примерно такие же характеристики, как у стандартного кода.
format	Article
author	Гупал, А.М. Гупал, Н.А.
author_facet	Гупал, А.М. Гупал, Н.А.
author_sort	Гупал, А.М.
title	Генетические алгоритмы в биоинформатике
title_short	Генетические алгоритмы в биоинформатике
title_full	Генетические алгоритмы в биоинформатике
title_fullStr	Генетические алгоритмы в биоинформатике
title_full_unstemmed	Генетические алгоритмы в биоинформатике
title_sort	генетические алгоритмы в биоинформатике
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2019
topic_facet	Математические модели в биологии и медицине
url	http://dspace.nbuv.gov.ua/handle/123456789/161939
citation_txt	Генетические алгоритмы в биоинформатике / А.М. Гупал, Н.А. Гупал // Компьютерная математика. — 2019. — № 1. — С. 100-108. — Бібліогр.: 3 назв. — рос.
series	Компьютерная математика
work_keys_str_mv	AT gupalam genetičeskiealgoritmyvbioinformatike AT gupalna genetičeskiealgoritmyvbioinformatike
first_indexed	2025-07-14T14:31:41Z
last_indexed	2025-07-14T14:31:41Z
_version_	1837633111709450240
fulltext	100 ISSN 2616-938X. Компьютерная математика. 2019, № 1 Математические модели в биологии и медицине В генетических алгоритмах в ка- честве начальной популяции ис- пользованы таблицы полярности на основе трех типов информа- ции, и таким образом построены оптимальные варианты несим- метричных кодов, а также кодов, имеющих примерно такие же характеристики, как у стан- дартного кода. © А.М. Гупал, Н.А. Гупал, 2019 УДК 519.217.268 А.М. ГУПАЛ, Н.А. ГУПАЛ ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ В БИОИНФОРМАТИКЕ Введение. В конце 1960-х годов американ- ский исследователь Д. Холланд в качестве принципов комбинаторного перебора вари- антов решения оптимизационных задач предложил использовать методы и модели механизма развития органического мира на Земле. Генетический алгоритм представляет собой адаптивный поисковый метод, осно- ванный на селекции лучших элементов в по- пуляции, подобно эволюционной теории Ч. Дарвина. Основой для возникновения ге- нетических алгоритмов послужили модель биологической эволюции и методы случай- ного поиска. Л. Растригин отмечал, что слу- чайный поиск возник как реализация про- стейшей модели эволюции, когда случайные мутации моделировались случайными шага- ми оптимального решения, а отбор – устра- нением неудачных вариантов [1]. Так же как процесс эволюции начинается с начальной популяции, так и алгоритм начинает свою работу с созданием начального множества конкурирующих между собой решений оп- тимизационной задачи. Затем эти родитель- ские решения создают потомков путем слу- чайных и направленных изменений. После этого оценивается эффективность решений и они подвергаются селекции. Аналогично естественным системам здесь действует принцип выживания «сильнейших», наиме- нее приспособленные решения исчезают, а затем процесс повторяется. Традиционные оптимизационные алгорит- мы для нахождения лучших решений ис- пользуют большое количество допущений при оценке целевой функции. Эволюционный подход не требует таких допущений, и это ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ В БИОИНФОРМАТИКЕ ISSN 2616-938X. Компьютерная математика. 2019, № 1 101 расширяет класс задач, которые можно решать с помощью генетических алго- ритмов. Можно сказать, что генетические алгоритмы позволяют решать те про- блемы, решение которых традиционными алгоритмами затруднительно. При эволюционном подходе популяцию можно анализировать, дополнять и видоизменять применительно к изменяющимся условиям, для этого не требу- ется полный перебор. Другое преимущество генерируемых алгоритмов для решения задач состоит в способности быстрой генерации достаточно хороших решений. Помехоустойчивость стандартного генетического кода. В работе [2] ис- следована помехоусточивость стандартного генетического кода относительно полярности аминокислот при точечных мутациях нуклеотидов в кодоне. Если в результате мутации полярный остаток в белке сменится на неполярный (или наоборот), то форма молекулы может измениться настолько, что белок не смо- жет выполнять свою функцию. В табл. 1 неполярные аминокислоты выделены жирным шрифтом. Каждый триплет допускает 9 однократных замен, число ко- дирующих аминокислоты триплетов равно 61. Для стандартного кода возможны 526 замещений, в которых кодон до и после мутации не является одним из трех стоп-кодонов, из них 364 замещения не меняют полярность, т. е. его помехо- устойчивость составляет 364/526 = 69,20 %. ТАБЛИЦА 1. Стандартный генетический код организмов Второе основаниеПервое основа- ние T C A G Третье осно- вание фенилаланин серин тирозин цистеин T фенилаланин серин тирозин цистеин C лейцин серин стоп стоп AT лейцин серин стоп триптофан (W), н G лейцин пролин гистидин агринин T лейцин пролин гистидин агринин C лейцин пролин глутамин агринин AC лейцин пролин глутамин агринин G изолейцин треонин аспарагин серин T изолейцин треонин аспарагин серин C изолейцин треонин лизин агринин AA метионин треонин лизин агринин G валин аланин асп. к-та глицин T валин аланин асп. к-та глицин C валин аланин глут. к-та глицин AG валин аланин глут. к-та глицин G А.М. ГУПАЛ, Н.А. ГУПАЛ ISSN 2616-938X. Компьютерная математика. 2019, № 1102 По аналогии со стандартным кодом произвольный генетический код можно рассматривать как функцию : ,f C A отображающую множество кодонов 3{ , , , }C a c g t на множество ,A включающее 20 базовых аминокислот и сигнал прекращения синтеза белка stop . Пусть 9:m C C – функция, сопоставляющая произвольному кодону список из девяти кодонов, порождаемых возможными точечными мутациями нуклеотидов из кодона. Помехоустойчивость кода в этих обозначениях можно выразить функционалом * * * ( ) 1( ) 1 ( , ) ( ( ), ( )). u C v m um Q f w u v f u f v Q       (1) Здесь f f h  : ,h A S где S  множество возможных характеристик с определенной на нем функцией расстояния 2: [0, ),S   ( , ) 0w u v   вес мутации, переводящей кодон u в ,v mQ  нормировочный множитель, подоб- ранный таким образом, что 0 ( ) 1.Q f  В качестве характеристики h рассмотрены следующие три функции, свя- занные с формированием аминокислотами пространственной структуры белков: полярность ,P принимающая значение 0 для неполярных аминокислот и 1 – для полярных, от которой зависит взаимодействие аминокислоты с другими амино- кислотами; гидрофобность ,Hy определяющая характер поведения аминокисло- ты в водной среде; склонность к образованию  -спиралей (одного из основных элементов пространственной структуры белка) He [2]. Вычислительный эксперимент оценивал помехоустойчивость стандартного генетического кода по сравнению со случайными генетическими кодами, при- надлежащими к одному из трех классов: коды ,f являющиеся «переста- новками» стандартного кода, для которых выполняется условие x S  1 1\| ( ) \| \| ( ) ( ) \|;f x St h x   произвольные генетические коды, отображающие кодо- ны на все множество характеристик x S  * 1\| ( ) \| 0;f x  подмножество преды- дущего класса – коды, имеющие приблизительно одинаковое со стандартным кодом распределение характеристик x S  * 1 1 1 \| ( ) \| \| ( ) ( ) \| , \| ( ) ( ) \| f x St h x St h x         где порог  полагался равным 1/ 3 (таким образом, например, количество стоп- кодонов в кодах этого класса колебалось от 2 до 4, количество кодонов поляр- ных и неполярных аминокислот находилось в диапазоне 27 , 34п н  ). В последнем случае коды генерировались в соответствии с частотами харак- теристик в стандартном коде ,u C x S   * 11{ ( ) } \| ( ) ( ) \| 64 P f u x St h x   . ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ В БИОИНФОРМАТИКЕ ISSN 2616-938X. Компьютерная математика. 2019, № 1 103 Значения функционала (1) для стандартного кода, а также усредненные зна- чения и среднеквадратичные отклонения для 510 кодов из вышеописанных трех классов приведены в табл. 2. ТАБЛИЦА 2. Сравнение стандартного кода со случайными кодами Характеристика, % Тип кода Помехоустойчивость стандартный 69,20 перестановки 49,19 ± 2,91Полярность P близкие 50,21 ± 3,10 стандартный 77,44 перестановки 61,52 ± 1,48Гидрофобность Hy близкие 61,77 ± 2,07 стандартный 85,86 перестановки 81,59 ± 0,69 Склонность к образованию спиралей He близкие 81,65 ± 1,97 Оптимальные генетические коды. В генетических алгоритмах в качестве «организмов» популяции использовались не сами генетические коды, т. е. таб- лицы, которые ставят каждому кодону в соответствие одну из 20 аминокислот или стоп-сигнал, а таблицы полярности, которые ставят в соответствие каждому кодону один из трех типов информации: полярную аминокислоту, неполярную аминокислоту или стоп-кодон. С помощью таблиц полярности можно избавиться от избыточной информа- ции. Количество вариантов генетических кодов оценивается примерно величи- ной 6421 (это число превосходит 8010 ), а таблиц полярности – всего 643 . Поэтому с помощью генетических алгоритмов удалось достаточно экономно и быстро построить оптимальные варианты помехоустойчивых генетических кодов, кото- рые отличаются от стандартного кода числом стоп-кодонов и количеством полярных и неполярных триплетов. Для оптимизации функционала качества (1) на множествах перестановок стандартного кода и близких к нему кодов исполь- зовался генетический алгоритм. Шаг 1. Задать начальное поколение, состоящее из 0N случайных переста- новок стандартного генетического кода. Шаг 2. Для каждого из T поколений ,tF 1, ,t = T выполнить шаги 3 – 6. Шаг 3. Добавить в текущее поколение tF результаты скрещивания каждого из кодов i tf F с определенным количеством cN других кодов из ,tF выбран- ных случайным образом. А.М. ГУПАЛ, Н.А. ГУПАЛ ISSN 2616-938X. Компьютерная математика. 2019, № 1104 Шаг 4. Добавить в поколение tF заданное количество mN мутаций каждого из кодов .i tf F Шаг 5. Удалить из поколения коды, не принадлежащие к рассматриваемому классу. Шаг 6. Перевести в следующее поколение не более L кодов, обладающих наибольшей помехоустойчивостью. Понятие мутации генетического кода ,i tf F определено следующим образом: 1 1 1 1 ( ), с вероятностью (1 ), , , ( ), с вероятностью ( , ( )), ( )( ) , , ( ), с вероятностью ( , ( )).n n n n f u p x x S x f u pR x f u m f u x x S x f u pR x f u           Где введено обозначение St – стандартный генетический код, 1 1 \| ( ) ( ) \|( , ) 1 \| ( ) ( ) \| St h xR x y St h y      . Таким образом, при мутации значение функции кода, соответствующее каждому из 64 кодонов, может с определенной вероятностью p измениться на другое возможное значение, причем распределение вероятностей перехода соот- ветствует распределению значений в стандартном генетическом коде. Использовались следующие параметры алгоритма: количество поколений 50000;T = размер начального поколения 0 50;N = максимальный размер поколения 250;L = число скрещиваний и мутаций для каждого кода 4cN = и 2mN = соответственно; вероятность мутации в отдельном кодоне 0,1.p = Для каждого набора из характеристики, функции расстояния и класса генетических кодов проводилось 20 запусков алгоритма; лучшие результаты приведены в табл. 3. Как видим, стандартный генетический код ни в одном из случаев не оптимален, однако возможный выигрыш в помехоустойчивости не слишком велик, в особенности для гидрофобности Hy и склонности к образованию  -спиралей. Один из полученных оптимальных симметричных генетических кодов по отношению к полярности приведен в табл. 4. Этот код можно получить из стан- дартного кода с помощью восьми парных перестановок. В симметричном коде кодон ( )ijk кодирует полярную аминокислоту, а антикодон ( )kji – неполярную, либо наоборот. С помощью генетических алгоритмов построены различные ва- рианты наиболее помехоустойчивых кодов, отличающиеся от стандартного кода числом стоп-кодонов и количеством триплетов, определяющих полярные и не- полярные аминокислоты. Например, построен симметричный код с помехо- устойчивостью 78,29 %, в котором четыре стоп-кодона расположены в клетке TA таблицы кода; в клетке TC содержатся аминокислоты цистеин, цистеин, триптофан, триптофан; а в клетке TG – аминокислоты тирозин, тирозин, серин, серин. ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ В БИОИНФОРМАТИКЕ ISSN 2616-938X. Компьютерная математика. 2019, № 1 105 ТАБЛИЦА 3. Помехоустойчивость оптимальных кодов Характеристика, % Тип кода Помехоустойчивость стандартный 69,20 перестановки 77,86Полярность P близкие 78,30 стандартный 77,44 перестановки 80,05Гидрофобность Hy близкие 81,66 стандартный 85,86 перестановки 89,26 Склонность к обра- зованию спиралей He близкие 91,30 ТАБЛИЦА 4. Оптимальный симметричный по полярности генетический код Второе основаниеПервое осно- вание T C A G Третье осно- вание фенилаланин стоп тирозин серин T фенилаланин триптофан тирозин серин C лейцин цистеин стоп серин A T лейцин цистеин стоп серин G лейцин пролин гистидин аргинин T лейцин пролин гистидин аргинин C лейцин пролин глутамин аргинин A C лейцин пролин глутамин аргинин G изолейцин глицин аспарагин серин T изолейцин глицин аспарагин серин C изолейцин глицин лизин аргинин A A метионин глицин лизин аргинин G валин аланин асп. к-та треонин T валин аланин асп. к-та треонин C валин аланин глут. к-та треонин AG валин аланин глут. к-та треонин G А.М. ГУПАЛ, Н.А. ГУПАЛ ISSN 2616-938X. Компьютерная математика. 2019, № 1106 Заметим, что оптимальных помехоустойчивых кодов существует несколько. Симметрия кода, понимаемая как переход от полярной аминокислоты к непо- лярной при переходе от кодона к антикодону, не является необходимым услови- ем оптимальности генетического кода. Если в коде, приведенном в табл. 4, поменять местами аминокислоты столбцов C и A, получим код (табл. 5), для которого симметрия не выполняется вообще: кодон и антикодон кодируют аминокислоту одного типа, поскольку неполярные аминокислоты содержатся в столбцах T и A, а полярные – в столб- цах C и G. Поэтому помехоустойчивость кода в табл. 4 такая же, как у симмет- ричного кода – 77,86 %. Если во всех кодонах кода в табл. 4 переставить местами второй и третий нуклеотиды, т. е. в каждой строке кодоны «повернуть на 90 градусов», получим код в табл. 6 с такой же помехоустойчивостью, что и симметричный код, в ко- тором симметрия выполняется примерно в половине случаев. В этом коде непо- лярные аминокислоты определяются триплетами с третьим нуклеотидом T и C, а у полярных аминокислот третий нуклеотид – A и G. ТАБЛИЦА 5. Оптимальный код, для которого симметрия не выполняется Второе основаниеПервое осно- вание T C A G Третье осно- вание фенилаланин тирозин стоп серин T фенилаланин тирозин триптофан серин C лейцин стоп цистеин серин A T лейцин стоп цистеин серин G лейцин гистидин пролин аргинин T лейцин гистидин пролин аргинин C лейцин глутамин пролин аргинин A C лейцин глутамин пролин аргинин G изолейцин аспарагин глицин серин T изолейцин аспарагин глицин серин C изолейцин лизин глицин аргинин A A метионин лизин глицин аргинин G валин асп. к-та аланин треонин T валин асп. к-та аланин треонин C валин глут. к-та аланин треонин AG валин глут. к-та аланин треонин G ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ В БИОИНФОРМАТИКЕ ISSN 2616-938X. Компьютерная математика. 2019, № 1 107 ТАБЛИЦА 6. Код, для которого симметрия выполняется в половине случаев Второе основаниеПервое осно- вание T C A G Третье осно- вание фенилаланин фенилаланин лейцин лейцин T стоп триптофан цистеин цистеин C тирозин тирозин стоп стоп A T серин серин серин серин (S) G лейцин лейцин лейцин лейцин T пролин пролин пролин пролин C гистидин гистидин глутамин глутамин A C аргинин аргинин аргинин аргинин G изолейцин изолейцин изолейцин метионин (M) T глицин глицин глицин глицин C аспарагин аспарагин лизин лизин A A серин серин аргинин аргинин G валин валин валин валин T аланин аланин аланин аланин C асп. к-та асп. к-та глут. к-та глут. к-та A G треонин треонин треонин треонин G Выводы. Описан математический аппарат для анализа помехоустойчивости генетического кода по отношению к определенному классу мутаций генов. Про- ведено сравнение стандартного генетического кода со случайно сгенерирован- ными генетическими кодами, а также с оптимальными кодами, полученными с помощью генетического алгоритма. Из результатов вычислительного экспери- мента следует, что стандартный код не максимизирует выбранных функциона- лов качества, хотя и весьма близок к оптимуму. Определенные особенности по- лученных оптимальных генетических кодов свидетельствуют о том, что помехо- устойчивость являлась одним из факторов, влияющих на эволюцию генетиче- ского кода. В генетических алгоритмах в качестве «организмов» популяции использо- вались не сами генетические коды, а таблицы полярности, которые ставят в со- ответствие каждому кодону один из трех типов информации: полярную амино- кислоту, неполярную аминокислоту или стоп-кодон. С помощью таблиц поляр- ности удалось избавиться от огромной избыточной информации, поскольку чис- ло вариантов генетических кодов превосходит астрономическую величину 8010 . Генетическими алгоритмами удалось построить оптимальные варианты не- симметричных кодов в табл. 5, 6, а также коды, имеющие примерно такие же характеристики, как у стандартного кода. Построить такие варианты генетиче- ских кодов на основе оптимизационных градиентных процедур невозможно. А.М. ГУПАЛ, Н.А. ГУПАЛ ISSN 2616-938X. Компьютерная математика. 2019, № 1108 А.М. Гупал, M.A. Гупал ГЕНЕТИЧНІ АЛГОРИТМИ В БІОІНФОРМАТИЦІ Проведено порівняння стандартного генетичного коду з генетичними кодами, що випадково згенерували, а також з оптимальними кодами, отриманими за допомогою генетичного алго- ритму. У генетичних алгоритмах як «організми» популяції використовувалися таблиці поляр- ності на основі трьох типів інформації, і таким чином вдалося побудувати оптимальні варі- анти несиметричних кодів, а також коди, що мають приблизно такі ж характеристики як у стандартного коду. A.M. Gupal, M.A. Gupal THE GENETIC ALGORITHMS IN BIOINFORMATICS The standard genetic code is compared with randomly generated genetic codes and with the optimal codes obtained by genetic algorithm. In genetic algorithms, polarity tables are used as the "organ- isms" of a population based on three types of information, and, thus, the optimal variants of asym- metric codes are constructed, as well as the codes with approximately the same characteristics as a standard code. Список литературы 1. Растригин Л.А. Статистические методы поиска. М: Наука, 1968. 376 с. 2. Сергиенко И.В., Гупал А.М., Островский А.В. Устойчивость генетического кода к точечным мутациям. Кибернетика и системный анализ. 2014. № 5. С. 17 – 24. 3. Гупал А.М., Сергиенко И.В. Симметрия в ДНК. Методы распознавания дискретных последовательностей. К.: Наукова думка, 2016. 228 с. Получено 29.05.2019 Об авторах: Гупал Анатолий Михайлович, доктор физико-математических наук, член-корреспондент НАН Украины, заведующий отделом Института кибернетики имени В.М. Глушкова НАН Украины, Гупал Никита Анатольевич, кандидат физико-математических наук, научный сотрудник Института кибернетики имени В.М. Глушкова НАН Украины.

Генетические алгоритмы в биоинформатике

Institution

Ähnliche Einträge