Восстановление отсутствующих данных в символьных последовательностях

Рубцов, Антон Геннадьевич

Математическое моделирование, численные методы и комплексы программ

автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Восстановление отсутствующих данных в символьных последовательностях

кандидата физико-математических наук: Рубцов, Антон Геннадьевич
город: Красноярск
год: 2010
специальность ВАК РФ: 05.13.18

Диссертация по информатике, вычислительной технике и управлению на тему «Восстановление отсутствующих данных в символьных последовательностях»

Автореферат диссертации по теме "Восстановление отсутствующих данных в символьных последовательностях"

иа34Э1672

На правах рукописи

РУБЦОВ Антон Геннадьевич

Восстановление отсутствующих данных в символьных последовательностях

05.13.18 - математическое моделирование, численные методы и комплексы

программ

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

1 1 ФЕВ 2019

Красноярск 2010

003491672

Работа выполнена в Институте вычислительного моделирования Сибирского отделения РАН, г. Красноярск

Научный руководитель:

кандидат физико-математических наук Сенашова Мария Юрьевна

Официальные оппоненты: доктор технических наук

Миркес Евгений Моисеевич

доктор физико-математических наук, профессор Смирнова Елена Валентиновна

Ведущая организация:

ГОУ ВПО «Сибирский государственный аэрокосмический университет им. М.Ф. Решетнева», г. Красноярск

Защита состоится 19 февраля 2010 года на заседании диссертационного совета ДМ 212.099.06 при Сибирском федеральном университете по адресу: 660074, г. Красноярск, ул. Киренского, 26.

С диссертацией можно ознакомиться в научной библиотеке Сибирского федерального университета по адресу: г. Красноярск, ул. Киренского, 26, Г 274.

Автореферат разослан «19» января 2010 года.

Ученый секретарь

диссертационного совета

Р.Ю. Царев

Общая характеристика работы

Актуальность. Подавляющее большинство методов обработки и анализа данных работают только с полными данными. На практике очень часто встречаются ситуации, когда какая-либо часть данных отсутствует. Для того чтобы иметь возможность обрабатывать такие данные, необходимо отсутствующие данные восстановить. Существуют различные подходы к этой задаче. Большинство методов позволяет получить значения для пропущенных данных, исходя из принципа максимальной похожести восстановленных данных на полные имеющиеся данные.

При проведении статистического анализа на практике ограничиваются анализом не всей генеральной совокупности в целом, а лишь некоторого выборочного числа наблюдений. Анализируемая выборка должна отвечать критериям качественности и полноты. Но в ситуациях, когда некоторые свойства у исследуемых объектов отсутствуют, происходит смещение основных статистических характеристик. Например, смещения математического ожидания и дисперсии возрастают прямо пропорционально числу пропусков. То есть ошибка напрямую зависит от количества отсутствующих данных. Причиной таких пропусков могут послужить, например, отсутствие значений вследствие каких-то мелких поломок оборудования, не связанных с экспериментальным процессом, или нежелание респондента при проведении статистического опроса отвечать на вопросы о своих доходах.

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

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

Символьные последовательности - это классические объекты математики и встречаются как предмет изучения во многих прикладных задачах, от теоретического программирования и теории управления до биологии и

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

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

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

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

Методы исследований. Для решения поставленных задач использовались методы эволюционной оптимизации, мелкозернистый параллельный вычислитель (КМК), методы матричной алгебры.

Основные результаты.

- разработан подход к восстановлению отсутствующих данных с помощью кинетической машины Кирдина. Модифицирован и реализован имитатор КМК применительно к задаче восстановления данных.

- получен способ представления опорного частотного словаря в матричной форме. Даны определения матрицы заполнений и индикаторной матрицы. Сформулировано и доказано утверждение о том, что возведение мат-

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

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

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

словари). Оценка сверху числа заполнений дается выражением | ЛП^ (N -мощность алфавита, Ь - длина отсутствующей части), что для алфавитов и характерных размеров пропусков, встречающихся в различных приложениях, представляет собой достаточно большую величину (порядка 1012). Таким образом, задача построения заполнения простым перебором вариантов представляется весьма ресурсоемкой. Необходим метод, снижающий вычислительные затраты. Кроме того, построение каждого из вариантов заполнений не зависит от построения других заполнений, что сделало возможным использование подходов и методов параллельных вычислений.

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

Однако использование КМК не решает вопрос о существовании заполнения из опорного словаря в силу своей стохастичности. В связи с этим был предложен принципиально новый подход - особое матричное представление опорного частотного словаря.

Для всякого частотного словаря возможны три (различных) матричных представления. Первое полностью эквивалентно самому частотному словарю, второе соответствует Марковскому процессу порядка д -1, который

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

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

Значение для теории. Для восстановления отсутствующих данных разработан метод, применимый для последовательностей с различными параметрами. В качестве параметров рассматривались: длина отсутствующей части последовательности, мощность алфавита, составляющего последовательность, мощность частотного словаря, построенного по последовательности.

Решен вопрос о существовании и построении заполнения из слов заданного частотного словаря. Кроме вопроса о существовании заполнения решен вопрос о числе таких заполнений, удовлетворяющих граничным условиям.

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

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

Личный вклад автора. Все результаты, выносимые на защиту, получены лично автором.

Рекомендации по использованию результатов диссертации. Результаты диссертации могут быть использованы в научно-исследовательских организациях, занимающихся обработкой и анализом генетических последовательностей, в частности в Институте цитологии и генетики СО РАН, Институт биологии гена РАН, Институт молекулярной генетики РАН. Кроме

того, результаты диссертации могут быть использованы как основа для спецкурсов в профильных высших учебных заведениях.

Апробация результатов диссертации. Результаты работы были представлены на IX и X Всероссийском семинаре «Моделирование неравновесных систем», XI международной конференции «Информационные и математические технологии в научных исследованиях», XIV и XV Всероссийском семинаре «Нейроинформатика и ее приложения», пятой школе-семинаре «Распределенные и кластерные вычисления», международной конференции «Компьютерное моделирование и интеллектуальные системы», XII Байкальской Всероссийской конференции «Информационные и математические технологии в науке и управлении», VI и VII Всероссийских ФАМ конференциях.

Публикации. По теме диссертации опубликовано 15 научных работ, в том числе: 1 статья в периодических изданиях по списку ВАК, 4 статьи в научных периодических изданиях, 3 статьи в трудах международных научных конференций, 5 статей в трудах Всероссийских научных конференций.

Общая характеристика диссертации. Диссертация состоит из 4 разделов, содержит основной текст на 109 е., 11 иллюстраций, 17 таблиц, список использованных источников из 158 наименований.

Содержание работы

Введение содержит актуальность работы, ее цель, научную новизну, практическую значимость, а также структуру диссертации.

В первой главе дан обзор литературы по существующим методам восстановления утерянных данных.

Во второй главе рассматривается общая постановка задачи восстановления данных и описывается критерий качества восстановления.

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

Рассматривается символьная последовательность, состоящая из символов алфавита Q и L - длина участка, который необходимо восстановить (будем называть его лакуной). Полагаем, что длина лакуны L много меньше длины самой последовательности.

Определение. Словом длины д будем называть любую связную последовательность этой длины, составленную из символов алфавита П .

Определение. Опорным частотным словарём IV (д), толщины д будем называть список всех слов этой длины, встречающихся в доступных частях символьной последовательности, с указанием частот этих слов .

Определение. Под частотой слова со будем понимать

отношение

Г =

/<а N '

где Л^ - число копий слова со в исходной последовательности, N - общее число слов длины д в исходной последовательности, с учетом кратности всех слов.

Определение. Словарь IV(д) называется полным, если он содержит слова, состоящие из всех возможных сочетаний символов алфавита П. В противном случае словарь неполный.

Определение. Пополненным частотным словарём IV (<7) будем называть частотный словарь (толщины д), составленный по той последовательности, которая возникает в результате заполнения пробела.

Определение. Левой опорой длины будем называть

слово этой длины, расположенное сразу слева от лакуны.

Определение. Правой опорой длины (0<Г<^-1) будем называть слово этой длины, расположенное сразу справа от лакуны.

Тем самым, восстанавливаемая часть имеет длину Ь + И, при условии, что первые и последние t символов являются фиксированными.

Пусть имеется некоторая символьная последовательность конечной длины N. Построим частотный словарь соответствующий данной последовательности. Зафиксируем длину слова с/. Теоретически длина слова может быть любой, не превышающей длины самой последовательности. В частности, частотный словарь может состоять из одного слова, соответствующего самой последовательности. Длина слова д может выбираться исходя из специфики самой последовательности.

Возьмем первые <7 символов последовательности эта

