Сборники тезисов • Сборник тезисов докладов конгресса молодых ученых. Выпуск 1 • ТЕХНОЛОГИИ ПРОГРАММИРОВАНИЯ, ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ, БИОИНФОРМАТИКА
ГЕНЕРАЦИЯ СЛОЖНЫХ ТЕСТОВЫХ ДАННЫХ ДЛЯ ЖАДНОГО АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ О МИНИМАЛЬНОЙ ОБЩЕЙ НАДСТРОКЕ
УДК: 004.023:519.161
Аннотация:
Введение. Задача о наименьшей общей надстроке имеет множество применений в
задачах вычислительной биологии (например, в сборке генома [1]). Задача является NP-
трудной [2], однако известны различные эвристические алгоритмы, позволяющие получать
приемлемые по оптимальности решения. Для одного из этих алгоритмов (GREEDY [3])
имеется следующая теоретическая оценка оптимальности: длина надстроки, полученной
этим алгоритмом, не может превышать 3,5N, где N – длина наименьшей надстроки [4].
Однако неизвестны входные данные, где длина такой надстроки равняется или превышает
2N.
Построение сложных тестовых данных для задачи о наименьшей общей надстроке, как
правило, производится вручную. В работе предлагается подход к построению таких тестовых
данных с помощью эволюционных алгоритмов. Вводятся новые критерии качества тестовых
данных. Тесты, сгенерированные с помощью эволюционного алгоритма, по указанным
критериям превосходят известные тесты, построенные вручную.