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

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

Панин Александр Геннадьевич

О НЕКОТОРЫХ АЛГОРИТМАХ РАБОТЫ С ДЛИННЫМИ СТРОКАМИ И ИХ ПРИМЕНЕНИИ В ЗАДАЧАХ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ

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

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук

1 О НОЯ 2011

Тольятти - 2011

4859431

Работа выполнена в Тольяттинском государственном университете.

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

доктор физико-математических наук, профессор Мельников Борис Феликсович

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

доцент Сафронов Александр Иванович

кандидат физико-математических наук, доцент Кондратьев Алексей Евгеньевич

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

Самарский государственный университет

Защита диссертации состоится «1» декабря 2011 года в 13:00 часов на заседании диссертационного совета Д212.264.03 при Тольяттинском государственном университете по адресу: 445667, Тольятти, ул. Белорусская, 14. С. диссертацией можно ознакомиться в библиотеке Тольятгинского государственного университета, с авторефератом - на сайте диссертационного совета http://edu.tltsu.ru/sites/site.php?s=14 96. Отзывы по данной работе в двух экземплярах, заверенные печатью организации, просим направлять по адресу: 445667, Тольятти, ул. Белорусская, 14, ТГУ, диссертационный совет Д212.264.03.

Автореферат разослан «31» октября 2011 года

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

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

к.п.н., доцент

Пивнева С.В.

1. ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы

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

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

1 Д.Кнуг. Искусство прсц-раммирования, т.2. Получисленные алгоритмы. - Москва: Вильяме, 2007. -832 с. (Страницы 425-468.) Субэкспоненциальную сложность имеет, например, алгоритм Диксона - а

О /"е2>/2,/)(« N,/108 1о| сЛ

именно, V ) , где N - число, которое требуется разложить на множители.

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

2

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

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

2 Б.Мельников. Мультиэвристический подход к задачам дискретной оптимизации // Кибернетика и системный анализ (HAH Украины), 2006, №3. С.32-42.

См. работы автора, приведённые ниже в списке его публикаций, а также следующие публикации:

• А.Белозёрова, БМельников. Применение комплекса эвристик в задаче составления схемы нук-лидных превращений // Сборник трудов Второй Всероссийской научной конф. «Методы и средства обработки информации», Москва, изд-во МГУ им М.В.Ломоносова, 2005. С.208-214;

• А.Белозёрова, Г.Шиманский. Оптимизация схемы расчёта трансмутации методом ветвей и границ // Труды семинара «Физ. моделирование изменения свойств реакторных материалов в номинальных и аварийных условиях», Димитровград, изд-во ФГУП ГНЦ РФ НИИАР, 2005. С.75-77;

• BMelnikov, A.Radionov, V.Gumayunov. Some special heuristics for discrete optimization problems // 8th Int. Conf. on Enterprise of Information Systems (ICEIS-2006), Pathos (Cyprus) 91-95;

• М.Алёхина, АЛысенко, Б.Мельников. Об одном подходе к моделированию вычислительных устройств. // Известия вузов. Поволжский регион. Физико-математические науки. No.2,2007. С.2-9;

• БМельников, Е.Мельникова. Кластеризация ситуаций и принятие решений в задачах дискретной оптимизации. // Известия вузов. Поволжский регион. Технические науки. № 2,2008. С.23-28;

• С.Баумгертнер, Б.Мельников. Мультиэвристический подход к проблеме звёздно-высотной минимизации недетерминированных конечных автоматов // Вестник Воронежского гос. унив., сер. Сист. анализ и инф. техн., 2010, № 1, С.5-7;

• БМельников, С.Эйрих. Подход к комбинированию незавершённого метода ветвей и границ и алгоритма имитационной нормализации // Вестник Воронежского гос. ун-та, сер. Сист. анализ и инф. техн., 2010, № 1, С.35-38.

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

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

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

Цель работы

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

3 А.Аграновский, Д.Леднов. Теоретические аспекты алгоритмов обработки и классификации речевых сигналов - Москва: Радио и связь, 2004. - 164 с.

4 А.Шевченко. Скважинная сейсморазведка. - Москва: Изд-во Российского государственного университета нефти и газа им. Губкина, 2002. - 129 с.

5 Ю.Сато. Обработка сигналов. Первое знакомство. - Москва: Додека, 2000. - 175 с.

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

Основные задачи исследования:

1. Разработка - на основе мультиэвристического подхода к задачам дискретной оптимизации - оригинальной метрики на множествахспециальным образом описанных дискретных сигналов.

2. Разработка и реализация алгоритма кластеризации сигналов акустической эмиссии на основе разработанной метрики.

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

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

5. Разработка и реализация оригинального алгоритма сравнения эффективности (качества) эвристических алгоритмов.

6 Е.Мельникова. Применение кластеризации ситуаций в эвристических алгоритмах для задач дискретной оптимизации: дисс. ... :канд. физ.-мат. наук : 05.13.18 // Тольятти, ТГУ, 2009. - 152 с. См. также соответствующие ссылки, приведённые в указанной диссертации.

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

Объект исследования

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

Предметом исследования являются алгоритмы работы со строками. Методы исследования

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

Результаты исследования

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

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

Разработанные алгоритмы решения рассматриваемых задач являются новыми. Мультиэвристический подход впервые был применён для сравнения сигналов и строк.

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

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

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