подпоследовательность будет представлять первое слово в частотном словаре. Далее произведем сдвиг рамки считывания длиной 9 символов на один символ вправо и выпишем следующие д символов последовательности Ч', получим следующее слово и так далее. Процедура повторяется до тех пор, пока не дойдем до конца последовательности. При выписывании таких

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

Пример. Пусть Q = {a,c,g}, а Ч*= accaaacaag. Фиксируем q- 3. Выписываем из ¥ все подряд цепочки символов длины 3, получим список слов:

асс; сса; саа; ааа; аас; аса; саа; aag. Учтем число копий: С(асс) = 1; С(сса) = 1; С(саа) = 2; С(ааа) = 1; С(аас) = 1; С(аса) = 1; C(aag) = 1; Подсчитаем частоты: N = 8, f(acc) = 0.125; Цсса) = 0.125; f(caa) = 0.25; f(aaa) = 0.125; f(aac) = 0.125; f(aca) = 0.125; f(aag) = 0.125;

В результате получаем опорный частотный словарь толщины 3 для последовательности Ч* = accaaacaag.

Лакуну будем заполнять исходя из той информации, которая имеется в распоряжении. Единственная информация, которая доступна - это знание числа копий отдельных «маленьких фрагментов» имеющихся частей последовательности. Данную информацию содержит опорный частотный словарь.

Так как никакой другой информации не используется, то построение заполнения лакуны означает построение из слов длины q цепочки вида:

щ, а2, «з,..., (úL+2¡_q, со1■+2|_?+, (1)

длиной L + 2t, у которой первые t и последние t символов заданы, а для каждой пары соседних слов выполняется условие:

со;=i,co;aiq=ú>J+i; (2)

т.е. два соседних слова пересекаются по общему подслову длины q — 1, первое слово в этой цепочке начинается левой опорой a¡, а последнее

заканчивается правой опорой аг.

Если такая цепочка существует и она единственна, то задача построения заполнения решена. В общем случае число таких заполнений будет больше одного. Число всех возможных заполнений для полного

словаря №(<]) составляет Это число является верхней границей

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

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

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

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

может превышать 10 ; содержательно выровнять тысячу (и более) последовательностей едва ли возможно.

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

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

^-^{/^пЛ,} (3)

со

пополненного частотного словаря W (д), где /ш — частота слов, вычисленная по тексту, полученному в результате заполнения лакуны. Подчеркнём, что задача построения заполнения словами из опорного частотного словаря может не иметь решения. Однако вне зависимости от того, существует или нет заполнение лакуны словами из опорного словаря, можно строить заполнение лакуны всеми возможными в данном алфавите словами. Очевидно, что такое заполнение существует всегда и оно не единственно.

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

(4)

со I 3О) )

опорного частотного словаря IV(д) относительно пополненного IV (ц) достигнет максимума. Здесь /а - частота слов в опорном частотном словаре, а

- частота слов в словаре, построенном по всей последовательности, полученной в результате заполнения лакуны (пополненного); понятно, что /а = О

для некоторых со', в то время, как /а. > О .

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

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

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

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

В третьей главе рассматриваются подходы к восстановлению данных с помощью имитации кинетики химических реакций - кинетической машины Кирдина (КМК), матричного представления частотного словаря и эволюционных алгоритмов оптимизации.

Неформально КМК можно представить себе как аналог химического реактора, в котором происходят реакции. Имеется химический реактор идеального смешения, в котором плавают слова. В реактор добавляются правила - катализаторы; одни из них, взаимодействуя со словами, способствуют их

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

КМК — абстрактная модель параллельных вычислений, предложенная А.Н. Кирдиным в октябре 1997 года на конференции «Нейроинформатика и ее приложения».

Идея КМК состоит в следующем. Пусть ¿2 - алфавит символов.

П* - множество всех конечных слов или цепочек в алфавите /2 . Обрабатываемой единицей является ансамбль слов М из алфавита П, который отождествляется с функцией с конечным носителем на £2*, принимающей неотрицательные целые значения :/2* —>А'и{0}. Значение {со) интерпретируется как число экземпляров слова а в ансамбле М.

Обработка ансамблей в КМК состоит в совокупности элементарных событий, происходящих недетерминировано и параллельно. Элементарное событие 5: М -» М' состоит в том, что из ансамбля М изымается ансамбль

К' и добавляется ансамбль К+, т.е. ,= /V - .Г . Ансамбли К~

ы м к к+

и К+ однозначно задаются правилами или командами, которые объединяются в программу. Команды могут быть только трёх видов:

- Распад и ум1 и/ + g\v ;

- Синтез ик + дм> —> и.ум' ; -Прямая замена и -> и я IV .

Применительно к задаче восстановления отсутствующих данных команды КМК выглядели следующим образом. Для построения частотного словаря IVч из текста Т использовалась команда распада, работающая по следующей формуле:

где, в качестве М берется ансамбль, состоящий из одного слова Т. Верхним индексом обозначено количество символов в слове. После того, как машина остановится, ансамбль М будет содержать все слова длины д, встречающиеся в исходном тексте, с учетом их кратности.

Программа, реализующая процесс заполнения лакуны в терминах КМК выглядит следующим образом:

и/]уд'У* «/V*-1 -ЬИ-У»

(5)

а ! + а 1 V 4 ' -> а ; V 4 г + а г -» *уч~'а г

я -

ч - I *

(а)

„V?"! * + у^'у' -> НУ^'у' * + * у 9-1и' * У'У9""1^

(б)

Ы * + * V -> КУ

Первые две строчки программы осуществляют инициализацию заполнений, т.е. обеспечивают взаимодействие правой (левой, соответственно) опоры длины I с подходящим словом длины <7. Третья и четвертая строчки осуществляют рост заполнений. И, наконец, последняя строка склеивает левые и правые части. Символ < * > не принадлежит алфавиту ¿2 и используется в программе, чтобы помечать те слова, которые успешно прошли стадию инициации.

Был реализован последовательный имитатор КМК. Для повышения эффективности построения заполнений лакун в символьной последовательности последовательный имитатор КМК был модифицирован; всего было внесено три модификации:

- все заполнения росли только в одном направлении - слева направо, для определённости;

- модификации подвергся словарь, по которому строилось заполнение;

- периодически проводилась селекция всех слов, являющихся продолжениями опор.

Таким образом, алгоритм работы имитатора КМК можно представить следующим образом:

- выбор параметров имитатора - толщины словаря, количества обрабатываемых слов, количества контрольных точек (в которых проводится селекция слов);

инициализация левых опор. Формирование опорного частотного слова-

- формирование модифицированного словаря; обработка слов;

- выбор заполнений, которые удовлетворяют граничным условиям; выбор заполнения в соответствии с определённым критерием.

Следует отметить, что существует много различных способов организации вычислений, в том числе, используя языки программирования, машину Тьюринга и т.д. Однако КМК является высоко параллельным вычислительным устройством, физическая реализация которого отсутствует и в ближайшее время вряд ли появится. Поэтому в данной работе была предпринята попытка имитации работы специального вычислителя, такого как КМК применительно к задаче восстановления данных.

ря;

Далее рассматривается подход к восстановлению данных с помощью матричного представления частотного словаря. Всякий частотный словарь представляет собой (упорядоченный) список слов длины д. Такой список

можно однозначно преобразовать в матрицу А порядка Л^-1 хNq~l (N -мощность алфавита), в которой строки и столбцы помечены словами со' и со" длины q каждое. Тогда любое слово а из словаря IV(д), начинающееся последними ц - ] символами слова со' и заканчивающееся первыми д -1 символами слова со", соответствует элементу матрицы, находящемуся на пересечении данных строки и столбца; а сам этот элемент является частотой слова со .

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

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

Пусть имеется некоторый текст, состоящий из символов алфавита О = {0,1}. Пусть этому тексту соответствует опорный частотный словарь ^(д) = {00,01,10,11} и, соответственно, частоты слов равны /1,/2,/з,/4. Тогда матричное представление модифицированного словаря будет следующим:

А =

00 01 ю 11

00 Ум

10 //+/, //+/, и -

/У Л/

// и /л+л //,+/«;

а индикаторная матрица будет иметь такой вид:

00 01 10 11

00 1 1 0 0

01 0 0 1 1

10 1 1 0 0

11 0 0 1 1

Процесс построения заполнений можно представить в виде роста дерева. В корне этого дерева находится слово, совпадающее с левой опорой. Каждый узел - это слово, которое получается присоединением одного символа к слову из родительского узла. Из каждого узла выходит столько ветвей, сколько можно присоединить символов к текущему слову. Глубина такого дерева будет составлять ¿ + 1 + 1, где Ь - длина лакуны, I - длина правой опоры. Так как при построении заполнений часто возникают ситуации, когда на некотором шаге к слову нельзя присоединить ни один символ, то, соответственно, дерево может быть неполным.

