Введение в Алгебраическую теорию информации - Гоппа В.Д.
Скачать (прямая ссылка):
2) Каждая пара двоичных символов одинаковое число раз встречается в
слове.
88
3) Каждая группа из (m + 1) символов одинаковое число раз встречается
в слове.
Таким образом, m-информация слова максимальна и практически отсутствует
память. Кроме того, в слове наблюдается минимальное количество симметрий.
Отсутствие симметрий обычно воспринимается как случайность, поэтому
последовательности с описанной идеальной информационной характеристикой
называют псевдослучайными.
Принцип построения таких последовательностей поясним на примере т = 3, п
= 16. Обозначим:
ООО - А 100 - Е
001 - В 101 - F
010 - С 110 - G
011 - D 111 - Я
Мы хотим построить последовательность X этих букв, такую,
что переходная матрица X -* ТХ имеет следующий вид:
А В С D Е F G я
А 1 1 2
В 1 1 2
С с- 1 1 2
D 1 1 2
Е 1 1 2
F 1 1 2
С 1 1 2
Н 1 1 2
222 2 2222 Соответствующий эйлеров граф можно представить как
16
Найдем остовное дерево, входящее в А:
Вписываем это дерево в xQ <8> у\
'о'
Уо
(АА ВВ СС DD ЕЕ FF GG ЯЯ С Е G А С F G
89
Заполняем остальные буквы слова >'Q и применяем алгоритм
вычеркивания:
х0(А А В В С С D D Е Е F F G G Н
\ABDCFEHGBADCEFHG)-*
1 2 3 9 10 15 4 12 8 16 11 14 7 13 5 6
-* (AABDHHGEBCFDGFCE).
Выписываем теперь каждую букву в виде двоичного столбца:
'0 000111100101101' 0001111001011010 0011110010110100
A A BDHHG Е ВС FDG FC Е
V /
Верхняя строка определяет нужную нам псевдослучайную последовательность:
х = (0000111100101101).
Эта последовательность порождается нелинейным регистром сдвига:
F(x)
СПИ
' Сдвиг влево
В зависимости от состояния регистра (jtj, х2, х^, х4) формируется
значение некоторой булевой функции F(xv х2, х3, х4), которое определяет
следующее состояние:
0000 - 0001 0001 - 0011
5.5. Генетическая информация
Наследственная информация (генетический материал) у всех растений,
животных, микроорганизмов и большинства вирусов представляется словами
большой длины в четырехбуквенном алфавите:
ATGGTTCGTTCTTAT...
Каждое такое слово представляет собой полимерную молекулу ДНК, в состав
которой входят четыре основания (нуклеотида):
А - аденин С - цитозин
G - гуанин Т - тимин
90
Существуют особые водородные связи А**Т и G ** С (комп-лементарность).
Такое попарное сопоставление нуклеотидов было выведено с помощью
молекулярных моделей, на которых точно выдерживались все межатомные
расстояния.
Природная молекула ДНК представляет собой две полимерные цепи попарно
соединенных нуклеотидов, закрученные в форме двойной спирали (модель
Уотсона-Крика):
(ATGGTTCGT ...\
[TACCAAGCA ...J'
Если отождествить ДНК с внешней памятью компьютера, например с магнитной
лентой, то можно сказать, что информация записывается избыточно, так что
к исходному слову приписывается его шаблон в дополнительном коде.
Введем в рассмотрение конечное поле = (0, 1, а, р), в котором операции
производятся по модулю неприводимого многочлена х2 + х + 1, так что а +
/3=1, а/? = 1. Поэтому можно сопоставить нуклеотиды и элементы поля F :
/О, 1, а,/3 \
\A,T,G,Cy
так что дополнительный нуклеотид определяется по правилу х -* 1 + х.
Таким образом, А -* А + 1 = Т, G -* G + 1 = С.
Очень длинные молекулы ДНК упакованы в клетке в небольшом объеме. Общая
длина ДНК хромосом человека (около
109 нуклеотидов) упакована в ядре диаметром меньше микрометра. Это
означает, что в клетке ДНК компактизована.
Определенные отрезки (подслова) слова ДНК, несущие смысловую нагрузку,
называются генами. Каждый ген кодирует информацию, ответственную за
создание определенного белка.
Средняя длина гена у человека порядка 104 нуклеотидов (букв).
Таким образом, у человека присутствует порядка 105 различных белков.
Пути переноса информации, закодированной в ДНК, обобщены Ф. Криком в виде
центральной догмы молекулярной биологии:
91
Сплошные стрелки обозначают здесь три основных великих канала передачи
биологической информации: репликация, транскрипция и трансляция.
Продолжая аналогию с компьютером, в которой ДНК отождествляется с внешней
памятью, можно сказать, что репликация соответствует копированию
(размножению) магнитных лент. Транскрипция соответствует записи в
оперативную память (РНК), а трансляция-обработке информации (построению
белков) .
Возможны ,и особые случаи переноса информации (на схеме они представлены
штриховыми линиями. Так, наблюдалась репликация РНК и обратная
транскрипция от РНК к ДНК. Далее, информация может непосредственно
преобразовываться из ДНК в белок, минуя РНК (это наблюдалось в случае
антибиотиков). "Запрещен" перенос информации от белков обратно к
нуклеиновым кислотам. Это означает, что модификация белков (генных
продуктов) не наследуется.
Способность ДНК к самовоспроизведению (репликации) лежит в основе
размножения живых организмов. Модель двойной спирали позволила понять
принцип удвоения ДНК. Представлялось логичным, что при удвоении ДНК две
хромосомные нити "расплетаются", а затем каждая из них служит базисом, на