Основные положения, выносимые на защиту:

1. Алгоритм кластеризации сигналов акустической эмиссии.

2. Алгоритм сравнения генетических последовательностей, основанный на мультиэвристическом подходе.

3. Алгоритм точного поиска наибольшей общей подпоследовательности.

4. Алгоритм приближённого поиска наибольшей общей подпоследовательности.

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

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

Результаты диссертационной работы докладывались и обсуждались на:

1) VII Всероссийской научно-технической конференции «Проблемы информатики в образовании, управлении, экономике и технике», Пенза, 2007;

2) 3-й Международной научно-практической конференции студентов и преподавателей «Информационные технологии в современной жизни», Бонн (Санкт-Августин), Германия, 2008;

3) конференции «Технологии искусственного интеллекта в экономике», Москва-Дубна, 2008;

4) VII Всероссийской межвузовской конференции молодых учёных, Санкт-Петербург, 2010;

5) Международной конференции «Современные проблемы математики, информатики и биоинформатики», Академгородок, Новосибирск, 2011;

6) Международной научно-практической конференции «Молодёжь и наука: модернизация и инновационное развитие страны», Пенза, 2011.

Публикации

По теме диссертации опубликовано 8 работ в рецензируемых научных

журналах и изданиях, из них 2 - в изданиях, рекомендованных ВАК.

Личный вклад автора

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

Структура и объём диссертации

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

2. КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

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

Подпоследовательность можно получить из некоторой конечной строки, если удалить из последней некоторое множество её символов (возможно, пустое). Общая подпоследовательность двух строк - это строка, являющаяся подпоследовательностью каждой из них. Самая длинная из таких строк называется наибольшей общей подпоследовательностью (les - longest common subsequence). Заметим, что lcs может быть несколько.

Редакционное расстояние (расстояние Лёвенштейна) между двумя стро-

ками определяется как минимальное число редакционных операций - вставок, удалений и замен, необходимое для преобразования первой строки во вторую. Например, для того, чтобы из строки «кот» получить строку «скат» нужно: вставить в неё символ «с»; заменить символ «о» на символ «а». Таким образом - поскольку за одну операцию подобное преобразование невозможно, - редакционное расстояние между этими строками равно 2.

В третьей главе описан метод кластеризации сигналов акустической

7 8

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

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

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

Вейвлет-преобразование на первом этапе осуществляется на графическом процессоре с использованием фильтров семейства Добеши9.

На втором этапе все сигналы сравниваются попарно, строится матрица расстояний между ними, после чего получившиеся значения приводятся к интервалу [0; 100] и возводятся в некоторую степень для более чёткого разделе-

7 P.Adrian. Acoustic Emission Inspection // Metals Handbook, Ninth Edition ASM International. Vol. 17. 1989. -P.278-294.

8 ГОСТ 27655-88. Акустическая эмиссия. Термины, определения и обозначения. - М.: Изд-во стандартов, 1988. - 29 с.

9 И.Добеши. Десять лекций по вейвлетам. - Ижевск: Издательство НИЦ «Регулярная и хаотическая динамика», 2001. - 464 с.

ния на кластеры.

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

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

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

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

На третьем этапе осуществляется нечёткая кластеризация.

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

автором был реализован и метод Брента10 (метод главных направлений). Это

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

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

Функция корреляцииДх, у) для сигналовхиу определяется по формуле

где а(х;, у,) - угол между касательными к функциям сигналов в точке, соответствующей г'-му отсчёту,

dt - квант времени.

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

Для кластеризации на основе параметров акустической эмиссии были выбраны следующие параметры:

• число, частота и энергия импульсов АЭ, превышающих пороговый уро-

10 R.Brent. Algorithms for Minimization without Derivatives, Chapter 4. // Prentice-Hall, Englewood Cliffs,

bx. =Xi- Xi_lt byi = y, - yt.u aXt = dyi = dt,

NJ, 1973.

вень, за единицу времени; • число, частота и энергия всех импульсов АЭ за единицу времени. Для всех параметров используются весовые коэффициенты, которые настраивались с помощью генетического алгоритма.

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

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

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

Вход: Строки х и у.

Шаг1: /" := 0, j := 0, г := 0;

Шаг 2: if x[i] = y[j] then begin

сдвигаем обе строки;

г : = г + стоимость совпадения символов x[i] и y[j]',

" D.Merson, S.Dement'ev, A.Ioffe, P.Suvorov, A.Vinogradov. Acoustic Emission during Hydrogen Charging of a Pipeline Steel // ISU International, Vol. 51 (2011), No. 10. - The Iron and Steel Institute of Japan, 2011 -pp.1682-1687.

См. так же другие публикации А. Виноградова.

end

else begin