Определение. Дерево, включающее в себя как ветки, которые могут дорасти до глубины Ь + 1 +1, так и ветки, которые обрываются на некотором уровне, будем называть полным деревом.

Определение. Дерево, включающее в себя только те ветки, которые достигают глубины Ь + / +1, будем называть неполным деревом.

Составим таблицу, соответствующую частотному словарю длины д. В первом столбце и первой строке таблицы расположим все слова из частотного словаря. Если последние ц -1 символов /'- ой строки совпадают с первыми -1 символами у - го столбца, то в ячейке, стоящей на пересечении этой строки и этого столбца пишем последний символ слова, расположенного в у - ом столбце. Если совпадения нет, то соответствующая ячейка будет пустой.

0} ¡V,

й>|1'2

Таблица 1. Матрица заполнений.

<РРъ

у ,<01

V, (02

V\<P^ "|9>3

Полученную матрицу будем называть матрицей заполнений. Элементами матрицы являются последовательности символов. Определим операции сложения и умножения для элементов матрицы.

Определение. Под сложением двух элементов матрицы будем понимать конкатенацию строк при помощи служебного символа, не входящего в алфавит О. Суммой двух строк «00000» и «11111» будет строка следующего вида «00000+11111», где '+' - служебный символ.

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

Например, первый множитель - строка «001+000», второй - строка «011+100». Тогда произведением этих строк является строка «001011+000011+001100+000100».

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

Утверждение. Возведение матрицы заполнений в степень I +í эквивалентно построению всех возможных заполнений из заданного опорного частотного словаря для всех возможных опор. Здесь Ь- длина лакуны, / — длина правой опоры.

Следствие. Если вместо матрицы заполнений использовать индикаторную матрицу I, то у матрицы 1!'+1 в столбце, в котором левые ц -1 символов слова совпадают с правой опорой и строке, в которой правые символов слова совпадают с левой опорой, будет стоять число всех возможных заполнений для выбранных опор, которые только можно построить из заданного опорного частотного словаря. Существование такого числа отличного от нуля, отвечает на вопрос о существовании заполнения из опорного частотного словаря как такового и говорит о числе таких заполнений.

Далее рассматривается подход к восстановлению данных с помощью генетических алгоритмов - ГА. Преимущества данного подхода перед матричным представлением и КМК заключается в том, что генетические алгоритмы существенно сужают пространство поиска и с помощью генетических операторов рекомбинации, мутации и селекции выбирают перспективные области за короткое время. Здесь речь идет именно об алгоритмах, так как, меняя хотя бы один генетический оператор, мы получаем совершенно другой алгоритм.

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

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

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

Разработан и реализован ГА применительно к задаче восстановления отсутствующих данных. Общий алгоритм, применительно к задаче восстановления данных будет следующим:

а) Инициализация начальной популяции. Генерирование символьных последовательностей длиной, равной длине лакуны L. Последовательности заполняются случайным образом символами алфавита, из которого состоит исследуемый текст;

б) Оценка начальной популяции. Считается энтропия для всех полученных текстов. Лучший индивид запоминается;

в) Селекция. Одним из методов селекции отбираются строки, которые станут родителями;

г) Скрещивание. Одним из методов скрещивания получаются два потомка. Затем они оцениваются, и выбирается лучший индивид;

д) Мутация. Все индивиды с заданной вероятностью подвергаются мутации. Затем, мутировавшие индивиды переоцениваются;

е) Формирование нового поколения. Лучший индивид запоминается;

ж) Если не выполняется критерий останова, то повторять шаги в), г),

Д), е).

В четвертой главе приводятся результаты вычислительных экспериментов. Для апробации представленных алгоритмов были реализованы последовательный имитатор КМК, матричный способ построения заполнений и генетический алгоритм. В качестве среды разработки использовались С++ Builder 6.0 и Microsoft Visual Studio 2005.

В качестве тест-объекта был взят текст генетической последовательности с кодом АВ012132 - геном вируса парагриппа человека. Длина текста составляла 14573 символа. Искусственно создавались лакуны длиной 6, 10, 20 символов. Затем с помощью вышеописанных алгоритмов строились заполнения данных лакун.

Сначала оценивалось количество возможных вариантов заполнения лакун, удовлетворяющих граничным условиям. Для выбранного текста была построена индикаторная матрица для различных толщин словаря. Для каждой лакуны и толщины словаря было определено количество заполнений, которые возможно построить по заданному опорному частотному словарю. Коли-

чество возможных заполнений для лакун длиной 10 и 20 символов представляет достаточно большую величину порядка 1012. Построить и обработать и такое количество заполнений очень сложно. Поэтому с помощью матричного представления частотного словаря были построены заполнения только для лакуны длиной 6 символов.

При использовании имитатора КМК строился опорный частотный словарь W(q) для различных значений q и по нему строились заполнения. Рассматривались заполнения с толщиной словаря от 3 до 8 символов. Число опор для каждой толщины словаря бралось равным 100000. КМК реализует гипотезу о наиболее вероятном продолжении заполнения. Именно такие заполнения доставляют меньшее значение энтропии.

При заполнении лакун с помощью генетических алгоритмов (ГА) также строился опорный частотный словарь W(q) и по нему строились заполнения. Основная сложность при использовании генетических алгоритмов

- это оптимально подобрать параметры алгоритма. Построение заполнении производилось при различных значениях параметров ГА. В качестве общих параметров использовались следующие: размер популяции - 200 индивидов, число поколений 200, использование штрафной функции - да, размер турнира

- 3 (для турнирной селекции). Так как алгоритм стохастический, то производилось не менее 5 запусков, затем выбирался лучший результат.

Сравнение результатов, полученных разными алгоритмами представлены в таблице 2.

Таблица 2. Сравнение результатов экспериментов при длине ла-_куны 6 символов и различных толщинах словаря

q Матричное представление КМК ГА

3 aaatat -5,575631539025Е-7 aaatat -5,575631539025E-7 aaatat -5,575631539025E-7

4 aaatat -2.849668656467Е-6 aaagat -2,874278297468E-6 aaatat -2,849668656467E-6

5 aaaaat -1,003320483111Е-5 aaaaat -1,003320483111E-5 aaaaat -1,003320483111E-5

6 aaaaca -4,180962370172E-5 agatat -4,24869269827E-5 aaaaca -4,180962370172E-5

Исходная часть и значение условной энтропии представлены в таблице 3.

Таблица 3.Утерянная часть длиной 6 символов и ее значения эн-

Я Исходная часть Энтропия

3 agtgca -2,158534029496Е-6

4 agtgca -9,749696922197Е-6

5 а^дса -3,332945613707Е-5

6 agtgca -1,486498956082 Е-4

Таблица 4. Сравнение результатов экспериментов при длине ла-_куны 10 и 20 символов и толщине словаря 3

КМК ГА

10 agataattat -6,304889570291Е-7 gaaatatcaa, agaaatatca. -6,280759463479Е-07

20 acatcagataatatgttgaa -1,031549682494Е-6 tatttaacaatgaaaagatc -7,892298411952Е-07

При этом для лакуны ] 0 символов исходная часть была aagcagtgca с энтропией -2,385809980663Е-6. Для лакуны 20 символов исходная часть была aagcagtgcagtcagttcag с энтропией -5,148549560011Е-6.

Матричное представление частотного словаря позволяет построить оптимальное заполнение. Как видно из результатов, таблица 2, КМК и ГА работают эффективно и построили оптимальные и близкие к оптимальным заполнения. При толщине словаря 4, КМК сработал хуже, чем ГА. Если же обратиться к таблице 4, то видно, что ГА строил заполнения эффективней, чем КМК. При этом ГА затратил на построение гораздо меньше времени - 5 мин. против 50 мин. у КМК.

Все полученные алгоритмы являются эффективными способами построения заполнений. Матричное представление используется для определения существования заполнения из опорного частотного словаря и построения заполнений для небольших лакун (до 10 символов) и словарей (до 65 слов). ГА и КМК также являются эффективными процедурами построения заполнений. КМК показал себя несколько хуже, чем ГА с точки зрения качества построения заполнений (значение энтропии) и временных затрат. Однако КМК может работать там, где не работает ГА. Для ГА затраты на вычисление целевой функции являются существенными. И там, где длина лакуны превосходит 20 символов, а мощность словаря превосходит 3000 слов, ГА не работает. Для КМК - это не критично и он может работать на лакунах длиной более 300 символов.

Настоящие алгоритмы разрабатывались для задачи восстановления отсутствующих данных в генетических последовательностях. Однако в этих алгоритмах есть одна важная особенность - они не привязаны к конкретному тексту, поскольку используют только числовые характеристики самого текста. Поэтому данные алгоритмы могут применяться не только для восстановления генетических последовательностей, но и любых других текстов тоже.

