Компьютерный анализ генетических текстов - Александров А.А.
ISBN 5-02-004691-4
Скачать (прямая ссылка):
Стоит отметить еще один способ представления последовательностей в некоторых системах. В этих системах последовательность нуклеотидов превращается в последовательность перекрывающихся 1-грамм (см.гл.1). Например, Т кодируется О, С-1, А-2, G-З. Тогда 1-грамм кодируется целым числом в интервале от 0 до 4*-1, а последовательность нуклеотидов превращается в последовательность целых чисел (рис. 7.1). Такое представление используется в некоторых программах быстрого поиска гомологии (Fondrat et al., 1986).
Т С A GAATGTAC
6____
27___
46____
58___
40____
Рис. 7.1. 3-нуклеотидное кодирование последовательности. В результате кодирования получается последовательность 6,27,46,58,40 ...
Сжатие информации. Сжатие (синоним упаковка) представляет собой однозначно декодируемую перекодировку последовательности. Коэффициентом сжатия К будем называть отношение количества байтов, занимаемых посимвольным представлением, к количеству байтов, занимаемых перекодированной, сжатой последовательностью. Таким образом, для по-
символьного представления коэффициент сжатия равен единице. Введем также среднюю длину кода:
L=E diPi. i
где d. - длина кода для i-й буквы; р, - вероятность i-й буквы.
Для информации, записанной байтами К = 8/L.
Существует по крайней мере два способа сжатия информации: не использующий и использующий статистические свойства последовательности символов. Очевидно, что в первом случае для последовательности с алфавитом из четырех символов максимальное сжатие информации возможно с коэффициентом 4 (метод 1). Для последовательности, где допускается 5 символов T,C,A,G,N, коэффициент сжатия не превышает 8/log25=3,445 (метод 2).
Выбор того или иного метода сжатия зависит не только от выигрыша в объеме внешней памяти, но и от других обстоятельств, а именно затрат на раскодировку, выигрыша в длительности считывания информации из внешней памяти, обеспечения возможности прямого доступа и др.
Раскодировка в методе 1 проста на любом языке программирования, в котором имеется возможность работы с отдельными битами. В методе 2 алгоритм раскодировки несколько сложнее. Можно закодировать последовательности, упаковывая тринуклеотиды в один байт (метод 3), коэффициент сжатия равен трем. Раскодировка осуществляется довольно просто. По этому же принципу можно закодировать 1-грамму в m байт. Приведем коэффициенты сжатия для пятибуквенного алфавита для различных значений m ([] обозначает целую часть числа):
Коэффициент сжатия
L log25 J
1 3 3
2 6 3
3 10 3,33
Л 13 3,25
5 17 3,4
Таким образом, в случае ш=5, 1=17 коэффициент сжатия близок к предельному.
Рассмотрим статистические способы кодирования. В методе 2 каждый из пяти символов кодируется одинаковым количеством бит. При этом редко встречающийся символ N кодируется неэкономно. Справедливо утверждение (см.Марков, 1982, с.165-166), указывающее предельную величину сжатия: средняя длина кода, оптимального в смысле длины L(B*,P)=H(P) + f(P), где 0<=Г(Р)<1; Р={р() - распределение вероятностей для букв алфави-
та: В* - множество сообщений из букв алфавита, удовлетворяющее некоторым дополнительным условиям, которые мы здесь не будем указывать; Н(Р)=-Ер,logjP, - шенноновская энтропия. Можно показать, что величина Г(Р) с помощью блочного кодирования может быть сделана сколь угодно близкой к 0. Таким образом, среднюю длину кода можно сделать сколь угодно близкой к величине энтропии последовательности в расчете на одну букву. Заметим, что сама величина энтропии зависит от модели порождения текста (см. "Представление молекулярно-генетических
ДЗ.ННЫХ } •
Алгоритм построения оптимального кода был предложен Хафманом (см. Марков, 1382). Приведем пример оптимального кода. Будем считать,
1 1
что веэоятность появления Т. f%A,G равна р— - -p(N), а вероятность
4 4
появления v'! p(N)<-'p, Идея статистического кодирования г тг:*.:
что наиболее вероятные символы кодируются коротким кодовым словом, редкие - длинным. Закодируем Т=00. С=01, А=10, G=110, N=111. Можно показать, что э^от код является однозначно декодируемым. (Обеспечение однозначной декодируемости является причиной того, что одна из букв Т, С, A, G, все равно какая, кодируется тремя битами.) Средняя
11 11 длина кода l-3p(N)+3*2( - -p(N))+3(- - -р(N)) = 2,2b+0,75p(N) бит.
4 4 4 4
Коэффициент сжатия в этом случае равен 3,55. Это еще не предел. При кодировании 1-граммы имеется 4: "хороших" 1-граммы, т. е. не содержащих N, и 5*-4‘ "плохих" 1-граммы, они имеют малую вероятность.
Пусть вероятность "плохой” 1-граммы не превосходит q, а сумма вероятностей всех "плохих" 1-грамм не превосходит вероятности любой из "хороших". Закодируем 4‘-1 "хороших" 1-грамм 2*1 битами, 1 "хорошую" 1-грамму 2k+i битами. R=5‘-4! "плохих" 1-грамм 2*1+п битами, где п наименьшее число, определяемое из условия 2”>5‘-4‘. Тогда К можно оценить следующим образом: при 1=3, max значение К=3,98,