применяем эвристики для генерации возможных «траекторий» сдвига в позиции /' и ]' таких, что х[1'] = YÜT,

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

осуществляем сдвиг (при этом может измениться значение г);

end;

Шаг 3: повторяем второй шаг до тех пор, пока не достигнут конец одной из строк.

В алгоритме были использованы следующие эвристики.

1. Выбираем траектории, для которых выражение (f - i) + (/' - j) принимает минимальное, либо близкое к минимальному значение. Например, сначала рассматриваем все траектории со сдвигом только одной из строк на 1 символ; затем - со сдвигом одной из строк на 2 символа или обеих строк на 1 символ, и т.д.

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

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

4. Второй способ оценки: используем степень сходства строк x[Li'J и y[j..f], полученную, например, с помощью алгоритма Ниддмана-Вунша12. В этом

12 S.Needleman, C.Wunsch. A general method applicable to the search for similarities in the amino acid sequence of two proteins // Journal of Molecular Biology, 1970,48 (3): 443-453.

случае предпочтительными являются траектории с наименьшей степенью сходства соответствующих подстрок. 5. Используем какой-либо алгоритм для поиска наибольшей общей подпоследовательности строк x[i..i+k] и y[j..j+k], где, на основе эмпирических запусков соответствующих программ, выбиралось fc - 15. Для сдвига выбираем такие индексы i',j', в которых заканчивается наибольшая общая подпоследовательность. Если не будет найдено ни одной пары одинаковых символов, область поиска увеличивается. При использовании этой эвристики результат будет близок к значению наибольшей общей подпоследовательности.

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

Пятая глава посвящена алгоритму поиска наибольшей общей подпоследовательности. Он построен на основе метода динамического программирования, работает за время Ofstl-f/n2)), где s - количество пар (i, j), таких, что х, = yj, п - длина строк х и у, г- длина les. Сложность по памяти составляет О(п). Он так же имеет сходство с алгоритмом Ханта-Шиманского14. В работе приведено сравнение сложности данных алгоритмов в различных областях пространства параметров (г, s).

Решаемая задача состоит в том, чтобы для данных строк хиу (1x1, 1>'1 > 0) найти \lcs(x,y)\, где lcs(x,y) - одна из наибольших общих подпоследовательностей. Как правило, требуется найти не только длину lcs(x,y), но и саму эту по-

" A.Shipunov. Systema Naturae or the outline of living world classification // Protistology. 2009.6 (1): 3-13

14 J.Hunt, T.Szymanski.. A fast algorithm for computing longest common subsequences // Communications of the ACM, Vol. 20, No. 5, p. 350-3, May 1977.

следовательность.

Самым простым является метод вычисления расстояния между двумя строками, основанный на методе динамического программирования15. Он был открыт независимо несколькими исследователями16. Суть метода заключается в следующем. Пусть хяу — две строки (для простоты изложения будем считать, что длины обеих строк совпадают и равны и) над некоторым алфавитом, тогда длину наибольшей общей подпоследовательности можно подсчитать по рекуррентной формуле \1с5(х, >>)!= Б(п, п), где

При этом промежуточные результаты можно хранить в матрице а[(п+1)х(п+1)], по которой впоследствии вычисляется само значение les. Очевидно, что такой алгоритм работает за время 0(п2) и требует 0(п2) памяти.

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

1. Изменение порядка перебора ячеек матрицы.

Эта модификация позволяет уменьшить количество перебираемых элементов и использовать ещё одну модификацию, связанную с массивами длин

15 R.Bellman, S.Dreyfus. Applied Dynamic Programming // Princeton University Press, Princeton NJ, 1962.

16 G.Stephen. String Search Algorithms // World Scientific, 1994. - 256 p.

17 Несмотря на то, что на самом деле её значения не хранятся и даже не вычисляются, для наглядного описания работы алгоритма удобно иногда «забывать» об этом. Кроме того, эту модификацию можно использовать отдельно от других.

"О,

D(i,j) = J D(i-1, j-1) + 1,

max(D(i-l, j), D(i, j-1)),

если i = 0 или j = 0 если Xi = y>j если Xi Ф yj

префиксов. Кроме того, появляется возможность достаточно точно прогнозировать длину les18. Порядок перебора изменяется следующим образом: в основном цикле перебираем числа от 0 до п. На каждой к-й итерации происходит перебор элементов а[к, 0] - а[к, к-1 ], а[0, к] - а[к, к]. Т.е. сначала - по fc-й строке, затем -по к-жу столбцу. Полученная таким образом матрица совпадает с матрицей, полученной перебором элементов построчно.

Количество перебираемых элементов можно уменьшить на величину, пропорциональную lies!, - за счёт того, что при таком способе обхода матрицы можно игнорировать элементы, для которых выполняется условие (i > j + г) II (j > i + г) (где г - длина les), то есть элементы, лежащие в левом нижнем и правом верхнем углах. В итоге для двух одинаковых строк будет пройдена только диагональ матрицы - всего п элементов. Конечно, значение г становится известно только после завершения алгоритма, поэтому граница определяется исходя из текущего значения llcsl. Однако это не приводит к существенному уменьшению числа игнорируемых элементов.

2.Исполъзование массивов длин префиксов.

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

Также ранее было сказано, что для определения значения D[i, j] нам надо знать наибольшее значение среди элементов, лежащих выше и левее D[i, j]. Если мы перебираем элементы к-й строки, то все интересующие нас элементы гарантированно лежат выше текущего - поэтому нам нужно найти наибольший среди элементов, лежащих левее текущего. Это нетрудно сделать по одному из

18 Приближённое значение llcsl можно вычислять по формуле rt*n/k, где к - номер итерации, а гк-значение llcsl префиксов строк хну длины к.

массивов длин префиксов - а именно, нужно найти в нём элемент с наибольшим индексом, для которого записанный в нём номер столбца меньше текущего. Индекс этого элемента будет значением наибольшего элемента матрицы среди тех, чтолежат выше и левее текущего (это было бы значение элемента В[ 1-1, ]-1 ], если бы мы хранили в памяти всю матрицу Б). Прибавив к найденному числу единицу, мы получим значение элемента О/г, //. После этого нужно обновить значение элемента массива префиксов, индексом которого является значение }]. Если такой элемент есть и его значение больше номера текущего столбца матрицы И, нужно записать в него номер текущего столбца. Если нет, то нужно добавить новые элементы в оба массива длин префиксов; в них записываются текущие номера строки и столбца соответственно. Перебор элементов столбца осуществляется аналогичным образом, при этом используется другой массив длин префиксов.

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

3. Использование списков вхождения символов.

Для поиска очередной пары индексов I и./, при которых соответствующие элементы и у} равны, можно использовать списки вхождения каждого символа алфавита в строки х и у. Например, для каждого значения к можно получить такие индексы ], что 0 < ] < к и хк = перебирая список вхождений символа хк в строку у. Это позволяет многократно сократить количество сравнений. Списки позиций вхождения символов в строки можно строить либо в процессе работы алгоритма, либо заранее. Кроме того, теперь на каждой к-й итерации основного цикла необходимо знать только по одному символу строк х и у, благодаря чему задача решается за один проход по обеим строкам.

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

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

