ОБ ИНФОРМАЦИОННОЙ емкости символьных ПОСЛЕДОВАТЕЛЬНОСТЕЙ

IHÔOPMATÈKA

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

ПЕРЕЧЕНЬ ССЫЛОК

1. Колмогоров А.^ Автоматы и жизнь. В сб. Кибернетика -неограниченные возможности и возможные ограничения. Итоги развития. M: Hаука, 1979 г. с. 10-29.

2. Колмогоров А.^ О представлении непрерывных функций нескольких переменных в виде суперпозиции непрерывных функций одного переменного и сложения. Доклады AH СО^ т. 114, вып.5, 1957г. с. 953-956

3. Hecht-Nielsen R. Kolmogorov's mapping neural networks existence theorem. In Proc. IEEE First Internat. Conference on Neural Networks. 1987. Vol.II, pp. 11-14. San Diego, CA: SOS Printing.

4. Cotter N.E., Guillerm T.J. The CMAC and a Theorem of Kol-mogorov. Neural Networks, 1992, v.3, pp.221-228

5. Радченко A.H. Аппроксимация и точное формирование булевых функций многих переменных. I. Объем памяти и точность аппроксимации. Изв. АН СССР. Техническая кибернетика. № 1, 1985р. с. 148-156.

6. Радченко А.Н. Аппроксимация и точное формирование булевых функций многих переменных. II. эффективное построение ассоциативной памяти. Там же, 1985г. N 2, с. 98-106.

7. Радченко А.Н. Влияние размеров рецептивных полей сетчатки на точность восприятия изображений. Биофизика, 1991, т.36. № 3б, с.521-529.

8. Радченко А.Н. Ассоциативная память. Нейронные сети. Оптимизация нейропроцессоров. Санкт-Петербург: Наука, 1998 г. 261 с.

9. Радченко А.Н. Точностные параметры зрительного восприятия. Известия РАН. Серия биологическая. № 4, с. 458-468.

10. Радченко А.Н. Обеспечение инвариантности телевизионного канала к параметрам развертки. Автометрия, 1992 г. № 2, с. 98-107

УДК 681.32

ОБ ИНФОРМАЦИОННОЙ ЕМКОСТИ СИМВОЛЬНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ

М.Г.Садовский

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

Information capacity of frequency dictionary is the specific entropy calculated against the reconstructed dictionary which bears the continuations of strings and has maximal entropy. Some examples are provided. A structure revealed by the information capacity of an entity is discussed.

ВВЕДЕНИЕ

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

они были развиты. Открытым остается вопрос о том, могут ли быть выделены какие-нибудь структурные элементы в последовательности на основе той информации, которая может быть получена только в пределах самой исследуемой последовательности. Одним из ярких примеров выделения структурных элементов такого типа явилось описание последовательностей с помощью профиля их сложности [1-6].

Идея выделения структурных элементов только на основе той информации, которая может быть извлечена непосредственно из символьной последовательности позволяет сосредоточится на поиске закономерностей и порядка в символьных последовательностях, которые определяются исключительно взаимным расположением символов в этих последовательностях. Такого рода структурирование символьной последовательности хорошо тем, что не требует привлечения никакой дополнительной информации для выделения структурных единиц; с другой стороны, интерпретация такого рода структурных элементов и установление их смысла и/ или значения становится гораздо более трудной проблемой. Тем не менее, поиск и выделение такого рода структур и их структурных элементов является важным инструментом для анализа символьных последовательностей, в первую очередь, благодаря своей универсальности. Кроме того, для широкого круга символьных последовательностей наблюдается существенная корреляция между структурными элементами, выделяемыми с помощью статистических методов и иными, контекстно-зависимыми методами.

1. РЕАЛЬНЫЕ ЧАСТОТНЫЕ СЛОВАРИ,

ВОССТАНОВЛЕННЫЕ ЧАСТОТНЫЕ СЛОВАРИ И ИНФОРМАЦИОННАЯ ЕМКОСТЬ