В качестве альтернативной последовательности был взят текст Всемирной декларации прав человека. Из оригинального текста декларации были удалены пробелы и знаки препинания. Для удобства рассматривали связную последовательность, что не повлияло на общность результатов. Получившаяся символьная последовательность составила около 7500 символов, длина лакуны - 100 символов. Восстановление производилось с помощью КМК. Использовались словари толщиной от 3 до 13 символов. Число левых опор для каждой толщины словаря бралось равным 100000. Число заполнений, совпавших с правой опорой составляло для всех словарей толщины д < 11 около 0,0001 %. Для словарей толщины <7 > 11, заполнений, совпавших с правой опорой, получено не было. В таблице 5 представлены значения условной энтропии для полученных заполнений при различных толщинах словаря.

Таблица 5. Значения условной энтропии для наилучшего заполнения.

Мощность алфавита

<1 32

3 -0.002501334

4 -0.004114464

5 -0.005274570

6 -0.006469274

7 -0.007102911

8 -0.006994414

9 -0.007878056

10 -0.00755565

11 -0.00835729

Ниже приведены варианты заполнений лакуны для словарей толщины ¿7 = 4, д = 6, 9 = 8 и собственно текст, который был удален из Декларации для получения лакуны; правая, а также левая опоры не показаны. После удаления знаков препинания и пробелов исходный (удаленный) текст выглядел следующим образом:

егоимуществакаждыйчеловекшеетправонасвободумыслисовестиир елигииэтопраеовключаетсвободумгнятьсвоюрел.

При восстановлении удаленного текста по словарям IV(4), IV(6), Ж(8), соответственно, были получены следующие цепочки:

- имладатъсяниисовявляющеедолжностиправонасоциальности идругиминациюкаждыйчеловекгшеетправонасторойирел

- егогражданствоиработающийимеетправонаравнуюзащитой каждыйчеловекимеетправоприниматьучаствоватьсвоюрел

- егогражданстваилитакихпосягательствкажды йчеловекимеетправо наобеспечивающихсвободуисповедоватьсвоюрел

Построение заполнений при толщине словаря шесть и более символов позволяет получить заполнения, в которых есть понятные фразы.

»48):

его гражданства или таких посягательств каждый человек имеет право на обеспечивающих свободу исповедовать свою рел

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

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

Заключение

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

В работе предложено три алгоритма восстановления утерянных данных в символьных последовательностях.

Первый - с помощью кинетической машины Кирдина. Построен имитатор КМК применительно к задаче восстановления данных. Для повышения эффективности построения заполнений в символьной последовательности имитатор КМК был модифицирован. Всего было внесено три модификации:

- все заполнения росли только в одном направлении — слева направо, для определённости;

- модификации подвергся словарь, по которому строились заполнения;

- периодически проводилась селекция всех слов, являющихся продолжениями опор;

Второй подход заключается в представлении опорного частотного словаря в виде матрицы А . Рассмотрено специальное матричное представление частотного словаря. Даны определения матрицы заполнений и индикаторной матрицы. Сформулировано и доказано утверждение о том, что возведение матрицы заполнений в степень Ь +1 эквивалентно построению всех возможных заполнений из заданного опорного частотного словаря для всех возможных опор, где Ь~ длина лакуны, ¡- длина правой опоры. Получен алгоритм построения заполнений, основанный на матричном представлении частотного словаря. Получен алгоритм, с помощью которого можно за приемлемое время ответить на вопрос о существовании заполнений из опорного частотного словаря, а также определить число таких заполнений.

Третий подход - использование генетических алгоритмов. Представлена структура ГА применительно к задаче восстановления утерянных данных.

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

Каждый алгоритм имеет свою область применения. Так имитатор КМК «хорошо» заполняет пробелы в текстах разной сложности, алфавитов различной мощности, и применим для больших лакун. Однако он не гарантирует построения оптимального заполнения. В то время как матричное представление позволяет построить все заполнения по данному словарю, но не работает на больших алфавитах и лакунах. Матричное представление лучше всего использовать для небольших (до 10 символов) лакун, когда мощность словаря не превышает 2000 слов.

ГА хорошо зарекомендовали себя при мощности словаря до 64 слов и толщине словаря 3 символа. При этом длина лакуны может достигать 50 символов.

Полученные методы зарекомендовали себя как эффективные способы восстановления утерянных или пропущенных данных в символьных последовательностях.

Публикации автора по теме диссертации

1. Рубцов А.Г., Сенашова М.Ю. Матричное представление частотного словаря для восстановления отсутствующих данных // Журнал Сибирского федерального университета. - Красноярск, серия «Математика и физика», январь 2009, том 2. №1. с. 105-115.

2. Рубцов А.Г. Восстановление отсутствующих данных и принцип максимального подобия / Рубцов А.Г., Садовский М.Г., Сенашова М.Ю. // Вычислительные технологии / Издательство СО РАН. - Новосибирск. 2008. Т. 13., 3, С. 114-127.

3. Рубцов А.Г. Кинетическая машина Кирдина и задача восстановления утерянных данных / Сенашова М.Ю., Рубцов А.Г., Садовский М.Г. // "Радюелектрошка, 1нформатика, Управлшня". - 2007. - № 1. - с. 87-93.

4. Рубцов А.Г. Кинетическая машина Кирдина в проблеме восстановления отсутствующих фрагментов символьных последовательностей. / Сенашова М.Ю., Садовский М.Г., Рубцов А.Г. // Ползуновский альманах. -Барнаул, 2006. №4. С. 59-63.

5. Рубцов А.Г. Применение генетических алгоритмов для восстановления отсутствующих данных в символьных последовательностях. / Сенашова М.Ю., Рубцов А.Г. // Ползуновский альманах. - Барнаул, 2007. №3. С. 84-87.

6. Рубцов А.Г. Восстановление отсутствующих данных в символьных последовательностях. / Рубцов А.Г., Садовский М.Г., Сенашова М.Ю. // Сборник научных трудов международной конференции «Компьютерное моделирование и интеллектуальные системы»:. - Запорожье: ЗНТУ, 2007. -206212.

7. Рубцов А.Г.Применение кинетической машины Кирдина для восстановления утерянных данных в символьных последовательностях / Сенашова М.Ю., Рубцов А.Г., Садовский М.Г. //Информационные и математические технологии в научных исследованиях / Труды XI международной конференции «Информационные и математические технологии в научных исследованиях». Часть И. - Иркутск: ИСЭМ СО РАН, 2006. - С. 168-176.

8. Рубцов А.Г. Восстановление отсутствующих данных в символьных последовательностях. Генетические алгоритмы / Сенашова М.Ю., Рубцов А.Г. // Материалы VIII международной научно-методической конферен-

ции "Информатика: проблемы, методология, технологии" (7-8 февраля 2008 г.). - Воронеж: Воронежский государственный университет, 2008. с. 232-237

9. Рубцов А.Г. Восстановление отсутствующих данных в символьных последовательностях, оценка количества заполнений /Рубцов А.Г., Садовский М.Г., Сенашова М.Ю. // Материалы IX Всероссийского семинара "Моделирование неравновесных систем-2006", 13-15 октября 2006 г. / Под ред. В.В. Слабко. Отв. за выпуск М.Ю. Сенашова, ИВМ СО РАН, Красноярск, 2006, с.145-148.

10. Рубцов А.Г. Принцип максимального подобия в проблеме восстановления утерянных данных. / Рубцов А.Г., Сенашова М.Ю., Садовский М.Г. // Нейроинформатика и ее приложения: Материалы XIV Всероссийского семинара, 6-8 октября 2006 г. / Под ред. А.Н. Горбаня, Е.М. Мирке-са. Отв. За выпуск Г.М. Садовская, ИВМ СО РАН, Красноярск, 2006, с.88-90.

11. Рубцов А.Г. Оценка количества заполнений при восстановлении отсутствующих данных / Рубцов А.Г., Садовский М.Г., Сенашова М.Ю. II Распределенные и кластерные вычисления. Избранные материалы Пятой школы-семинара. - Красноярск: Институт вычислительного моделирования СО РАН. - 2007. - С. 132-149

12. Рубцов А.Г. Восстановление отсутствующих данных. Оценка вычислительных затрат / Сенашова М.Ю., Рубцов А.Г., Садовский М.Г. // Информационные и математические технологии в науке и управлении / Труды XII Байкальской Всероссийской конференции «Информационные и математические технологии в науке и управлении». Часть II. - Иркутск: ИСЭМ СО РАН, 2007.-С. 99-106.