Ещё одной особенностью описанного алгоритма является то, что в каждый определённый момент работы он имеет лучшее на данный момент решение, и, следовательно, является anytime-алгоритмом19. При этом точность наибольшей общей подпоследовательности линейно зависит от количества прошедших итераций основного цикла алгоритма, и поэтому для её длины можно сделать приемлемый прогноз уже по прошествии 1-10% времени общей работы алгоритма. Оценки этого общего времени работы алгоритма могут быть проведены согласно вышеописанным эвристикам.

Ниже представлен псевдокод, иллюстрирующий работу алгоритма.

FastLCS(x, у, п) for к <- 0 to n do

if х[к] = у[к] then

UpdateXSuffixLen(k, к); border := max(lcslen - (к - Icslen + 1), Icslen + к - n, 0) for i in XMatchUst[y[k]] and i > border do

UpdateXSuffixLen(i, k); for j in YMatchList[x[k]] and j > border do UpdateYSuffixLen(k, j);

XMatchlJst[x[k]].Add(k); YMatchList[y[k]] .Add(k) ; return |XSuffixLen|;

UpdateXSuffixLen(i, j) value := Icslen + 1;

" Б.Мельников. Мультиэвристический подход к задачам дискретной оптимизации // Кибернетика и системный анализ (HAH Украины), 2006, №3. С.32-42. В качестве русского термина, соответствующего английскому "anytime algorithm", можно употреблять «алгоритм с отсечением по времени» (см. Большой англо-русский и русско-английский словарь, 2001) - но термин "anytime algorithm" автор считает более предпочтительным. См. так же сноску 2 в указанной статье.

while XSuffixLenfvalue] > i do

value—; if value = Iscien + 1 then XSuffixLen.Add(i); YSuffixLen.Add(j);

else

if XSuffixLenfvalue] > i then XSuffixLenfvalue] = i;

return;

UpdateYSuffixLen(i, j) value := Icslen + 1; while YSuffixLen[value] > j do

value—; if value = Iscien + 1 then XSuffixLen.Add(i); YSufflxLenAdd(j);

else

if YSuffixLen[value] > j then YSuffixLenfvalue] = j;

return;

Тестирование алгоритма.

В первом тесте на вход подавались случайные строки с равновероятным появлением всех символов алфавита, состоящего из 127 символов. Кривая, соответствующая алгоритму Хиршберга, обозначена цифрой 3, алгоритму Ханта-Шиманского - цифрой 2, точному алгоритму, описанному в данной главе -цифрой 1.

Длина строк, тысячи символов

Рис. 1. Зависимость времени работы (в секундах) от длины строк (в тысячах символов), размер алфавита - 127 символов.

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

Тестирование точности прогноза производилось на фрагментах ДНК длиной 10000 символов20.

0,016 п 0.014

g 0,012 а

о

В- o,oi

о с

5 0,008

X

л

5 0,006

S

о 0,004 ь

° 0,002 0

1 10 19 28 37 46 55 64 73 82 91 100

Время работы, проценты

Рис. 2. Зависимость относительной лрогрешности прогноза (безразмерная величина) от прошедшего времени работы алгоритма (в процентах).

Как видно из графика, относительная погрешность составляет примерно 1.5% уже по прошествии 1/100 времени выполнения алгоритма. Такой

20 Здесь и далее использовались следующие данные:

gi|88952330|ref|NW_922462.1|HsCraAADB02_20, Homo sapiens chromosome 1 genomic contig, alternate assembly (based on Celera assembly). - GenBank, хромосома 1 генома Homo Sapience, версия от 04.09.2006. Последняя версия этого файла доступна по адресу

ftp://ftp.ncbi. nih.gov/genbank/genonnes/EukarYotes/vertebrates_mammals/Homo_sapiens/GR Ch37/Primary_Assembly/assembled_chromosomes/FASTA/dirl.fa.gz

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

