Физика процессов эволюции - Эбилинг В.
Скачать (прямая ссылка):
»(р) =Р(9(<0)-
Иначе говоря, существует отображение гёделевского числа, соответствующего последовательности q, в гёделевское число, соответствующее последовательности р.
По Колмогорову, сложность двоичного слова р 6 X относительно алгоритма
(или рекурсивной функции) F(q), q € X, определяется следующим образом (Звонкий, Левин, 1970):
JT*(p) := min i(q): F(q) = p. (11.38)
По теореме Колмогорова—Соломонова, существует оптимальный алгоритм Fo в том смысле, что
KfAp) <KF(p) + C VpeX*.
Сложность относительно этого оптимального алгоритма обозначается К(р) и называется сложностью последовательности р. По теореме Колмогорова, К(р) является верхней гранью сложности последовательности символов, задаваемой длиной последовательностей, т. е.
где С — не зависящая от р константа. Понятие алгоритмической энтропии является обобщением шенноновской энтропии. Шенноновскую энтропию последовательности мы определяем по формуле (11.22) как величину '
л
Я,(р) = -Х>»к*й*, (11.40)
к-1
где ft* = vk/v — относительная частота появления символа А„, vk — абсолютная частота символа А„ в слове р. По Звонкину и Левину (Звонкин, Левин, 1970), для двоичной последовательности справедлива теорема
К(р) s: [vH\ (р) + С0 + С, In и], (11.41)
где v — длина последовательности, Са и С\ — константы, не зависящие от р.
Исследования, о которых мы упоминали выше, естественно приводят к вопросу
о том, как связаны между собой сложность и шенноновская энтропия. Связь между
этими величинами устанавливает важная теорема Звонкина и Левина (Звонкин,
Левин, 1970) и более поздняя работа (Leung-Yan-Cheong, Cover, 1978).
Теорема. Для каждого эргодического процесса с конечным алфавитом соотношение
(11-42>
выполняется в пределе при 1(р) —» оо с вероятностью единица. Таким образом, сложность в смысле Колмогорова— Чейтина с вероятностью единица сходится к шенноновской энтропии источника сообщений.
Учитывая это, мы определяем алгоритмическую энтропию на символ (букву) следующим образом:
, > К(р)
Наяг(р) = 1§)- (11-43)
Как нетрудно убедиться, величина
КН(Р) = /(р)Я(р) (11.44)
удовлетворяет аксиомам Тиле и поэтому является сложностью в смысле Ткле. Мы вычислили if-сложности для некоторых биологических последовательностей в предположении, что биополимеры в первом приближении можно рассматривать как марковские процессы первого порядка, т. е. что
Я(р) = Я2(р)-Я,(р).
Избыточность вычислялась по формуле
р _ . Кн(р) Я(р)
s Щт{р) ятах(р)' ^ ‘ ^
Мы видим, что Я-избыточность совпадает с шенноновской избыточностью с точностью до выбора Ятах(р). При вычислении шенноновской избыточности, вообще говоря, вводят предположение о том, что Ятах(р) = log А (Gatlin, 1972).
Более подробный анализ показывает, что формула Ятах(р) = log А неприменима к относительно коротким последовательностям. В частности, это следует иметь в виду при вычислении избыточности белков. Рассмотрим в качестве примера
последовательности цитохрома с длиной 104. В такой последовательности могут реализоваться самое большее 103 различные пары, т. е.
НГ = log [i(p) - 1] = log 103 = 1,547.
Чтобы построить 103 различные пары, нам необходимо самое большее 11 различных символов, из которых 5 символов должны встречаться 10 раз и 6 символов 9 раз, т. е.
НГ = log 104 - — [50 log 10 + 54 log 9] = 0,800.
104
Окончательно получаем:
д-max = япих _ д-min = ^ ^ знаков)
Например, для цитохрома с человека вычисленное нами значение Rg = 0,267 оказывается значительно ниже значения R = 0,447, полученного Гатлином. Другие исправленные значения для различных белков приведены в табл. 11.6. У последовательностей ДНК этот эффект играет не столь заметную роль, поскольку для них 1(р) > 16 (Ebeling, Feistel, Herzel, 1987).
Таблица 11.6. Сложности, избыточности и длины программ, вычисленные на основе
порождающих грамматик (KG, Rg, Lg). анализа частичных слов (Кт, Rt) и шенноновских энтропий (Kg, RB) (Ebeltng, Jimenez-Montano, 1980).
Сорт Ка Кт Ка Rg Ду Ra 1 La
ДНК В. coli, ген тиро 85 120,37 119,70 0,105 0,0298 0,045 126 37
зина тРНК
ДНК вируса Х174, ген 1 78 --- 99,91 0,125 --- 0,100 111 32
ДНК человека, 55 г КВ 84 _ 112,56 0,086 _ 0,062 120 46