13. Рубцов А.Г. Генетические алгоритмы в задаче восстановления отсутствующих данных / Рубцов А.Г., Сенашова М.Ю., Садовский М.Г. // Нейроинформатика и ее приложения: Материалы XV Всероссийского семинара, 5-7 октября 2007 г. / Под ред. А.Н. Горбаня, Е.М. Миркеса. Отв. за выпуск Г.М. Садовская, ИВМ СО РАН, Красноярск, 2007, с.108-114.

14. Рубцов А.Г. Восстановление отсутствующих данных в символьных последовательностях при помощи матричного представления частотного словаря / Сенашова М.Ю., Садовский М.Г. и Рубцов А.Г.// Труды Шестой Всероссийской ФАМ'2007 конференции. Часть первая. (Под ред. Олега Воробьёва). Красноярск: ИВМ СО РАН, СФУ, КГТЭИ, СИБУП, Издательство "Гротеск", 2007, - с. 271-278

15. Рубцов А.Г. Матричное представление частотного словаря в задаче восстановления отсутствующих данных / Сенашова М.Ю., Рубцов А.Г. // Материалы V Всесибирского конгресса женщин-математиков, 15-18 января 2008 г. Красноярск: РИО СФУ, 2008, -с. 367-372

Рубцов Антон Геннадьевич Восстановление отсутствующих данных в символьных последовательностях. Автореф. дисс. на соискание учёной степени кандидата физ.-мат.

наук.

Подписано в печать 14.01.2010. Заказ №_

Формат 60x90/16. Усл. печ. л. 1.75. Тираж 100 экз.

Оглавление автор диссертации — кандидата физико-математических наук Рубцов, Антон Геннадьевич

1. Обзор методов заполнения пропусков в данных.

1.1. Статистические методы.

1.2. Методы, основанные на моделировании.

1.3. Коды обнаружения ошибок и корректирующие коды.

1.4. Выводы.

2. Постановка задачи и критерий качества заполнения.

2.1. Постановка задачи.

2.2. Критерий качества заполнения.

2.3. Выводы.

3. Кинетическая машина Кирдина, матричное представление частотного словаря и генетические алгоритмы в задаче восстановления отсутствующих данных в символьных последовательностях.

3.1. Кинетическая машина Кирдина.

3.2. Кинетическая машина Кирдина в задаче восстановления утерянных данных.

3.3. Последовательный имитатор.

3.4. Отличие КМК от случайных процессов и классических параллельных систем вычислений.

3.5. Матричное представление частотных словарей.

3.6. Построение заполнений с помощью матричного представления частотного словаря.

3.7. Генетические алгоритмы в задаче восстановления отсутствующих данных.

3.8. Выводы.

4. Программная реализация и вычислительные эксперименты.

4.1. Эксперименты.

4.2. Выводы.

Введение 2010 год, диссертация по информатике, вычислительной технике и управлению, Рубцов, Антон Геннадьевич

Актуальность темы

Подавляющее большинство методов обработки и анализа данных работают только с полными данными. На практике очень часто встречаются ситуации, когда какая-либо часть данных отсутствует. Для того чтобы иметь возможность обрабатывать такие данные, необходимо восстановить отсутствующие. Существуют различные подходы к решению этой задачи. Большинство методов позволяют получить значения пропущенных данных исходя из принципа их максимальной похожести на полные имеющиеся данные.

При проведении статистического анализа [21, 23] на практике ограничиваются анализом не всей генеральной совокупности в целом, а лишь некоторого выборочного числа наблюдений. Анализируемая выборка должна отвечать критериям качественности и полноты. Но в ситуациях, когда некоторые свойства у исследуемых объектов отсутствуют, происходит смещение основных статистических характеристик. Например, смещения математического ожидания и дисперсии возрастают прямо пропорционально числу пропусков. То есть, ошибка напрямую зависит от количества отсутствующих данных. Причинами таких пропусков могут послужить, например, отсутствие значений вследствие каких-то мелких поломок оборудования, не связанных с экспериментальным процессом, или нежелание респондента при проведении статистического опроса отвечать на вопросы о своих доходах. Знание механизма, приводящего к отсутствию значений, является ключевым при выборе методов анализа и интерпретации результатов. Неполные данные несут в себе новую информацию для исследования, важность которой может быть велика. Поэтому ее следует включать в анализ.

Практически все методы восстановления данных используют аппарат теории вероятности и математической статистики. Как правило, подобные методы восстанавливают пропущенные данные, представленные в какой-нибудь специальной форме, например, в виде таблиц. К тому же, как говорилось ранее, эти данные должны удовлетворять критериям качественности и полноты; это достаточно жесткое ограничение для практического применения. Работы, посвященные восстановлению пропущенных данных, в основной своей массе рассматривают многомерные данные [8, 16, 17, 20, 21, 23]. В этих работах данные (объекты) представляются точкой в многомерном пространстве, а параметры объекта являются координатами этой точки. При этом для восстановления пропущенных координат зачастую требуется некоторая априорная информация.

Символьные последовательности - это классические объекты математики. Они встречаются как предмет изучения во многих прикладных задачах, от теоретического программирования и теории управления до биологии и лингвистики. Изучение символьных последовательностей позволяет ответить на множество вопросов различных областей науки, связанных с чистой или прикладной математикой.

Как объект прикладного исследования, символьные последовательности встречаются во всех областях, где рассматриваются те или иные объекты, состоящие из большого числа одинаковых фрагментов. При этом схожесть или подобие могут носить искусственный характер. Исследователь вправе по своему усмотрению рассматривать некоторые фрагменты исследуемого объекта, например, нуклеотиды в молекуле нуклеиновой кислоты или символы в текстах какого-либо естественного языка, записанные в алфавитной системе записи, как тождественные друг другу, не отличающиеся ничем, кроме своего положения в рассматриваемом объекте — символьной последовательности.

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

Цель работы

Целью работы является: разработка и реализация метода восстановления отсутствующих данных в символьных последовательностях, который включает в себя три алгоритма восстановления отсутствующих данных: с использованием кинетической машины Кирдина, с использованием матричного словаря и с использованием генетических алгоритмов.

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

Научная новизна

Результаты диссертации являются новыми. В частности, разработан метод восстановления данных, который работает с символьными последовательностями, при этом их утерянные части восстанавливаются с использованием только той информации, которая содержится в самих символьных последовательностях (частотные словари). Оценка сверху числа заполнений дается выражением (N — мощность алфавита, L — длина отсутствующей части), что для алфавитов и характерных размеров пропусков, встречающихся в различных приложениях, представляет собой достаточно большую величину (порядка 1012). Таким образом, задача построения заполнения простым перебором вариантов представляется весьма ресурсоемкой. Необходим метод, снижающий вычислительные затраты. Кроме того, построение каждого из вариантов заполнений не зависит от построения других заполнений, что сделало возможным использование подходов и методов параллельных вычислений.

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

Практическая значимость

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

Апробация работы

Результаты работы были представлены на IX Всероссийском семинаре «Моделирование неравновесных систем - 2006», XI международной конференции «Информационные и математические технологии в научных исследованиях», XIV и XV Всероссийском семинаре «Нейроинформатика и ее приложения», V школе-семинаре «Распределенные и кластерные вычисления», международной конференции «Компьютерное моделирование и интеллектуальные системы», XII Байкальской Всероссийской конференции «Информационные и математические технологии в науке и управлении», VI и VII Всероссийских ФАМ конференциях. По теме диссертации опубликовано 15 работ.

Структура диссертации

Диссертация состоит из введения, четырех глав, заключения и списка цитируемой литературы из 157 наименований, содержит 11 рисунков. Общий объем диссертации составляет 109 страниц.

Заключение диссертация на тему "Восстановление отсутствующих данных в символьных последовательностях"

4.2. Выводы

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

Заключение

В работе предложено три алгоритма восстановления утерянных данных в символьных последовательностях.

- все заполнения росли только в одном направлении — слева направо, для определённости;

- модификации подвергся словарь, по которому строились заполнения;

- периодически проводилась селекция всех слов, являющихся продолжениями опор.

Второй подход заключается в представлении опорного частотного словаря в виде матрицы А. Рассмотрено специальное матричное представление частотного словаря. Даны определения матрицы заполнений и индикаторной матрицы. Сформулировано и доказано утверждение о том, что возведение матрицы заполнений в степень L + t эквивалентно построению всех возможных заполнений из заданного опорного частотного словаря для всех возможных опор, где L — длина лакуны, t— длина правой опоры. Получен алгоритм построения заполнений, основанный на матричном представлении частотного словаря. Получен алгоритм, с помощью которого можно за приемлемое время ответить на вопрос о существовании заполнений из опорного частотного словаря, а также определить число таких заполнений.