Будем рассматривать последовательность длины N из

алфавита Л ; мощность алфавита Л равна М. Будем всюду впредь рассматривать только связные последовательности и их подпоследовательности. Словом Ю длины q будем называть любую (связную) подпоследовательность этой длины, встречающуюся в рассматриваемом тексте; 1 < q < N. Набор всех слов, встречающихся в тексте, будем называть носителем словаря. Частотным словарем будем называть носитель, в котором каждому элементу приписана его частота. Отметим, что мы будем рассматривать тексты, замкнутые в кольцо; мотивацию такого перехода см. в [7-11]. Тем самым, содержательно постановка вопроса об информационной емкости символьных последовательностей сводится к вопросу об информационной емкости их частотных словарей. Информационная емкость частотного словаря - это мера различия между реальными частотами слов, которые содержатся в таком словаре и теми частотами слов такой же длины, которые можно было бы ожидать, исходя из частот слов меньшей длины.

Итак, пусть /Ю - реальная частота слова Ю, а /Ю -ожидаемая частота этого слова. Тогда информационная емкость частотного словаря Wq, содержащего слова длины q, определяется как

5 = § -1

Очевидно, что значение информационной емкости (1) будет существенно зависеть от того, что именно понимается

по ожидаемыми частотами /Ю. Одним из возможных подходов к определению ожидаемых частот может быть такой, который основан на предположении о тех или иных статистических свойствах рассматриваемой последовательности; например, можно предполагать, что рассматриваемая последовательность порождена случайным бернуллиевским процессом, либо марковским процессом того или иного порядка. Кроме того, весьма важен также вопрос о той исходной информации, которая имеется в распоряжении исследователя для оценки ожидаемых частот. Так, например, предположение о марковости рассматриваемой символьной последовательности основано на знании некоторых свойств, полностью выходящем за рамки того знания, которое может быть почерпнуто собственно из самой символьной последовательности. Не обсуждая здесь деталей этого вопроса, зафиксируем, что мы будем оценивать ожидаемые частоты слов длины q только по той информации (либо знанию), которую можно получить только из рассмотрения изучаемой символьной последовательности. Единственным знанием, доступным исследователю, ограничившемуся рассмотрением символьной последовательности, является знание частот слов меньшей длины, содержащихся в тексте. Действительно, для того, чтобы получить частоты слов длины q-1, достаточно просуммировать частоты всех слов, различающихся только первым (либо последним) символом. Равенство двух этих сумм требует замыкания исходной последовательности в кольцо.

Рассмотрим частотный словарь толщины q-1 (т.е. содержащий слова длины q-1). Оценим частоты слов длины q по этому словарю. Оценивать ожидаемые частоты слов длины q

мы будем, исходя из максимально общего предположения о том, что словарь Wq ожидаемых частот /Ю должен содержать такие продолжения слов длины q-1, которые являются наиболее вероятными [7-9]. Здесь следует подчеркнуть, что всегда существует такая толщина словаря й* , для которой возможно однозначное восстановление любого частотного словаря большей толщины [12-17]. Отношение такой толщины словаря к логарифму длины всей последовательности можно считать мерой избыточности последовательности, и этот показатель выявляет некоторые биологически интересные закономерности в нуклеотидных последовательностях [12-16]. В общем же случае хотя бы одно слово длины q < й* имеет не одно, а несколько продолжений. Если продолжения слов длины q-1 неединственны, то в качестве словаря большей толщины возникает не один словарь (толщины q), а ансамбль словарей; все словари из ансамбля должны удовлетворять линейным ограничениям: они должны порождать исходный частотный словарь толщины q-1, но и этих ограничений недостаточно: несколько словарей могут порождать заданный. Здесь возникает задача выбора того словаря, который можно было бы считать продолжением рассматриваемого (толщины q-1). Принцип наиболее вероятного продолжения требует выбрать такой словарь (толщины q) из множества, энтропия которого была бы максимальна [7, 8]. Этот экстремальный принцип позволяет вычислить частоты такого словаря (будем называть его вос--становленным) явным образом. Для случая восстановления слов длины q по словарю толщины q-1 имеем:

/¿1 г

либо

/ • /

У1 1 г2 г3 - - - гд - 1 У 12

Л

'ьь... г _

^ = / • /

г1 г2 г1 г2

для случая восстановления словаря толщины 2 по словарю толщины 1. Подставляя (2, 3) в (1), получаем

5 =

/Ю • /Ю

§/ю • Ч т-/т I = • 1п/

+ §/ю • /юкега - §/Ю ^ / - §/Ю • /

где

Ю=

1 г2 l3lq - 1

Югq = г213г4-гч , а

Юкегп = ¿2г'з.'^- 1 ; I] обозначает г -ый символ, стоящий на ] -ом месте. Суммирование по "лишним" индексам дает

окончательно

либо

5 25q - 1 - 5q - 5q - 2^

5 251 — 52

Ю

2

для определения информационной емкости словаря толщины 2 по словарю толщины 1. Формулы (2) и (3) могут быть обобщены для случая восстановления частотного словаря толщины q по частотному словарю толщины q - £ >1 [7, 8]. Соответственно, формулы (5) и (6) также могут быть обобщены на случай восстановления словаря заданной толщины q по словарям произвольной толщины £. Информационная емкость частотного словаря в этом случае определяется следующим образом:

5 = ((! - * + 1 - Б - ^ - *- 1

* = qSl - Sq .

Всюду далее мы ограничимся случаем определения информационной емкости частотного словаря, сравниваемого с восстановленным по словарю толщины см (5, 6).

2. ПРИМЕРЫ ОПРЕДЕЛЕНИЯ ИНФОРМАЦИОННОЙ ЕМКОСТИ НЕКОТОРЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ

Будем рассматривать нуклеиновые кислоты как пример символьных последовательностей; эти последовательности записаны в четырехбуквенном алфавите. К настоящему времени количество расшифрованных последовательностей, осмысленных с точки зрения исследователей, исчисляется миллионами, а число полностью расшифрованных геномов (полных наборов наследственной информации того или иного организма) достигает тысяч. На рисунке 1 приведены кривые изменения информационной емкости пяти генов -038240, и37287, Х76706, Ш2863 и 746939; все они депонированы в БМББ-банке [18]. Таблица 1 содержит значения информационной емкости для семейства генов митохон-дриальных 128 РНК некоторых видов грызунов. Здесь информационная емкость определялась согласно (5, 6). Таблица 2 содержит результаты определения информационной емкости всех генов в геноме вируса Эбола (номер доступа ЛБ086833).

Таблица 1 - Условные энтропии реальных частотных словарей относительно восстановленных до той же толщины для митохондриальных 12Б РНК некоторых видов грызунов

Таблица 1 - Условные энтропии реальных частотных словарей относительно восстановленных до той же толщины для митохондриальных 12Б РНК некоторых видов грызунов

Последовательность, длина Толщина словаря

2 3 4 5 6

И12446, 769 0,0192 0,0302 0,1142 0,3048 0,3899

И12443, 766 0,0170 0,0227 0,1299 0,3336 0,3924

И12453, 763 0,0152 0,0174 0,1314 0,3381 0,4101

И12451, 768 0,0093 0,0236 0,1204 0,3614 0,4137

И12452, 761 0,0173 0,0221 0,1121 0,3575 0,4149

М63568, 783 0,0108 0,0226 0,1147 0,3298 0,4156

М63569, 788 0,0095 0,0249 0,1043 0,3658 0,4222

Последовательность, длина Толщина словаря

2 3 4 5 6

М63566, 782 0,0107 0,0275 0,1122 0,3191 0,4289

И12445, 762 0,0168 0,0210 0,1017 0,3645 0,4346

И12444, 761 0,0109 0,0394 0,1124 0,3159 0,4358

И12454, 769 0,0112 0,0235 0,1222 0,3217 0,4374

М63565, 784 0,0126 0,0271 0,1101 0,3375 0,4403

М63564, 783 0,0143 0,0266 0,1079 0,3246 0,4478

М63570, 790 0,0135 0,0327 0,1128 0,3341 0,4479

И12450, 773 0,0219 0,0220 0,1201 0,3322 0,4491

М63567, 782 0,0090 0,0275 0,1022 0,3104 0,4497

И12448, 765 0,0107 0,0227 0,1228 0,3455 0,4497

М63562 , 791 0,0160 0,0194 0,1125 0,2958 0,4512

М63563, 786 0,0108 0,0224 0,1118 0,3451 0,4657

И12447, 767 0,0173 0,0261 0,1023 0,3263 0,4674

М63571, 752 0,0147 0,0299 0,1272 0,3253 0,4715

И12449, 765 0,0115 0,0203 0,1112 0,3570 0,4864

Таблица 2 - Условные энтропии реальных частотных словарей относительно восстановленных до той же толщины для всех генов вируса Эбола. Последовательности обозначены номерами доступа к базе данный белков 8т1з8-Рго1

Последовательность, длина Толщина словаря

2 3 4 5 6

Р18272 0,0291 0,0177 0,0439 0,1547 0,3914

005127 0,0305 0,0174 0,0782 0,3597 0,4148

005128 0,0384 0,0274 0,0891 0,2955 0,4696

066819 0,0246 0,0270 0,0818 0,2787 0,5112

09УМС2 0,0280 0,0276 0,0947 0,3237 0,4471

005323 0,0178 0,0183 0,1019 0,3513 0,4917

005322 0,0292 0,0240 0,1170 0,3416 0,4959

005318 0,0097 0,0031 0,0137 0,0479 0,1957

-И-Ш7287 -Й-Х76706 -»-1112363

и

Рисунок 1 - Информационная емкость пяти генов

Еще одним примером символьных последовательностей являются тексты, записанные в языках с алфавитной системой письма (исключим из рассмотрения промежуточные случаи - японский и корейский языки, имеющие слоговую систему письма). Одна из интересных проблем сравнительного языкознания - изучение консонантности различных языков. Консонантность - это закономерности в чередовании гласных и согласных на письме и в речи. Здесь следует подчеркнуть, что сама по себе проблема передачи звуков на письме весьма сложна и требует специального рассмотрения; мы не будем подробно останавливаться на этом здесь [19]. Изучение закономерностей в чередовании гласных и согласных требует построения специально редуцированного алфавита. Возможны различные системы редукции; мы будем рассматривать в рамках настоящей статьи четырехбуквенную редукцию [20]. Такая редукция превращает исходный лингвистический текст в специальный - консонантный. В консонантном тексте все согласные буквы (определяемые согласно академической грамматике того или иного языка) заменены на символ <С>, все гласные - на символ <У>, все пробелы между словами - в символ <*>, а все остальные символы, встречающиеся в изучаемом тексте (знаки препинания и т.п.) - в символ <&>. В результате возникает связная символьная последовательность, для которой применимы все развитые выше методы. Таблица 3 содержит результаты определения консонантности 30 различных языков; в качестве лингвистического объекта, на материале которого определялась консонантность, использовались переводы Всеобщей декларации прав человека [21].

Таблица 3 - Сравнение различных языков мира по консонантности

Таблица 3 - Сравнение различных языков мира по консонантности

Язык Толщина словаря

2 3 4 5 6

польский 0,2009 0,0378 0,0246 0,0173 0,0283

румынский 0,2411 0,0563 0,0233 0,0216 0,0295

русский 0,2080 0,0743 0,0309 0,0290 0,0438

саамский 0,1461 0,1179 0,0311 0,0323 0,0330

сербский 0,2914 0,0384 0,0185 0,0248 0,0259

словацкий 0,2773 0,0435 0,0176 0,0328 0,0258

словенский 0,3062 0,0623 0,0158 0,0224 0,0225

украинский 0,2681 0,0652 0,0229 0,0314 0,0354

финский 0,1295 0,1535 0,0313 0,0266 0,0288

французский 0,1432 0,0805 0,0360 0,0423 0,0351

хорватский 0,3150 0,0330 0,0162 0,0270 0,0191

шведский 0,2124 0,1060 0,0335 0,0178 0,0255

эсперанто 0,2368 0,0788 0,0198 0,0304 0,0310

эстонский 0,2155 0,0688 0,0303 0,0223 0,0282

Важным приложением метода определения информационной емкости символьных последовательностей является выделение структуры в них с помощью сканирования окном определенного размера и вычисления информационной емкости выделенного фрагмента последовательности (5, 6). Понятно, что результаты такого сканирования будут зависеть до двух параметров: величины окна сканирования Ь и шага сканирования Т. Не обсуждая здесь всех особенностей процедуры выделения структуры в символьной последовательности указанным способом, приведем лишь иллюстрацию такого рода выделения структуры. Будем рассматривать геном вируса Эбола; зафиксируем величину окна сканирования Ь= 1200 символов и шага сканирования Т= 50 символов. Рисунки 2 и 3 содержат результаты построения такого рода сканов; на Рисунке 2 приведены результаты сканирования для словарей толщины 2, 3 и 6, а на Рисунке 3 - для словарей 4 и 5. Следует обратить внимание на то, что среднее значение информационной емкости выделявшихся фрагментов генома на толщине словарей 6 меньше, чем на толщине словарей 4 и 5.

< и 1 ' /Ш

и " \| |1 Г 1 А, А1............М,(

у 1 , "V \ 1 л г V И' V, Ш 1/11" чг

Язык Толщина словаря

2 3 4 5 6

албанский 0,2994 0,0485 0,0213 0,0299 0,0262

английский 0,1596 0,0824 0,0402 0,0292 0,0409

африкаанс 0,1103 0,1336 0,0405 0,0380 0,0422

баскский 0,2280 0,0643 0,0295 0,0280 0,0223

белорусский 0,2368 0,0665 0,0189 0,0240 0,0403

болгарский 0,2946 0,0314 0,0202 0,0217 0,0330

венгерский 0,2561 0,0653 0,0245 0,0240 0,0199

греческий 0,1959 0,0637 0,0286 0,0382 0,0340

датский 0,1650 0,1074 0,0152 0,0240 0,0332

исландский 0,1952 0,0928 0,0434 0,0230 0,0263

испанский 0,2340 0,0793 0,0151 0,0184 0,0290

итальянский 0,2262 0,0517 0,0340 0,0226 0,0208

каталонский 0,1737 0,0752 0,0365 0,0231 0,0318

латышский 0,2253 0,0604 0,0540 0,0332 0,0314

македонский 0,3109 0,0333 0,0199 0,0200 0,0302

немецкий 0,1446 0,0824 0,0252 0,0302 0,0283

Рисунок 2 - Сканирование генома вируса Эбола, толщина словаря 2, 3 и 6

Рисунок 3 - Сканирование генома вируса Эбола, толщина словаря 4 и 5

ЗАКЛЮЧЕНИЕ

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

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

ПЕРЕЧЕНЬ ССЫЛОК

1. Немытикова Л.А. Использование серийных характеристик для исследования эффекта кластеризации элементов в ДНК-молекулах // Вычислительные системы. - 1994, № 150. - с. 147-163, 227.

2. Lempel A., Ziv J. On the Complexity of Finite Sequences // IEEE Trans.of Inf.Theor. (1976), v.IT-22, issue 1, pp.75-81.

3. Гусев В.Д. Сложностные профили символьных последовательностей // Методы обработки символьных последовательностей и сигналов (Выч. системы, вып. 132). Новосибирск: ИМ СО АН СССР, 1989. С.35-63.

4. Орлов Ю.Л., Потапов В.Н. Оценка стохастической сложности генетических текстов // Выч. технологии. 2000. Т.5. С.5-15.

5. Кислюк О.С., Боровина Т.А., Назипова Н.Н. Оценка избыточности генетических текстов с помощью высокочастотной компоненты графа l-граммного разложения // Биофизика. 1999. Т.44, № 4. С.639-648.

6. Ossadnik S.M., Buldyrev S.V., Goldberger A.L., Havlin S., Mantegna R.N., Peng C.K., Simons M., Stanley H.E. Correlation approach to identify coding regions in DNA sequences // Biophys.J. 1994. V.67(1). P.64-70.

7. Bugaenko N.N., Gorban A.N., Sadovsky M.G. Maximum entropy method in analysis of genetic text and measurement of its information content // Open Systems & Information Dynamics, 1998, v.5, № 3, pp.265-278.

8. Бугаенко Н.Н., Горбань А.Н., Садовский М.Г. Об определении информационного содержания нуклеотидных последовательностей // Мол.биология (1996) т.30, № 3, с.529 - 541.

9. Sadovsky M.G. Information capacity of symbol sequences // Open System & Information Dynamics, 2002, v.9, № 1, pp.37-49.

10. Sadovsky M.G. Comparison of Symbol Sequences: No Editing, No Alignment // Open System & Information Dynamics, 2002, v.9, № 1, pp.19-36.

11. Бугаенко Н.Н., Горбань А.Н., Садовский М.Г. Информационная емкость нуклеотидных последовательностей и их фрагментов // Биофизика, (1997), т.42, вып. 5. - С.1047-1053.

12. Горбань А.Н., Попова Т.Г., Садовский М.Г. Гены вирусов человека менее избыточны, чем гены человека // Генетика (1996) т.32, № 2. - С.281-294.

13. Горбань А.Н., Попова Т.Г., Садовский М.Г. Избыточность генетических текстов и мозаичная структура генома // Мол.биология (1994) т.28, № 2. - С.313-322.

14. Попова Т.Г., Садовский М.Г. Избыточность генов уменьшается в результате сплайсинга // Мол.биология (1995) т.29, № 3. - С.500-506.

15. Попова Т.Г., Садовский М.Г. Интроны отличаются от экзонов по своей избыточности // Генетика (1995) т.31, № 10. - С.1365-1369.

16. Горбань А.Н., Миркес Е.М., Попова Т.Г., Садовский М.Г. Сравнительная избыточность генов различных организмов и их вирусов // Генетика (1993), т.29, № 9. - С.1413-1419.

17. Гусев В.Д., Куличков В.А., Титкова Т.Н. Анализ генетических текстов. I. l-граммные характеристики // Эмпирическое предсказание образов (Выч. системы, вып. 83). Новосибирск: ИМ СО АН СССР, 1980. - С.11-33.

18. www.ebi.ac.uk

19. Зиндер Л.Р. Очерк общей теории письма Л.: Наука. Ленинград. отд., 1987. 112 с.

20. Карева М.В., Садовский М.Г. Энтропийные методы в некоторых задачах лингвистики // 9 Всерос.конференция "Нейроинформатика и ее приложения", Красноярск 5-7 октября 2001. - С.125-127.

21. http://www.un.org

УДК 681.32:007.52

НЕЙРОКОМПЬЮТЕРНАЯ МОДЕЛЬ ПЕРВИЧНЫХ ТОРСИОННЫХ ПОЛЕЙ

В.Д.Цыганков

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

нетрадиционных технологий.

The neural computer interpretation of tor fields is proposed. It gives possibility for future development of new technologies.

1. ТРИ УРОВНЯ СУБФИЗИКИ