Основы биоинформатики - Огурцов А.Н. 2013

Основания биоинформатики
Понятие «информация»
Количество информации

В 1948 году 28-летний сотрудник американской компании Bell Telephone Laboratories Клод Элвуд Шеннон (Claude Elwood Shannon) (1916-2001) опубликовал в журнале "Bell System Technical Journal" фундаментальную работу "Математическая теория связи". С её появлением обычно связывают возникновение классической (статистической) теории информации.

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

И хотя в классической теории информации вопрос "Что такое информация?" даже не ставится и, вообще говоря, сама классическая теория информации практически бесполезна в вопросах биоинформатики, но для общего образования полезно ознакомиться с определением количества информации, введённым Шенноном на примере текстового сообщения.

Формула Шеннона. Количество информации, I_N, в сообщении, содержащем N символов, равно

где М - число букв в алфавите; р_i — вероятность (частота) встречаемости і -й буквы в языке, на котором написано сообщение; знак "минус" перед всей правой частью формулы поставлен для того, чтобы количество информации было всегда положительным, несмотря на то, что log₂p_i < 0, поскольку р_i < 1.

Двоичные логарифмы в формуле Шеннона выбраны для удобства. Например, при однократном бросании монеты М = 2 ("орел" или "решка"), N = 1 и

При этом получаем минимальное количество

информации (I = 1), которое называется "бит" ("bit" от англ. binаry digit).

Иногда в формуле Шеннона используются натуральные логарифмы. Тогда единица информации называется "нат" и связана с битом соотношением: 1 бит = 1,44 ната.

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

Для примера возьмём некоторый текст, который можно рассматривать как результат выбора определённого варианта расстановки букв.

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

Если все варианты равновероятны, то есть то

В частном случае сообщения из N букв из бинарного алфавита (М = 2) число вариантов равно: n = 2^N и количество информации I = N.

На этом примере удобно пояснить, что означает слово "равноправные" в определении информации. Представим, что в тексте имеются символы, которые в алфавите вообще не содержатся (не "буквы").

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

Отметим, что формула Шеннона отражает количество информации, но не ценность её.

Поясним это на примере. Количество информации в сообщении, определяемое формулой Шеннона, не зависит от того или иного сочетания букв: можно сделать сообщение бессмысленным, переставив буквы. В этом случае ценность информации исчезнет, а количество информации останется прежним. Из этого примера следует, что подменять определение информации (с учетом всех её качеств) определением количества информации нельзя.

Вернемся снова к формуле Шеннона и проанализируем, например, текст "Завтра будет буря". Действительно, осмысленность или информация текста "Завтра будет буря" очевидна. Достаточно, однако, сохранив все элементы (буквы) этого сообщения, переставить их случайным образом, например, "рдеа Звубуб траяи", как оно утратит всякий смысл. Но бессмысленной информации не бывает. Согласно же формуле Шеннона оба предложения содержат одинаковое "количество информации". О какой же информации здесь идет речь? Или, вообще, можно ли говорить об информации по отношению к разрозненным элементам сообщения?

Очевидно, отдельные элементы сообщения можно назвать "информацией Шеннона" лишь при условии, если перестать связывать информацию с осмысленностью, то есть с содержательностью. Но тогда это бессодержательное нечто вряд ли стоит называть "информацией", вкладывая в первичный термин несвойственный ему смысл.

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

Очевидно, что ёмкость тары не зависит от того, заполнена ли она и чем она заполнена. Поэтому частотную характеристику элементов сообщения (или количество информации, связанное с і -й буквой алфавита), которое определяется как H_i = -log₂ p_i лучше называть не "количеством информации", а "ёмкостью информационной тары". Это, кстати, хорошо согласуется с формулой Шеннона, по которой "количество информации» в данном сообщении не зависит от порядка следования составляющих его букв, а только от их числа и частотных характеристик.

Очевидно, что в терминах Шеннона количество информации в интроне и экзоне равной длины одинаковое, в то время как экзон участвует в биосинтезе белка (имеет смысл) а интрон - нет.

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

Семантика - раздел языкознания, изучающий смысловое значение единиц языка.

Приведем пример. Имеется текст на русском языке, содержащий N_K букв кириллицы (алфавит содержит 32 буквы). Перевод его на английский содержит N_L букв латинского алфавита (26 букв). Русский текст - это результат выбора определённого расположения русских букв (число вариантов порядка 32^NK). Английский перевод - это выбор определённого расположения латинских букв, который предопределен русским текстом (рецепция информации). Число вариантов в английском текста порядка 26^NL. Количество ценной информации одинаково (если смысл не искажен), а количество информации, в том смысле, как оно определяется формулой Шеннона, различно.

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

Так, в процессе трансляции генетическая информация "переливается" из нуклеотидной информации, записанной в молекулах ДНК, в аминокислотную белковую информацию. При этом, как правило, количество информации изменяется, но количество ценной информации сохраняется.

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

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

Информация и энтропия. Понятие "энтропия" (от греческого слова, означающего "поворот", "превращение") было введено в физику в 1865 г. Рудольфом Клаузиусом (Rudolf Clausius) как количественная мера неопределенности. Согласно второму началу термодинамики, в замкнутой системе энтропия либо остаётся неизменной (если в системе протекают обратимые процессы), либо возрастает (при неравновесных процессах), а при состоянии равновесия достигает максимума.

Статистическая физика рассматривает энтропию (обозначаемую символом S) в качестве меры вероятности пребывания системы в данном состоянии. Людвиг Больцман отмечал (1894 г.), что энтропия связана с "потерей информации", поскольку энтропия сопровождается уменьшением числа взаимоисключающих возможных состояний, которые остаются допустимыми в физической системе после того, как относящаяся к ней макроскопическая информация уже зарегистрирована.

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

Норберт Винер писал: "Как энтропия есть мера дезорганизации, так и передаваемая рядом сигналов информация является мерой организации. Действительно, передаваемую сигналом информацию возможно толковать, по существу, как отрицание её энтропии и как отрицательный логарифм её вероятности. То есть, чем более вероятно сообщение, тем меньше оно содержит информации". Мера неопределенности - это число двоичных знаков, необходимое для фиксирования (записи) произвольного сообщения от конкретного источника, либо среднее значение длины кодовой цепочки, соответствующее самому экономному способу кодирования.

Леон Бриллюэн (Leon Nicolas Brillouin) развил так называемый негэнтропийный принцип информации, согласно которому информация — это энтропия с обратным знаком — негативная энтропия (негэнтропия). Бриллюэн предложил выражать информацию (I) и энтропию (S) в одних и тех же единицах - информационных (биты) либо физических (эрг/град). В отличие от энтропии, рассматриваемой в качестве меры неупорядоченности системы, негэнтропия - мера её упорядоченности. Применяя вероятностный подход, можно рассуждать следующим образом. Допустим, физическая система имеет несколько возможных состояний. По Бриллюэну увеличение информации о физической системе эквивалентно фиксированию этой системы в одном определённом состоянии, что приведет к уменьшению энтропии системы, I + S = const. Чем больше известно о системе, тем меньше её энтропия. При утрате информации о системе возрастает энтропия этой системы. Увеличивать информацию о системе можно, лишь увеличивая количество энтропии в среде вне системы, причем всегда ∆S ≥ I.

В соответствии со вторым началом термодинамики энтропия замкнутой системы не может убывать со временем. Формально получается, что в замкнутой системе (например, в тексте) увеличение энтропии может означать только "забывание" информации, чтобы равенство I + S = const сохранялось. При этом возникновение новой информации возможно только в открытой системе, где параметры порядка становятся динамическими переменными.