Проведены вычислительные эксперименты по заполнению лакун в символьных последовательностях. Полученные результаты показали, что каждый из предложенных методов может применяться для восстановления данных. Качество восстановления проверялось при различных значениях параметров.

Таким образом, на защиту выносятся следующие положения: Разработать метод восстановления отсутствующих данных, включающий в себя:

- метод построения заполнения; критерий качества заполнения; построение заполнений с помощью кинетической машины Кирди-на и ее частного последовательного имитатора; матричное представление частотного словаря и ответ на вопрос о существовании заполнения из опорного частотного словаря; построение заполнений с помощью генетических алгоритмов;

Исследование свойств полученных алгоритмов при решении задач восстановления.

Библиография Рубцов, Антон Геннадьевич, диссертация по теме Математическое моделирование, численные методы и комплексы программ

1. Altschul S.F., Lipman D.J. Trees, stars and multiple biological sequence alignment//SIAM J. Appl. Math. (1986), vol. 48, 603 616.

2. Ayala F.J., Kiger, Jr. J.A. Modern Genetics// The Benjamin/ Cum-mings Pbl. Co., Inc. Menlo Park, California, 1986.

3. Banzhaf W., Francone F. D., Nordin P. «The Effect of Extensive Use of the Mutation Operator on Generalization in Genetic Programming» Department of Computer Science, Dortmund University, Germany

4. Blaisdell B.E. Markov chain analysis finds a significant influence of neighboring bases on the occurrence of a base in eucariotic nuclear DNA sequences protein coding and noncoding // Mol. Evol. (1985), Vol. 21, p. 278 -288.

5. Buldyrev S.V., Goldberger A.L., Havlin S., Peng С. K., Simons M., Sciortino F., Stanley H.E. Long- range power - law correlations in DNA // Phys. Rev. Letters (1993), vol. 71, p. 1776.

6. Breen S., Waterman M.S., Zhang N. Reneval theory for several patterns// J. Appl.Prob. (1985), Vol. 22, p. 228 234.

7. Brendel V., Beckmann J.S., Trifonov E.N. Linguistics of nucleotide sequences: morphology and comparison of vocabularies // J. Biomol. Struct. Dyn. (1986), Vol. 4, p. 11 22.

8. Beckmann J.S., Brendel V., Trifonov E.N. Intervening sequences exi-bit distinct vocabulary // J. Biomol.Struct.Dyn.(1986), Vol. 4, p. 391 -400.

9. Cramer Nichael Lynn «А representation for the adaptive generation of simple sequential programs» Proceedings of an International Conference on Genetic Algorithms and Their Applications. Hillsdale, NJ: Lawrence Erlbaum Associates 1985

10. Carrillo H., Lipman D.J. The multiple sequence alignment problem in biology // SIAM J. Appl. Math. (1988), vol. 48, p. 1073 1082.

11. Dayhoff J.E. Distinguished words in data sequences: Analysis and Applications to nevral coding and other fields// Bull.Math.Biol. (1984), Vol. 46, p. 529-543.

12. Deken T.G. Some limit results for longest common subsequences// Discrete Mathematics (1979), vol. 26, №1, p. 17 31.

13. Day W.H.E., Jonson D.S., Sancoff D. The computational complexity of inferring rooted phylogenies by parsimony// Math. Biosci. 1986. - v. 81. p. 33-42.

14. Findler N.V., Van Leeuwen J. A family of similarity measures between two strings// IEEE Trans, on Pattern Analysis and Machine Inteligence, (1979), vol. PAMI 1,№1, p. 116 - 118.

15. Fitch W.M., Smith T.F. Optimal sequence alignment// Proc. Natl. Acad. Sci. USA (1983), vol. 80, p. 1382 1386.

16. Finkelstein A.V., Roytberg M.A. Computation of biopolymers: a general approach to different problems. BioSystems, 1993, vol. 30 (1 1 3). ( spec, volume «Computer genetics». P.A. Pevzner, M.S. Gelfand, eds.).

17. Goad W.B., Kanehisa M.I. Pattern recognition in nucleic acid sequences//Nucleic acid reseach (1982), vol. 10, №1.

18. Goulden I.P., Jackson D.M. An inversion theorem for claster decomposition of sequences with distinguished subsequences// J. London Math.Soc.(1979), Vol. 20, p. 567 576.

19. Guibas L.J., Odlyzko A.M. String overlaps, pattern matching and non-transitive games// J. Combinatorial Theory (ser. A). (1981), p. 183 208.

20. Gardner M. On the paradoxical situations that arise from non transitive relations// Sci. Am. (1974), vol. 231, p. 679 684.

21. Gelfand M.S., Roytberg M.A. A dynamic programming algorithm for prediction of the exon intron structure. BioSystems, 1993, vol. 30 (1 — 3). (spec, volume «Computer genetics». P.A. Pevzner, M.S. Gelfand, eds.).

22. A.N. Gorban and A.Yu. Novokhodko. Neural Networks In Transposed Regression Problem, Proc. of the World Congress on Neural Networks, Sept. 15 18, 1996, San Diego, CA, Lawrence Erlbaum Associates, 1996, pp. 515 - 522.

23. Gorban A.N., Gorbunova K.O., Wunsch D.C. Liquid Brain: Kinetic Model of Structureless Parallelism // Advances in Modelling & Anal-isis.- ASME.- 2000.-V.5, №5.

24. Gorban A.N., Gorbunova K.O., Wunsch D.C. Liquid Brain: The Proof of Algorithmic Univer sality of Quasichemical Model of Fine-Grained Parallelism // Neural Network World.- 2001.-№4.- P.391 412.

25. Gorbunova E.O., Kondratenko Yu.V., Sadovsky M.G. Data loss reparation due to indeterminate fine-grained parallel computation // ICCS, LNCS 2658, Springer-Verlag, Berlin Heidelberg, 2003.- P. 794 801.

26. Goldberg D. E. «Genetic algorithms in search, optimization, and machine learning» Reading, MA: Addison-Wesley, 1989

27. Garden P.W. Markov Analysis of Viral DNA/RNA sequences// J. Theor. Biol. (1980), Vol. 82, p. 679 684.

28. Gordon, Geoffrey, System Simulation, 2nd ed., Prentice-Hall, 1978.

29. Holland J. H. «Adaptation in natural and artificial systems» Ann Arbor: University of Michigan Press, 1975

30. Hunt J.W., Szymansky T.G. A fast algorithm for computing LCS// CASM (1977), vol. 20, №5, p. 350 353.

31. Jaap P. L. Brand. Development, implementation and evaluation of multiple imputation strategies for the statistical analysis of incomplete data // Print partners ispkamp, Enschede 1999.

32. Koza John R. «Genetic programming tutorial» URL: http://www.genetic-programming.com/gpanimatedtutorial.html

33. Koza John R. «Hierarchical genetic algorithms operating on populations of computer programs» Proceedings of the 11th International Joint Conference on Artificial Intelligence. San Mateo: Morgan Kaufman, 1989

34. Koza John R. «The Genetic Programming Paradigm: Genetically Breeding Populations of Computer Programs to Solve Problems» Cambridge, MA: MIT Press, 1992

35. Koza John R. «Genetic Programming: On Programming Computer by Means of Natural Selection and Genetics» Cambridge, MA: The MIT Press, 1992

36. Kruskal J.B. An overview of sequence comparison// Siam Review Apr. (1983), Vol. 25, №2, p. 201 237.

37. Karlin S., Ghandour G., Ost F., Tavare S., Korn L. J. New approaches for computer analysis of nucleic acid sequences// Proc. Natl. Acad. Sci. USA (1983), Vol. 80, p. 5660 5664.

38. Kingman T.F.C. Subadditive ergodic theory// The Annals of Probability (1973), vol. 1, №6, p. 883 909.

39. Luo Liaafu, Li Hong The statistical correlation of nucleotides in protein coding DNA sequences // Bull. Math. Biol. (1991), vol. 53, №3, p. 345 -353.

40. Lempel A., Ziv J. On the Complexity if Finite Sequences// IEEE Trans, on Inf. Th. (1976), Vol. IT 22, №1, p. 75 - 81.

41. Law, Averill M. "Designing and Analyzing Simulation Experiments", Industrial Engineering, March 1991, pp. 20-23.

42. McGreight E.M. A space — economical suffics tree construction al-horithm// JASM (1976), v. 23, № 2, p.262 272.

43. Mirkcs E.M., Popova T.G., Sadovsky M.G. Investigating statistical properties of genetic texts: A new approach// Advances in Modeling & Analysis, ser.B, (1993) AMSE Press. Vol. 27, №1, p. 1 17.

44. Mani G.S. Correlation between coding and non — coding regions of DNA sequences // J. Theoret. Biol. 1992. v. 158, pp. 429 -445.