Шестая глава посвящена алгоритму неточного поиска наибольшей общей подпоследовательности. Для двух строк алгоритм работает за время 0(п-2й), где (1 - константа, от которой зависит точность решения. В общем случае для к строк временная сложность является линейной относительно п и составляет 0(п-к■<?'). Более подробное исследование свойств алгоритма в этом случае, а так же применение алгоритма для решения других ИР-полных задач является предметом дальнейшей работы.

Графики, иллюстрирующие время работы в сравнении с точным алгоритмом, не приведены, так как время их работы несравнимо. Например, для строк длиной 10 тысяч символов точный алгоритм работает 420 миллисекунд, неточный - 63 миллисекунды, для строк, длиной 1 миллион символов время работы составляет 70 минут и 6,2 секунды соответственно.

Тестирование неточного алгоритма проводилось на случайных фрагментах ДНК. На вход подавались фрагменты ДНК длиной от 10 до 500 тысяч символов, глубина перебора с1 составляла 500. Верхняя линия соответствует среднему значению точности, нижняя - наихудшему значению. Во время тестирования осуществлялось по 50 запусков алгоритма с различными строками одной длины для получения среднего значения.

0,87 4-—-ТПТП I I I I I I М I И М I г-гл-ггтттт-гттттт-пгп ..... т

10 50 90 130 170 210 250 290 330 370 410 450 490 Длина строк, тысячи символов

Рис. 3. Зависимость относительной точности от размера строк (в тысячах сиимволов).

Средняя относительная точность для строк длиной 500 тысяч символов составила около 99.5%, причём это значение почти не ухудшается начиная с длины строк 100 тысяч символов. Точность в наихудшем случае не опускалась ниже 98%, за исключением двух случаев, когда она опустилась до 88%. В обоих этих случаях строки х и у начинались с относительно близких позиций в исходном файле (например, при длине строк 490 000 символов разница между начальными позициями составляла около 50 000 символов), из-за чего имели очень большую совпадающую часть - порядка 80-90%, которая начиналась с начала одной строки и с некотрой отдалённой позиции другой. Это приводило к тому, что оптимальный «маршрут» в таблице О оказывался сильно «сдвинут» относительно главной диагонали и не попадал в область, обрабатываемую алгоритмом. Для обнаружения подобных плохих случаев можно использовать алгоритм поиска наибольшей общей подстроки, работающий за линейное время21.

21 Д.Гасфилд. Строки, деревья и последовательности в алгоритмах. Информатика и вычислительная биология. - СПб; Невский Диалект, БХВ-Петербург. - 2003.

0,03

1 10 19 28 37 46 55 64 73 82 91 100

Время работы, проценты

Рис. 4. Зависимость относительной прогрешности прогноза (безразмерная величина) от прошедшего времени работы алгоритма (в процентах).

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

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

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

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

4. Разработан алгоритм неточного поиска наибольшей общей подпоследовательности. Алгоритм работает за линейное время для двух строк с точностью порядка 0.99 (для фрагментов ДНК длиной до 500 тысяч символов). В общем случае, для к строк, сложность так же является линейной относительно длин строк.

5. Проведён анализ эффективности разработанных алгоритмов.

4. ПУБЛИКАЦИИ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

Публикации в изданиях, рекомендованных списком ВАК:

1. А. Панин. Об одном алгоритме поиска наибольшей общей подпоследовательности двух строк. // Вектор науки ТГУ №4(14). - Тольятти, 2010. -стр. 19-22.

2. А. Панин. Применение мультиэвристического подхода к задаче определения схожести ДНК. // Вектор науки ТГУ №3(17). - Тольятти, 2011. - стр. 27-29.

Публикации в рецензируемых научных журналах и изданиях:

3. А. Панин. Алгоритм поиска длины наибольшей общей подпоследовательности двух строк. // Сборник тезисов докладов конференции молодых учёных, Выпуск 5. Труды молодых учёных. - СПб: СПбГУ ИТМО, 2010.

4. Д. Мерсон, А. Панин. Применение мультиэвристического подхода для

анализа сигналов акустической эмиссии. // [электронной издание] Материалы международной конференции «Современные проблемы математики, информатики и биоинформатики». - Новосибирск, 2011.

5. А. Панин, М. Точёная. Несколько подходов к оптимизации алгоритма вейвлет-преобразования реализованного на графическом процессоре. // [электронной издание] Материалы международной конференции «Современные проблемы математики, информатики и биоинформатики». -Новосибирск, 2011.

6. А. Панин, Ю. Хайруллова. Применение мультиэвристического подхода совместно со специальным алгоритмом архивации для сравнения последовательностей ДНК. // [электронной издание] Материалы международной конференции «Современные проблемы математики, информатики и биоинформатики». - Новосибирск, 2011.

7. Д. Мерсон, А. Панин. Применение мультиэвристического подхода для кластеризации сигналов акустической эмиссии. // Материалы международной научно-практической конференции «Молодёжь и наука: модернизация и инновационное развитие страны». Часть 2. - Пенза: Издательство ПГУ, 2011.

8. К. Крашенинникова, А. Панин. Об одном подходе к кластеризации ситуаций при решении переборных задач //В кн.: «Некоторые вопросы математического моделирования дискретных систем», монография. -Тольятти: изд-во ТГУ, 2011.

Подписано в печать 31.10.2011. Формат 60x84/16. Печать оперативная. Усл. п. л. 1,57. Тираж 120 экз. Заказ № 3-218-11.

Тольяттинский государственный университет 445667, г. Тольятти, ул. Белорусская, 14

Глава 1. Введение.

1.1 Основные задачи исследования.

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

1.3 Краткое содержание работы.

Глава 2. Фундаментальные понятия предметной области.

2.1 Эвристические алгоритмы.

2.2 Вейвлет-анализ.

2.3 Кластеризация.

2.4 Генетические алгоритмы.

2.5 Задачи обработки строк.

Глава 3. Мультиэвристический подход в задаче сравнения сигналов акустической эмиссии.

3.1 Математическая модель сигнала.

3.2 Предварительная обработка сигналов.

3.2.1 Выделение импульсов акустической эмиссии.

3.2.2 Вейвлет-преобразование сигналов.

3.2.3 Особенности применения технологии NVIDIA CUD А.

3.3 Сравнение сигналов.

3.3.1 Использование мультиэвристического подхода.

3.3.2 Функция корреляции.

3.3.3 Специальная версия алгоритма вычисления расстояния Лёвенштейна для сравнения сигналов.

3.3.4 Ещё один способ задания признаков.

3.4 Кластеризация.

3.5 Оптимизация параметров алгоритма.

3.5.1 Генетический алгоритм.

3.5.2 Метод Брента.33 •

3.5.3 Параметры оптимизации.

3.6 Результаты кластеризации.

Глава 4. Мультиэвристический подход в задаче сравнения генетических последовательностей.

4.1 Математическая модель ДНК.

4.2 Реализация мультиэвристического подхода.

4.3 Алгоритм поиска наибольшей общей подпоследователности.

4.4 Алгоритм Нидлмана-Вунша.

4.5 Результат сравнения цепочек ДНК.

Глава 5. Алгоритм поиска наибольшей общей подпоследовательности.

5.1 Математическая постановка задачи.

5.2 Описание нового алгоритма.

5.2.1 Изменение порядка перебора ячеек матрицы.

5.2.2 Использование массивов длин префиксов.

5.2.3 Использование списков вхождения символов.

5.3 Некоторые свойства алгоритма.

5.4 Схема алгоритма.

5.5 Оценка сложности.

5.6 Тестирование алгоритма.

Глава 6. Аппроксимационный алгоритм поиска наибольшей общей подпоследовательности.

6.1 Описание алгоритма.

6.2 Тестирование алгоритма.

Основные результаты работы заключаются в следующем:

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

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

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

4. Разработан алгоритм неточного поиска наибольшей общей подпоследовательности. Алгоритм работает за линейное время для двух строк с точностью порядка 0.98 (для фрагментов ДНК длиной 1 миллион символов). В общем случае, для к строк, сложность так же является линейной относительно длин строк.

5. Проведён анализ эффективности разработанных алгоритмов.

Предметный указатель алгоритм

Апостолико и Гиерра 48 Вагнера-Фишера 42, 48 Машека и Патерсона 49 нечёткой кластеризации 28 Нидлмана-Вунша 42 поиска наибольшей общей подпоследовательности 49 приближённый 59 Ханта-Шиманского 48 Хиршберга 48 вейвлет 10 вейвлет-преобразование 10, 20 генетический алгоритм 11, 30 импульсы акустической эмиссии 18 кластеризация 11,28 метод акустической эмиссии 16 Брента 32 митохондриальная ДНК 43 мультиэвристический подход 9, 24,39 наибольшая общая подпоследовательность 14, 47 оператор естественного отбора 11,12 мутации 11, 12 скрещивания 11, 12, 31 подпоследовательность 14 пропорциональный отбор 13 расстояние Лёвенштейна 14 для сигналов 26 редакционное расстояние 14 предписание 14 рулеточный отбор 13 турнирный отбор 13 фитнес-функция 12 функция корреляции 26 эвристика 9 эвристические алгоритмы 9 NVIDIA CUDA 22

Заключение

1. А. Аграновский, Д. Леднов. Теоретические аспекты алгоритмов обработки и классификации речевых сигналов — Москва: Радио и связь, 2004. — 164 с.

2. Д.А. Александров. Алгоритм муравьиной колонии для задачи о минимальном, покрытии. // XI междунар. Байкальская школа-семинар Методы оптимизации и их приложения, Труды, тЗ(1998), Иркутск. — с. 17—20.

3. М. Алёхина, А. Лысенко, Б. Мельников. Об одном подходе к моделированию вычислительных устройств. // Известия вузов. Поволжский регион. Физико-математические науки. No.2, 2007. — С.2—9;

4. Н.М. Астафьева. Вейвлет-анализ: основы теории и примеры применения// Успехи физических наук,1996, №11(166) — Москва: Издательство Института космических исследований РАН, 1996— с. 1145—1170(1996)

5. А. Ахо, Дж. Хопкрофт, Дж. Ульман. Структуры данных и алгоритмы. // Москва: Вильяме, 2003. — 382 с.

6. A.A. Барсегян, М.С. Куприянов, В.В. Степаненко, И.И. Холод. Методы и модели анализа данных: OLAP и Data Mining — Санкт-Петербург: БХВ-Петербург, 2004. 336 с.

7. С. Баумгертнер, Б. Мельников. Мультиэвристический подход к проблеме звёздно-высотной минимизации недетерминированных конечных автоматов // Вестник Воронежского гос. унив., сер. Сист. анализ и инф. техн., 2010, № 1. — С.5-7;

8. A.B. Боресков, A.A. Харламов. Основы работы с технологией CUDA. — М.: ДМК Пресс, 2010. 232 е.: ил.

9. И. Г.К. Вороновский, К.В. Махотило, С.Н. Петрашев, С.А. Сергеев. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности. Харьков: ОСНОВА, 1997. - 112с.

10. Д. Гасфилд. Строки, деревья и последовательности в алгоритмах. Информатика и вычислительная биология. — СПб: Невский Диалект, БХВ-Петербург. 2003.

11. E.H. Гончаров, Ю.А. Кочетов. Поведение вероятностных жадных алгоритмов для многостадийной задачи размещения. // Дискретный анализ и исследование операций. Сер. 2. тб(1999); №4. — с. 12-32.

12. JI.E. Горбачевская, Ю.А. Кочетов. Вероятностная эвристика для двухуровневой задачи размещения. // XI междунар. Байкальская школа-семинар Методы оптимизации и их приложения, Труды, т1(1998), Иркутск. с. 249-252.

13. Ю. Громкович. Теоретическая информатика. Введение в теорию автоматов, теорию вычислимости, теорию сложности, теорию алгоритмов, рандомизацию, теорию связи и криптографию. БХВ-Петербург, 2010. - 336 с.

14. М. Гэри, Д. Джонсон. Вычислительные машины и труднорешаемые задачи. М.: Издательство «Мир», 1982. - 416 с.

15. И. Добеши. Десять лекций по вейвлетам. — Ижевск: Издательство НИЦ «Регулярная и хаотическая динамика», 2001. — 464 с.

16. Н.Г. 3агоруйко. Прикладные методы анализа данных и знаний. — Новосибирск: .ИМ СО РАН, 1999.

17. С. Исаев Генетические алгоритмы в задачах оптимизации. / 2005. URL: http://masters.donntu.edu.ua/2005/kita/shestopalov/library/gaoptim.htm(AaTa обращения 29.10.2011)

18. Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. Алгоритмы. Построение и анализ. -М.: Вильяме, 2005. 1296 с.

19. Д. Кнут. Искусство программирования, т.2. Получисленные алгоритмы. — Москва: Вильяме, 2007. — 832 е.

20. К. Крашенинникова, А. Панин Об одном подходе к кластеризации ситуаций при решении переборных задач // В кн.: «Некоторые вопросы математического моделирования дискретных систем», монография. — Тольятти: изд-во ТГУ, 2011.

21. В.М. Курейчик. Генетические алгоритмы. — Таганрог: изд-во ТРТУ, 1998. -242 с. '

22. Медиченко М.П., Литвинов В.П. Радиотехнические цепи и сигналы. Ч. 1. -М.: МГОУ, 2011.-120 с.

23. Б. Мельников. Мультиэвристический подход к задачам дискретной оптимизации // Кибернетика и системный анализ(НАН Украины), 2006, №3. — С.32-42.

24. Б.Ф. Мельников. Эвристики в программировании недетерминированных игр. // Известия РАН. Программирование, 2001, № 5. — С. 63-80.

25. Б. Мельников, Е. Мельникова. Кластеризация ситуаций и принятие решений в задачах дискретной оптимизации. // Известия вузов. Поволжский регион. Технические науки. № 2, 2008. С.23-28;

26. Б. Ф. Мельников, А. Н. Радионов. О выборе стратегии в недетерминированных антагонистических играх. // Известия РАН. Программирование, 1998, №5.-С. 55-62.

27. Б. Мельников, С. Эйрих. Подход к комбинированию незавершённого метода ветвей и границ и алгоритма имитационной нормализации // Вестник

28. Воронежского гос. ун-та, сер. Сист. анализ и инф. техн., 2010, № 1, — С.35-38.

29. Е. Мельникова. Применение кластеризации ситуаций в эвристических алгоритмах для задач дискретной оптимизации: дисс. . : канд. физ.-мат. наук : 05.13.18 // Тольятти, ТГУ, 2009. 152 с.

30. Мерсон, Д. Л. Оценка состояния образцов стали 20 по параметрам акустической эмиссии / Д. Л. Мерсон, Е. В. Черняева, Д. Е. Мещеряков // XVII Петербургские чтения по проблемам прочности. Сборник материалов. СПб.: СПбГУ, 2007. Ч. 1 - С. 78-81.

31. Д. Рутковская, М. Пилиньский, Л. Рутковский Нейронные сети, генетические алгоритмы и нечёткие системы — 2-е изд. — М.: Горячая линия-Телеком, 2008.-С. 452

32. Ю. Сато. Обработка сигналов. Первое знакомство. Москва: Додека, 2000.- 175 с.

33. М. Сингер, П. Берг. Гены и геномы. Том 1. — М.: Мир, 1998. 373 с.

34. У. Смит Методы и алгоритмы вычислений на строках. М.: ООО «И.Д. Вильяме», 2006. - 496 с.

35. Л.Н. Степанова, А.Е. Кареев. Использование кластерного анализа для определения связи сигнала акустической эмиссии с характером разрушения в металлических образцах // Контроль. Диагностика. 2005. — №9. — С. 18-23.

36. А. Шевченко. Скважинная сейсморазведка. — Москва: Изд-во Российского государственного университета нефти и газа им. Губкина, 2002. 129c.

37. A. Apostolico, C. Guerra. The longest common subsequence problem revisited. // Algorithmica, Vol. 2, 1987. p. 315-36.

38. R. Bellman, S. Dreyfus. Applied Dynamic Programming Princeton University Press, Princeton NJ, 1962.

39. L. Bergroth, H. Hakonen, T. Raita. A Survey of Longest Common Subsequence Algorithms. // Proceedings of SPIRE, 2000. p. 39-48.

40. K.D. Boese, A.B. Kahng, S. Muddu. A new adaptive multi-start technique for combinatorial global optimizations. // Oper. Res. Lett. vl6(1994), N2. — p. 101-114.

41. R. Brent. Algorithms for Minimization without Derivatives, Chapter 4. // Prentice-Hall, Englewood Cliffs, NJ, 1973.

42. K. Deb, A. Kumar. Real-coded* genetic algorithms with simulated binary crossover. // Studies on multi-modal and multi-objective problems. — Complex Systems, 9(6), 1995. p. 431-454.

43. G. Gönnet, R. Scholl. Scientific Computation. Cambridge University Press, 2009.-250 p.

44. A.S. Graham. String Search. // Technical Report TR-92-gas-01. School, of Electronic Engineering Science University College of North Wales. — 1992.

45. A.S. Graham. String Searching Algorithms. World Scientific, 1994.

46. S. Henikoff, J.G. Henikoff. Amino Acid Substitution Matrices from Protein Blocks. //PNAS 89(22), 1992. -p. 10915-10919.

47. D.S. Hirschberg. A linear space algorithm for computing maximal common subsequences. // Communications of the ACM 18(6), 1975. p. 341-343.

48. J.W. Hunt, T.G. Szymanski. A fast algorithm for computing longest common subsequences. // Communications of the ACM, Vol. 20, No. 5, 1977. p. 350353.

49. S. Kirkpatrick, G. Toulouse. Configuration space analysis of traveling salesman problems. // J. de Phys. v46(1985), p. 1277-1292.

50. W.J. Masek, M.S. Paterson. A faster algorithm for computing string-edit distances. // Journal of Computer and Systems Sciences, Vol. 20, No. 1, 1980. — p. 18-31.

51. W.J. Masek, M.S. Paterson. How to compute string-edit distances quickly. // Time Warps, String Edits and Macromolecules: The Theory and Practice of Sequence Comparison. D.Sankoff, J.B.Kruskal eds. Addison-Wesley, 1983. -p. 337-349.

52. B. Melnikov, A. Radionov, V. Gumayunov. Some special heuristics for discrete optimization problems // 8th Int. Conf. on Enterprise of Information Sys-tems(ICEIS-2006), Pathos(Cyprus) pp. 91-95;

53. D. Merson, S. Dement'ev, A. Ioffe, P. Suvorov, A. Vinogradov. Acoustic Emission during Hydrogen Charging1 of a Pipeline Steel // ISIJ International , Vol. 51(2011) , No. 10. The Iron and Steel Institute of Japan, 2011 -pp. 1682-1687.

54. M. Mitchell. An Introduction to Genetic Algorithms. Cambridge, MA: The MIT Press, 1996.

55. H. Muhlenbein. Parallel genetic algorithm, population dynamics and combinatorial optimization. // Proc. Third Inter. Conf. Genetic Alg. San Mateo: Morgan Kaufman, 1989.-p 416-421.

56. E.W. Myers. An Overview of Sequence Comparison Algorithms in Molecular Biology.-1991.

57. S. Needleman, C. Wunsch. A general method applicable to the search for similarities in the amino acid sequence of two proteins // Journal of Molecular Biology, 1970,48(3). p. 443-453.

58. A. Pollock Acoustic Emission Inspection // Metals Handbook, Ninth Edition ASM International. Vol. 17.1989.-P.278-294.

59. A. Shipunov. Systema Naturae or the outline of living world classification //

60. Protistology. 2009. 6(1). p. 3-13

61. G. Stephen. String Search Algorithms World Scientific, 1994. - 256 p.

62. I. Torshin. Bioinformatics in the Post-Genomic Era: The Role of Bio-physics, Novapublishers, 2006

63. R.A. Wagner, M.J. Fischer. The string-to-string correction problem. // Journal of the ACM, Vol. 21, No. 1, 1974.-p. 168-173.

64. G. Wieds. Bioinformatics explained: BLAST versus Smith-Waterman. — CLCBio, 2007.

65. ГОСТ 27655-88. Акустическая эмиссия. Термины, определения и обозначения. — М.: Издательство стандартов, 1988. — 29 с.

66. Библиотека ALGLIB — URL. http://alglib.sources.ru/ (дата обращения 29.10.2011)

67. Генетические алгоритмы. — URL.: , http://math.nsc.ru/AP/benchmarks/UFLP/uflpga.html (дата обращения 29.10.2011)

68. NCBI Nucleotide database URL. http: //www.ncbi.nlm.nih.gov/nuccore (дата обращения 29.10.2011)

69. Processors Intel® microprocessor export compliance metrics // URL.:http://www.intel.com/support/processors/sb/cs-02314 3.htm (дата обращения: 29.10.2011)