Московский Государственный Университет Факультет Вычислительной Математики и Кибернетики К У Р С О В А Я Р А Б О Т А "Программа для анализа генетических текстов с помощью ЭВМ" Студента кафедры Системного Программирования ЗАХАРОВА МАКСИМА Научные руководители: Матекин М.П. Бахарев И.А. Наумов Н.А. Коротков Е.В. МАЛЕНЬКОЕ ВВЕДЕНИЕ По современным данным у человека имеется от 50 до 100 тыс. генов, упакованных всего в 46 хромосом. Полный их набор встречается в ядре практически каждой клетки человека. Гены управляют ростом и жизнеспособностью организма. Недавно удалось установить, что заболевания сердца, рак и другие серьезные растройства здоровья обусловлены наличием дефектов в двух, трех или нескольких генах. Ряд ученых считают, что практически каждое заболевание имеет тот или иной генетический компонент. Выявление "виновных" генов позволит открыть важнейшие подступы к диагнозтике и лечению заболеваний. Не исключено, что уже в ближайшее время удастся найти генетические методы лечения гемофилии и некоторых видов рака. По материалам Ридерз Дайджест, ноябрь 1991. ОСНОВНАЯ ИДЕЯ АНАЛИЗА Известно, что генетическую информацию несут нуклеиновые кислоты клетки. Вся совокупность генов, а также участки пунктуации (фрагменты, отвечающие за регуляцию основных генетических процессов) называются геномом. В настоящее время геномы многих простейших хорошо изучены. Анализ же геномов высших животных невозможен без применения ЭВМ из-за огромного объема информации. Молекулы нуклеиновых кислот состоят из четырех еще более мелких молекул (A-аденина, C-цитозина, G-гуанина и T-тимизина). Поэтому геном можно рассматривать как текст из четырех букв: ACGT. Основная идея заключается в установлении закономерностей участков генетических текстов, соответствующи тем или иным генам или знакам пунктуации И при помощи установленных закономерностей попробовать провести анализ еще неизученных геномов. Цель данной курсовой работы - создание программы, производящей анализ генетических текстов нижеописанным методом. ИСПОЛЬЗУЕМЫЙ МЕТОД АНАЛИЗА Будем считать генетический текст сообщением, состоящим из алфавита: ACGT. Каждую букву такого текста можно представить с помощью двух бит (00,01,10,11). Энтропией генетического текста назовем величину: H2 = -(n0*log2(n0)+n1*log2(n1))*size, где n0 - частота нулей в двоичнм представлении текста; n1 - частота единиц; size - количество битов в двоичном представлении текста. Используемый метод анализа состоит в следующем: к каждому возможному подинтервалу гинетического текста (или к некоторому подмножеству всех возможных подинтервалов) применяется один из методов сжатия информации, основанный на учете заканомерностей сжимаемого текста. Для сжатого текста также подсчитывается энтропия H2 (сжатый текст составлен из другого алфавита, но битовую энтропию для него можно подсчитывать, если представлять его как последовательность битов). Среди всех рассматриваемых подинтервалов находится такой, у которого минимальное отношение Hout/Hin,где Hout - энтропия сжатого текста; Hin - энтропия генетического текста. Этот интервал выбрасываем из дальнейшего рассмотрения. Вообще говоря выбрашенный интервал делит текст на две части. Вышеописанный алгоритм выбрасывания применяется для каждой из них независимо. Разбиение происходит до тех пор, пока длина подинтервала текста станет меньше заданной. Во время работы вышеописанного алгоритма производится построение множества длин выбрасываемых подинтервалов. Для каждого элемента такого множества строится спектр степени сжатия всевозможных подинтервалов данной длины. Эта часть программы вставлена по требованию Е.В.Короткова, ее назначение непонятно. МЕТОДЫ СЖАТИЯ ИНФОРМАЦИИ В программе используются два метода сжатия информации, основанных на поиске закономерностей сжимаемого текста. Первый метод: классический алгоритм Lempel-Ziv'77 с небольшими модификациями: размер окна предыстории равен 2/5 сжимаемого текста, но не превышает 254 байта, причем для избежания тупика алгоритма первые 4 байта окна всегда равны ACGT, т.е. алфавиту генетического текста; вторая модификация заключается в том, что помимо отыскания нормального повторения цепочки из предыстории ищется и повторение ее зеркального отражения; в-третьих, длина повторяющейся цепочки не может превышать 16 байт. (Метод именуется в программе: LZ). Второй метод заключается в том,что каждой букве алфавита ACGT в порядке убывания частоты вхождения в текст ставится в соответствие один из следующих весов: 1,5,20,60. Сжатие текста производится по следующему алгоритму: тек_код:=0; для каждой буквы текста находится ее вес: тек_вес; если тек_код < next(тек_вес) - тек_вес тогда тек_код:=тек_код + тек_вес иначе записать тек_код; тек_код:=тек_вес. next(тек_вес) - следующий по возрастанию вес, для 60 равно 255. Таким образом степень сжатия исходного файла в какой-то мере зависит от порядка следования букв в тексте. (Имя метода в программе: ZM). ПРЕДВАРИТЕЛЬНЫЕ РЕЗУЛЬТАТЫ В настоящее время с помощью ЭВМ просчитано давольно мало текстов, уже изученых. Основная причина: большие затраты машинного времени. Частичное совпадение полученного разбиения с уже известным получается в большинстве случаев при анализе вторым из описанных методом. Полученной информации для анализа неизученных генов пока нехватает. Примеры результатов анализа см. Приложение Б. ИСПОЛЬЗОВАНННАЯ ЛИТЕРАТУРА 1.Ридерз Дайджест, ноябрь 1991. 2.Р.Кричевский. Сжатие и поиск информации. Радио и связь, 1989. 3.Р.Стратанович. Теория информации. Советское радио, 1975. 4.В.Гусев, В.Куличков, О.Чупахина. Сложностной анализ геномов ч.I. Молекулярная биология, том 25 вып.3 1991. 5.В.Гусев, В.Куличков, О.Чупахина. Сложностной анализ геномов ч.II. Молекулярная биология, том 25 вып.4 1991.