45. Nemenchinskaya E.O., Kondratenko Yu.V., Sadovsky M.G. Entropy based approach to data loss reparation through the indeterminate finegrained parallel computation // Open Systems & Information Dynamics.- 2004.- V.l 1, № 2.- P.161 175.

46. Needleman S.B., Wunch S. B. A general method applicable to the search for similarities in the amino acid sequences of two proteins// J. Mol. Biol. (1970), vol. 48, p. 443 453.

47. Nakatsu N., Kambayashi Y., Yalima S. A LCS algorithm suitable for similar text strings//Acta Informatica (1982), vol. 18, Fasc. 3, p. 171 -179.

48. Neelamkavil, Francis Computer Simulation and Modeling, John Wiley & Sons, 1987.

49. Poli Riccardo «Exact Schema Theory for Genetic Programming and Variable-Length Genetic Algorithms with One-Point Crossover». — Genetic Programming and Evolvable Machines, 2, 2001.

50. Pevzner P.A., Borodovsky M.Yu., Mironov A.A. 1. The significance of deviation from mean statistical characteristics and prediction of the frequency of occurrences of words// J.Biomol. Struct.Dyn.(1989), Vol. 6, p. 1013 -1026.

51. Pevzner P.A., Borodovsky M.Yu., Mironov A.A. Linguistics of nucleotide sequences: 11. Stationary words in genetic texts and zonal structure of DNA//J. Biomol. Struct. Dyn. (1989), Vol. 6, p. 1027 -1038

52. Rossiev D.A., Savchenko A.A., Borisov A.G., Kochenov D.A. The employment of neural network classifier for diagnostics of different phases of immunodeficiency // Modeling, Measurement & Control. -1994. - V. 42. - № 2. P. 55-63.

53. Roytberg M.A. Similarity search in two biological sequences. Proceedings of the Conference «Modelling and Computer Methods in Molecular Biology and Genteics», p. 7 8, Novosibirsk, 1990.

54. Roytberg M.A. Mathematical methods of the analysis of biopolymer sequences // (S. Gindikin, ed.). AMS, 1992, Providence. P. 103 117.

55. Serre Т., Auvergne M., Goupil M. J. A new method for filling gaps in data // Astron. Astrophys. 259, p. 404 411, 1992.

56. Sellers P.H. On the theory and computation of evolutionary distances// SIAM. J. Appl. Math. (1974), vol. 26, №4, p. 787 793.

57. Sellers P.H. Pattern recognition in genetic sequences// Proc. Natl. Acal. Sci. USA (1979), vol. 76, №7, p. 3041.

58. Sankoff D., Gedergren R.J. Simultaneous comparison of three or more sequences related by a tree // Strings and macromolecules: The Theory and practice of sequence comparison. Reading, MA, Addison Wesley, (1983), p. 253-263.

59. Steele J. M. Long common subsequences and the proximity of two random strings// SIAM J. Appl. Math. (1982), vol. 10, №1, p. 731 737.

60. Shannon, Robert E., System Simulation: The Art and Science, Prentice-Hall, 1975.

61. Schlesinger, S., "Terminology for Model Credibility", Simulation, 32(3), 1979, pp. 103-104.

62. Takens F. Detecting Strange Attractors in Fluid Turbulence // Dynamical System and Turbulence, Springer Lecture Notes in Mathematics 898, Berlin, p. 366,1981

63. Trifonov E.N., Brendel V. GNOMIC: a dictionary of the genetic code// Philadelphia: Balaban Publishing., 1986, 272 p.

64. Thesen, Arne and Laurel E. Travis, Simulation For Decision Making, West Publishing Company, 1992.

65. Ukkonen E. An approximate string matching// Lect. Notes in Comput. Sci. (1983), №158, p. 487 495.

66. Weiner P. Lenear pattern matching algorithms// Conf. Record, IEEE 14th Annual Symposium on Switching and Automata Theory (1973), p. 1 -11.

67. Waterman M.S. General methods of sequence comparison// Bull. Math. Biol. (1984), Vol. 46, p. 474 500.

68. Waterman M.S., Perlwits M.D. Line geometries for sequence comparison// Bull. Math. Biol. (1984), vol. 46, p. 576 577.

69. Waterman M.S., Smith Т.Е., Beyer W.A. Some biological sequence ma-trics// Advances in mathematics (1976), №20, p. 367 387.

70. Wong C.K., Chandra A.K. Bound for the string correction problem// J. ASM. (1976), vol. 23, №1, p. 13 16.

71. Wagner B.M., Fisher M.J. The string to - string correction problem// J. ASM. (1974), vol. 21, №1, p. 168 - 173.

72. Zharkikh A.A., Rzhetsky Yu. I. Quick assessment of similarity of two sequences by comparison of their 1 — tuple frequencies//Biosystems, (1993), vol. 30, p. 93-111.

73. Александров А.А., Александров H.H., Бородовский М.Ю. и др. М.: Наука, 1990. 267 с.

74. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов/ — М.: Мир, 1979.

75. Айзенберг JI.A. Фомулы Карлемана в комплексном анализе. Перые приложения. Новосибирск: Наука, 1990. 248 с.

76. Бахмутова И.В., Гусев В.Д., Зарипов Р.Х., Титкова Т.Н. Выявление и анализ сходных фрагментов в музыкальных произведениях// В кн. Анализ символьных последовательностей (Вычислительные системы, вып. 113). Новосибирск, 1985, с. 3 - 45.

77. Бородовский М.Ю., Сприжицкий Ю.А., Голованов Е.И., Александров А.А. Статистические закономерности в первичных структурах функциональных областей генома Е. coli. 11. Неоднородные марковские модели// Молекуляр. Биология (1986), т. 20, с. 1024 1033.

78. Волькенштейн М.В. Энтропия и информация. М.: Наука, 1986. — с. 192

79. Гусев В.Д. Сложностные профили символьных последовательностей// В кн. Методы обработки символьных последовательностей и сигналов (Вычислительные системы, вып. 132). Новосибирск, 1989, с. 35-63.

80. Гусев В.Д. Характеристики символьных последовательностей// В кн. Проблемы обработки информации (Вычислительные системы, вып. 88). Новосибирск, 1981, с. 112 - 123.

81. Гусев В.Д., Куличков В.А., Титкова Т.Н. Анализ генетических текстов. 1.1- граммные характеристики// Эмпирическое предсказание и распознавание образов (Выч. системы, вып. 83). Новосибирск, Ин -т математики СО АН СССР. 1980. c.l 1 33.

82. Гусев В.Д. Механизмы обнаружения структурных закономерностей в символьных последовательностях// В кн. Проблемы обработки информации (Вычислительные системы, вып. 100). Новосибирск, 1983, с. 47-66.

83. Галягин Д.К., Фрик П.Г. Адаптивные вейвлеты (алгоритм спектрального анализа сигналов)

84. Гросберг А.Ю., Рабин И., Хавлин Ш., Нир А. Самоподобие в структуре ДНК: зачем нужны интроны? // Биофизика (1993), т. 38, 1, с. 75 -83.

85. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация, М.: Мир, 1985.-509с.

86. Горбань А.Н., Миркес Е.М., Свитин А.П. Полуэмпирический метод классификации атомов и интерполяции их свойств // Математическое моделирование в биологии и химии. Новые подходы. Новосибирск: Наука. Сиб. отделение, 1992.-е. 204-220.

87. Горбань А.Н. Обход равновесия Новосибирск: Наука, 1984. 236 с.

88. Горбань А.Н., Миркес Е.М., Свитин А.П. Метод мультиплетных покрытий и его использование для предсказания свойств атомов и молекул // Журнал физической химии.-1992.-Е.66, №6. с. 1503 -1510.

89. Горбань А.Н., Россиев A.A., Wunsch 2 D.C. Самоорганизующиеся кривые и нейросетевое моделирование данных с пробелами // сб. Нейроинформатика 2000, научная сессия МИФИ, 4.1, М., с. 40-45, 2000.

90. Горбань А.Н., Россиев Д.А. Нейронные сети на персональном компьютере. Новосибириск: Наука, 1996. 256 с.

91. Горбань А.Н., Попова Т.Г., Садовский М.Г. Классификация нуклео-тидных последовательностей по частотным словарям обнаруживаетсвязь между их структурой и таксономическим положением организмов// ЖОБ. 2003. Т. 64, №1. С. 51 63.

92. Горбань А.Н. Проблема скрытых параметров и задачи транспонированной регрессии // V Всеросс. семинар "Нейроинформатика и ее приложения": Тез.докл-Красноярск, 1997.-С. 15-16.

93. Горбань А.Н., Миркес Е.М., Попова Т.Г., Садовский М.Г. «Новый подход к изучению статистических свойств генетических последовательностей»/ Биофизика (1993), т. 38, вып. 5.-е. 762 767.

94. Горбань А.Н., Миркес Е.М., Попова Т.Г., Садовский М.Г. «Сравнительная избыточность генов некоторых организмов и вирусов»/ Генетика (1993), т. 29, № 11, с. 1413 1419.

95. Горбань А.Н., Попова Т.Г., Садовский М.Г. Избыточность генетических последовательностей и мозаичная структура генома//Мол. биол. (1994), т.28, вып. 2. с. 313 -324.

96. Георгиев Г.П. Гены высших организмов и их экспрессия. М.: Наука, 1989.-255 с.

97. Горбунова Е.О. Формально-кинетическая модель бесструктурного мелкозернистого параллелизма // Сиб. журн. вычисл. математики1999. Т.2, № з. С.239-256.

98. Гантмахер Ф.Р., Теория матриц, «Наука», 1967.

99. Ильин В.А., Позняк Э.Г. Линейная алгебра М: наука, физматлит, 1999.

100. Ефимов Н.В., Высшая геометрия, Физматгиз, 1961.

101. Зубков A.M., Михайлов В.Г., Предельные распределения случайных величин, связанных с длинными повторениями в последовательности независимых испытаний// Теория вероятностей и ее применение (1974), т. XIX, №1, с. 173 181.

102. Загоруйко Н.Г. Методы распознавания и их применение. Изд. Сов. Радио, М., 1972.

103. Загоруйко Н.Г., Елкина В.Н. Блок анализа данных в экспертной системе ЭКСНА. //Экспертные системы и анализ данных. Новосибирск, 1991, - Вычислительные системы: Вып. 144 - с. 57 - 175.

104. Загоруйко Н.Г., ЁлкинаВ.Н., Тимеркаев B.C. Алгоритм заполнения пропусков в эмпирических таблицах (алгоритм "ZET") // Вычислительные системы. Новосибирск, 1975. - Вып. 61. Эмпирическое предсказание и распознавание образов. - С. 3-27.

105. Злоба Е., Яцкив И. Статистические методы восстановления пропущенных данных. // Компьютерные модели и новые технологии-2002.- Т. 6, №.1.-С. 51-61.

106. Капитонов В.В., Титов И.И. Порядок расположения интронов и дальние корреляции в нуклеотидных последовательностях// ДАН (1994), т. 337, №6. с. 810 812.

107. Королев С.В., Соловьев В.В., Туманян В.Г. Новый метод поиска функциональных участков ДНК с использованием фрактального представления нуклеотидных текстов// Биофизика (1992), т. 37, вып. 5, с. 837-847.

108. Кирдин А.Н. Идеальная ансамблевая модель параллельных вычислений // Нейроинформатика и ее приложения. Тезисы докладов V Всеросс. семинара. Красноярск, КГТУ, 1997. С. 101.

109. Курош А.Г., Курс высшей алгебры, «Наука», 1970.

110. Колчанов Н.А., Соловьев В.В. Построение филогенетических деревьев по корреляциям в нуклеотидных последовательностях// ИНТ сер. Моле. биол. т. 21. М.: ВИНИТИ, 1985. 80 122.

111. Литтл Р.Дж.А., Рубин Д.Б. Статистический анализ данных с пропусками-М.: Финансы и статистика, 1991.

112. Ленг С., Алгебра, «Мир», 1968.

113. Левенштейн В.И. двоичные коды с исправлением выпадений, вставок и замещений символов// ДАН СССР. (1965), т. 163, №4, с. 845 -848.

114. Д.С. Лебедев, В.А. Гармаш. О возможности увеличения скорости передачи телеграфных сообщений. — М.: Электросвязь, 1958, №1 с. 68-69

115. Неменчинская Е.О., Кондратенко Ю.В., Садовский М.Г. Предварительные результаты в проблеме восстановления утерянных данных с помощью кинетической машины Кирдина // Вычислительные технологии.- 2004.- Т.9, № 1.- С.42 57.

116. Немытикова Л.А. Методы сравнения символьных последовательностей// В кн. Методы обработки символьных последовательностей и сигналов (Вычислительные системы, вып. 132). Новосибирск, 1989, с. 3-34.

117. Пасеков В.П. Генетические расстояния // Итоги науки и техники, сер. Общая генетика, т. 8 М.: ВИНИТИ, 1981. с. 3 - 75.

118. Попова Т.Г., Садовский М.Г. Точная мера избыточности генетических текстов / Экоген, вып. 2, изд во ТГУ, 1992, с. 9.

119. Россиев А.А. Моделирование данных при помощи кривых для восстановления пробелов в таблицах// Методы нейроинформатики, Сб. науч. Трудов, с 6-22, Красноярск, 1998.

120. Становление химии как науки. Всеобщая история химии / Под ред. Ю.И. Соловьева. -М.: Наука, 1983.-464 с.

121. Свойства элементов. В 2 х частях. Ч. 1. Физические свойства. Справочник. - М.: Метуллургия, 1976. - 600 с.

122. Садовский М.Г. Об информационной емкости символьных последовательностей. Выч. Технологии, 10 , № 4, 2005, 82 89.

123. Садовский М.Г. О сравнении символьных последовательностей. Выч. Технологии, 10, № 3, 2005, 108 116.

124. Семенкин Е.С., Семенкина О.Э., Коробейников С.П. «Оптимизация технических систем» Учебное пособие. Красноярск: СИБУП, 1996

125. Соловьев В.В., Колчанов Н.А. Компьютерный анализ статистических характеристик нуклеотидных последовательностей // ИНТ сер. Молек. Биол. т. 21. М.: ВИНИТИ, 1985. с. 38 80.

126. Стратонович P.JI. Теория информации. М.: «Советское радио». -1975.

127. Физико химические свойства элементов. - Киев: Наукова думка. 1965-808 с.

128. Фоменко А.Т. Методика распознавания дубликатов и некоторые приложения// ДАН СССР (1981), т. 258, №6, с. 1326 1330.

129. Цымбал В.П. Теория информации и кодирование. К.: Высшая Шлола, 1977 г. - с. 288

130. Чупахина О.М. Сложностный анализ генетических текстов/ Авто-реф. .канд. Техн. Наук, Новосибирск, НИОХ, 1993, 18 с.

131. Шеннон К. Работы по теории информации и кибернетике. М. : Изд. иностр. лит., 1963. с.830

132. Эфрон Б. (1988) Нетрадиционные методы многомерного статистического анализа. Финансы и статистика, Москва.

133. Яблонский Г.С., Быков В.И., Горбань А.Н. Кинетические модели каталитических реакций. — Новосибирск: Наука, 1983. 253 с.

134. Яблоков А.В., Юсуфов А.Г. Эволюционное учение/ М.: Высшая школа, 1989. 335 с.142. http://www.ebi.ac.uk/genomes143. http://www.un.org

135. Рубцов А.Г., Садовский М.Г., Сенашова М.Ю. Восстановление отсутствующих данных в символьных последовательностях. // Компьютерное моделирование и интеллектуальные системы: Сборник научных трудов. Запорожье: ЗНТУ, 2007. -206-212.

136. Сенашова М.Ю., Садовский М.Г., Рубцов А.Г. Кинетическая машина Кирдина в проблеме восстановления отсутствующих фрагментов символьных последовательностей. // Ползуновский альманах. Барнаул, 2006. №4. С. 59-63.

137. Рубцов А.Г., Садовский М.Г., Сенашова М.Ю. Восстановление отсутствующих данных и принцип максимального подобия // Вычислительные технологии / Издательство СО РАН. Новосибирск. 2008. Т. 13., 3, С. 114-127.

138. Сенашова М.Ю., Рубцов А.Г., Садовский М.Г. Кинетическая машина Кирдина и задача восстановления утерянных данных // "Радюелектрошка, 1нформатика, Управлшня". 2007. - № 1.-е. 87-93.

139. Сенашова М.Ю., Рубцов А.Г. Применение генетических алгоритмов для восстановления отсутствующих данных в символьных последовательностях. // Ползуновский альманах. Барнаул, 2007. №3. С. 84-87.

140. Сенашова М.Ю., Рубцов А.Г. Матричное представление частотного словаря в задаче восстановления отсутствующих данных. Матерлалы V Всесибирского конгресса женщин-математиков, 15-18 января 2008 г. Красноярск: РИО СФУ, 2008, -с. 367-372

141. Рубцов А.Г., Сенашова М.Ю. Матричное представление частотного словаря для восстановления отсутствующих данных // Журнал Сибирского федерального университета. Красноярск, серия «Математика и физика», январь 2009, том 2. №1. с. 105-115.

Похожие работы

Информатика, вычислительная техника и управление
05.13.00